A non-blind week

TopCoder SRM 691 wrapped up May's contests (problems, results, top 5 on the left, my screencast). rng_58 applied his usual start-from-hardest strategy which almost gave him the win this time - if not for xudyh's amazing performance. It didn't seem likely that all three problems can be solved in time, but xudyh has managed to do just that with only a few minutes to spare. Congratulations!

The hardest problem required both knowing an advanced algorithm, and being careful while reducing the problem to the said algorithm to stay within the time limit. You're given a 50x50 integer matrix with all values between 1 and 61. We pick two (possibly intersecting or even coinciding) submatrices uniformly at random. We find X - the least common multiple of all numbers in those two submatrices combined. Now we find the number Y - the smallest possible integer that does not divide X. What's the expected value of Y?

Yandex.Algorithm 2016 Round 1 on the first weekend of June has once again tempted contestants with submitting blindly for smaller penalty time (problems requiring Yandex login, results, top 5 on the left, analysis). Tourist has convincingly demonstrated that blind submissions are not essential to winning the round, as having instant feedback allows one to take more risks and thus proceed quicker. Congratulations!

Russian Code Cup 2016 Qualification Round 3 has finalized the list of 600 Elimination Round participants (problems, results, top 5 on the left, analysis). YakutovDmitriy has claimed the first place with a large margin, despite finishing more than 20 minutes later than second-placed jiry_2, all thanks to being careful and not submitting incorrect solutions. Great job!

I've mentioned a nice Code Jam problem last week: consider a RxC grid such that every cell has exactly one of its two diagonals drawn. Those diagonals separate the grid into pathways which connect 2*(R+C) unit segments on the sides of the grid to each other. Given a matching telling to which other unit segment should each unit segment be connected, construct any grid that results in such connectivity. R times C is at most 100.

It turns out that the relatively small constraints are a red herring: this problem has a O(R*C) solution. We can build it as follows: start by finding two adjacent unit segments that need to be connected. If they're on one side, they can be connected by placing exactly two diagonals next to them, and if they're in a corner, then just one diagonal will do. Moreover, it doesn't make sense to connect them in any other way, as then their pathway will just occupy more space while not bringing any benefit, and any "holes" surrounded by the pathway will be completely wasted as two pathways can't intersect.

Having connected those two, we pick another two unit segments that are adjacent in the remaining list - note that we also take those that might've been originally separated by the two segments we've already connected. Again, we will connect them while occupying the least possible space, and not leaving any holes between the new pathway and the wall. More formally, we'll start from the left segment, and go along the side of the already placed pathways while "keeping our right hand" on the already placed diagonals. You can see a couple of examples on the right.

We continue like this while there are still segments left to connect. If at some point there are no two adjacent segments to connect, it means that the original list requires two intersecting pathways, which is impossible to achieve. Another possible roadblock is that we don't reach the right segment from the left segment while keeping the right hand on the wall. That means that the grid has already became disconnected, and since we occupied the least possible space with each move, there's no solution at all.

Thanks for reading, and check back next week!

A diagonal week

The May 23 - May 29 week was full with various tournament rounds. TopCoder Open 2016 Round 2B took place on Thursday (problems, results, top 5 on the left). Top 40 have qualified for the Round 3s which was of course the main point, but W4yneb0t wasn't content with just that as he found 100 points in the challenge phase to snatch the first place from Egor – congratulations!

Google Code Jam 2016 Online Round 2 was the main event on Saturday (problems, results, top 5 on the left, analysis). Just four contestants have managed to solve all four problems in full, and EgorKulikov has claimed a clear first place by solving everything with 40 minutes to spare – great job! Of course, well done to all 500 contestants qualifying for Round 3.

I was the author of the hardest problem D in this round, but it's actually problem C which I found the most beautiful. Consider a RxC grid such that every cell has exactly one of its two diagonals drawn. Those diagonals separate the grid into pathways which connect 2*(R+C) unit segments on the sides of the grid to each other. Given a matching telling to which other unit segment should each unit segment be connected, construct any grid that results in such connectivity. R times C is at most 100.

I like this problem so much in part because the solution doesn't rely on any advanced algorithms or data structures – it is a pure thinking challenge. Consider giving it a go!

Russian Code Cup 2016 Qualification Round 2 selected another 200 participants for the upcoming Elimination Round (problems, results, top 5 on the left, analysis). With four easy problems and only one hard one, the competition for the top spots was all about accuracy. Tourist has demonstrated just that and has managed to overcome the early gap vs enot.1.10 to claim the top spot by just 7 penalty minutes. Way to go!

Finally, Google Distributed Code Jam 2016 Online Round 1 on Sunday was the first round in 2016 that challenged contestants with problems that require distributed solutions (problems, results, top 5 on the left, analysis). Unlike last year, the contestants already had quite a lot of experience with the format, and thus breezed through the easier problems. Last year's finalist simonlindholm has solved all problems correctly in just over an hour (out of the three available hours) – awesome job!

In my previous summary, I've mentioned a very nice ACM ICPC World Finals problem: 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.

Let's split the drives into two classes: increasing ones have b_i>=a_i, and all others are decreasing. First, we can note that all increasing drives should be reformatted before all decreasing ones (assume we reformat an increasing drive right after a decreasing drive; if we do those actions in reverse order, the end result is the same but the capacity we have before both reformattings is greater or equal).

The remaining part is to find in which order to handle the increasing drives, and in which order to handle the decreasing drives. To see that, consider the drive we reformat the first, with some parameters a_i and b_i. In order to not lose data, we need at least a_i capacity of the new drive. But if we have that capacity, we can also reformat any other increasing drive with the same or smaller a_i, and since increasing drives make our situation strictly better, we can always reformat them as soon as we have enough spare capacity. Because of this, we can always start by reformatting the increasing drive with the smallest a_i. And that, in turn, enables us to see that we can handle all increasing drives in sorted order by a_i. Similarly, all decreasing drives should be handled in reverse sorted order by b_i.

Now that we've figured out the exact order of reformatting the drives, we can find the required spare capacity by simply tracking the total available size after every operation.

Thanks for reading, and check back soon for some June news!

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 :)