A maze week

Last week was quite a bit calmer than its predecessors. On Monday, Code Festival 2016 wrapped up the festivities with its Grand Final (problems, results, top 5 on the left, online mirror results, analysis). It was W4yneb0t's day, as he managed to deny tourist a somewhat expected victory by solving the same amount of problems, but a more expensive set of them. Big congratulatons!

I did not cover a lot of ACM ICPC regionals this season, but now is a good time to start :) ACM ICPC 2016-17 NEERC took place on Sunday in St Petersburg, Barnaul, Tbilisi and Almaty (problems, results, top 5 on the left). One of the main events of the year for most of ex-USSR algorithmic competition community, and the main event of their entire algorithmic competition career for many teams who practice for multiple years for this one chance to advance to the World Finals. One can experience a very wide spectrum of emotions just by watching the NEERC award ceremony where some teams are full of joy and are not at all shy to share that moment with everybody, while others ruminate over the far-reaching consequences of just one bad day. Nevertheless, the community stays very close and friendly, and kudos to everybody for keeping the spirit going! And last but not the least, congratulations to the team SPb SU Base on the victory!

Problem I was left unsolved in the onsite competition, and it's a pity since I find it really beautiful. It's an interactive problem where your program explores a maze with at most 20 rooms which look exactly the same. Each room of the maze has the same amount m (also at most 20) of outgoing one-way passages which also look exactly like one another, arranged in a circle. The only way not to get completely lost in this maze is to use the fact that each room also has a movable rock. Initially there's a rock is in the center of each room. When you leave a room, you can put the rock next to any outgoing passage, and moreover, you can choose whether to put it to the left or to the right of this passage (that means that there are 2m ways to put it). If you ever arrive in this room again, you will see whether the rock is placed to the left or to the right of a passage - but since all passages look the same, you won't have any other information! So now you will be able express the number of the passage to take, and the number of the passage to move the rock to by the number in clockwise order starting from the one marked with the rock when you arrive. Your goal is to visit all rooms in at most 20000 steps.

The problem statement is quite abstract, so I encourage you to read in full in the PDF (problem I), especially the sample input/output. After you understand what's going on, however, I find it really exciting to solve!

In my previous summary, I have mentioned a CERC problem that had to do with bipartite matchings. You were given a bipartite graph with at most 20 vertices in each part (40 together). A set s of its vertices was called nice if there existed a matching that covers it - in other words, such that for every vertex from s there was an adjacent edge that belongs to the matching. Note that it's not necessary for each end of the matching edges to be in s. Each vertex also had an integer weight. Your goal was to count the number of nice sets (out of at most 2⁴⁰ total sets) with total weight exceeding the given threshold t.

I won't describe its detailed solution, but I will mention the main idea that makes this problem tractable. At first sight, we have 2⁴⁰ sets which is way too much to handle one-by-one. However, it turns out that a set s consisting of some set x of vertices of the first part and some set y of vertices of the second part can be covered by a matching if and only if both x can be covered by a matching and y can be covered by a matching (but those don't have to be the same matching)! This idea allows to reduce the number of sets to consider to 2²⁰, which is tractable.

Thanks for reading, and check back for this week's summary!