A 7 minute week

The main event of the May 16 - May 22 week was ACM ICPC 2016 World Finals in Phuket (problems, results, top 12 on the left, video broadcast). ACM ICPC remains the most prestigious competition for university students for many reasons. First, a very extensive network of regionals and subregionals ensures high and broad participation. Second, the final event itself is organized on a massive scale, bringing everybody together for 4 days in a new city. Third, the format of the competition stays the same for decades, allowing the students to start preparing well in advance, and leading to the formation of regular training groups in many universities. And finally, this is a self-reinforcing stable state: the competition being the most prestigious results in more great students participating, more great companies hiring the winners and participants, more great problemsetters willing to invest time to prepare the tasks, all of which contribute back to the prestige.

This year’s finals was a great event – thanks a lot to everybody involved, in particular to the organizing ICPC team, to the problemsetters, to the sponsor IBM, and to the hosts from Thailand. This was my 14th World Finals, 2 as a participant and 12 as a spectator, and every year it keeps being exciting! And of course, congratulations to the winning Saint-Petersburg State University team, stealing the victory from the Shanghai Jiao Tong University by a mere 7 minutes of penalty time by solving their 10th and 11th problems 12 and 10 minutes before the end of the contest respectively!

The problemset was quite heavily skewed towards the technical side, but there were three problems that I enjoyed solving algorithmically: F, K and L. Of those, problem L has quite compelling statement: you have n disk drives (n up to 1 million), i-th having capacity a_i. You want to reformat all of them to a new filesystem, and i-th drive will have capacity b_i after reformatting. However, the drives are filled with data initially, and in order to reformat a drive you have to move its data elsewhere, be it other drives that gained more capacity after reformatting, or a new drive that you buy – that one already uses the new filesystem and doesn’t need reformatting. What is the minimum capacity the new drive needs to have in order to support reformatting all existing drives? Note that we are free to pick the order of reformatting the drives, and are free to move the data around arbitrarily between reformattings.

Thanks for reading, and check back soon as I clear the five-week backlog :)

Tweet