A Christmas week

Last week got going with Codeforces Round 336 (problems, results, top 5 on the left). Nobody was able to solve the hardest problem, which allowed matthew99 to win by solving the remaining four problems in about an hour. Successful challenges by tourist and ACRush brought them closer, but it was barely not enough for the victory. Congratulations matthew99!

On Saturday, TopCoder SRM 677 (problems, results, top 5 on the left) featured problems by cgy4ever, which are usually very entertaining. I didn't manage to take part since I was on a plane during the time of the SRM. Maybe I'll still manage to solve the problems in the practice room, will then share the best one in a later post.

ACRush continued his impressive comeback by winning the second SRM in a row - great job! In my last post, I've mentioned him climbing into the third place in the all-time SRM victory stats, but I was somewhat expecting tourist to take that third place soon, as he was just two SRMs short. Well, now I'm not so certain :)

(Christmas in Moscow on the left) Finally, let's discuss the tough problem C from the previous week's Open Cup: two strings of 0s and 1s are considered equivalent, if one can be obtained from the other by repeatedly removing or inserting (anywhere in the string) the following substrings: 00, 111, 0101010101. For example, 100110 and 010011 are equivalent, since we can do the following sequence of transformations: 100110 --> 1110 --> 0 --> 0111 --> 010011. Given 4000 strings of total length at most 50000, find out the groups of equivalent strings among them.

The first approach that comes to mind is to build some kind of "reduction" process - in the example above, both strings could be reduced to just "0" by repeatedly removing the 00/111 substrings. However, it is very tricky since sometimes you have to first add something in order to be able to remove a bigger pattern. For example, if you have substring 001010101, then you can insert 111 to get 011101010101, then insert 00 to get 01100101010101, and finally remove the last 10 characters to get 0110. Building a system of reduction that always works is hard, and can probably only be accomplished by implementing a stress-test that will give you missing reductions with small lengths until you can catch all of them. Here's the description of such approach by darnley in Russian.

However, the problem becomes much more tractable if we bring in some powerful theory. One can notice that we have a presentation of a group with two generators and three relations here, and need to check if the given products represent the same element of the group. Which group is it? Well, the Wikipedia article referenced above actually has an answer: this is the group of rotations of an icosahedron, with 1 corresponding to a 120-degree rotation around a line passing through centers of two opposing faces, and 0 corresponding to a 180-degree rotation that swaps two opposing vertices. Now the only remaining challenge is to see how the vertices of an icosahedron are permuted by each of those two rotations, and the actual code simply boils down to multiplying permutations of 12 elements.

Reading the Wikipedia article more carefully, we can notice that the group is actually isomorphic to A₅, so there exist an even permutation of degree 2 and an even permutation of degree 3 with just 5 elements that will also work in the above solution. How do we find those permutations? Well, there's just one permutation of each kind up to renumbering of elements (two transpositions and a cycle of length 3), and we have to pick such two permutations that their product has degree 5. Now it's very easy to find two permutations that fit.

However, the Wikipedia article in question is not easy to find if you forget the right terms. What to do if you remember that this is related to groups but don't know about the icosahedral symmetry? We can approach the problem from the other side. Suppose we can come up with _any_ two permutations p and q such that p*p=e, q*q*q=e, and p*q*p*q*p*q*p*q*p*q=e. Then, we can multiply those permutations according to the sequences from the input, and in case two sequences resulted in different products we know that they're not equivalent. In case they resulted in the same product, we can't be sure (for example, if both p=e and q=e, this will always happen). But if we try enough (p, q) pairs, most likely we'll be able to differentiate. So we can use simple brute force to find a few such (p, q) pairs, and use them to compare our sequences!

Thanks for reading, and Happy New Year! Now on to the New Year Contest, let's see how many different languages I can remember in the remaining time :)

Tweet