A delayed week

TopCoder SRM 722 on Thursday was the first contest of the Oct 9 - Oct 15 week (problems, results, top 5 on the left, analysis). TopCoder has put together an easier problemset with a very tricky medium problem this time, which put a great emphasis on the challenge phase. tourist, uwi and gainullin.ildar have found enough challenges to overtake the others into the top three. Congratulations!

Codeforces Round 440 took place early on Sunday (problems, results, top 5 on the left, analysis). All top scorers solved 4 problems, albeit different ones, and mere minutes separated them. khadaev was 1 minute faster than Errichto, and thus earned the first place. Well done!

Overlapping with that round, the Open Cup Grand Prix of SPb took place just an hour later (problems, results, top 5 on the left). Uncharacteristically for our team we had reasonable penalty time and just needed to solve the last problem in an hour to win — but missed a small detail in the problem statement and could not get it accepted, which allowed team Past Glory to score another victory — congratulations!

In continuing the great traditions of St. Petersburg State University championships, this contest featured many interesting problems, of which I'd like to highlight the two hardest ones. Problem F was an interactive problem about exploring a random maze with a communication delay. You are given a maze in a 20x20 grid with walls between cells. The maze is randomly generated to form a tree using the Kruskal-like approach. You control a robot that starts in the bottom-left corner. You can command the robot to move in one of the four cardinal directions, and you would receive a reply telling you that the robot has moved in that direction (if there was no wall there), or that it stayed in its current cell (if there was a wall). You need to get the robot in the bottom-right corner in 10000 moves. The catch is that you don't receive the replies right away: the reply to the i-th command only arrives after you send the (i+100)-th command. We can't afford 100 moves per cell, so we have to somehow continue exploring without knowing where exactly we are. Can you see an effective approach?

I have explained and analyzed our approach in this comment thread.

Problem H discussed formal proofs in the spirit of the Dirichlet problem from another St. Petersburg State University Championship this spring. You are given an undirected connected graph with at most 73 vertices and 492 edges, and a desired parity for each vertex (either odd, denoted by 1, or even, denoted by 0). The sum of all parities is 1 modulo 2. You need to prove that there doesn't exist a subset of edges of the graph with the desired parity of the number of edges adjacent to each vertex. It would be easy to prove, as it is well known that the number of vertices of odd degree in any graph is always even. However, you're only interested in proofs stated in a specific form.

Such proof is a sequence of clauses. Each clause is an "or" of zero or more variables and/or their negations. Each variable corresponds to an edge in the graph, and is true if we take this edge, and false otherwise. Each clause must be built in one of the three ways:

1. In can be an axiom, which in our case means that it must contain the variables corresponding to all edges adjacent to some vertex of the graph, with the number of negated variables having the parity that is opposite to the desired parity for this vertex. For example, consider a vertex of degree 5 and desired parity 0, with adjacent edges a, b, c, d, e. A valid axiom for this vertex would be for example !a|!b|c|d|!e, which would be false only if variables a,b,e are true, and variables c,d are false, but that would mean that the vertex has 3 adjacent edges which doesn't satisfy its parity requirement, so this axiom is always true.
2. It can be a conclusion, in which we take two previous clauses of form A|x and B|!x, and make a new clause A|B. Since both original clauses are true the conclusion is true as well.
3. It can be a transformation of a previous clause. We take a previous clause and a permutation of the set of all variables and their negations, and apply the permutation to the elements of the clause to get the new clause. The permutation can not be arbitrary: it must be an automorphism of the set of axioms (map every axiom to an axiom). Note that transformations are not a strictly necessary operation, as we could have constructed the resulting clause by applying the automorphism to the axioms used to build the original clause, and then repeating how it was built, but it allows to dramatically reduce the number of clauses in a proof.

Your goal to derive an empty clause in at most 1000 steps, which would mean a contradiction, and prove that the parities goal is impossible to achieve. Can you do that?

In my previous summary, I have mentioned a Codeforces problem: two players are playing a real-time game on a tree. The first player has one token, and in one second can move it to an adjacent vertex of the tree. The second player has several tokens, and can move them with infinite speed whenever they want. However, as soon as a token of the second player meets the token of the first player, this second player's token is removed from the game. The goal of the first player is to remove all tokens of the second player as fast as possible. How long would it take in worst case? You are given the tree and the starting locations of all tokens. There are at most 50 vertices in the tree, and at most 50 tokens.

We can notice that whenever we (the first player) are walking along an edge, only two numbers matter: how many tokens are there on each side of this edge in the tree. When we approach a vertex, the second player has to decide how to distribute the tokens on the side we're approaching between different subtrees of that vertex. We must then proceed into one of those subtrees, as going back along the edge we just arrived on just wastes two seconds. We must proceed into a subtree that has at least one token. Eventually, we will reach a leaf and remove all tokens which are there (at least one).

This makes our game acyclic, and we can solve it using dynamic programming where the state is the directed edge of the tree we're traversing, and two numbers: the number of second player tokens on each side of it. When we reach a vertex, in order to find how the second player will divide their tokens, we use an inner dynamic programming which computes the highest minimum time to finish the game if we placed a tokens into the first b subtrees of this vertex. This means we process one state in O(n³), and we have O(n²) states, for the total running time of O(n⁵). However, we can notice that the inner dynamic programming actually computes the answers not just for one state, but for all states with the same total number of tokens of the second player left, and thus the running time becomes O(n⁴) which is fast enough.

Thanks for reading, and check back soon for the next week's summary!