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!

Tweet