This week in competitive programming

A quite eventful week in competitive programming comes to an end.

On Monday, the onsite round of Russian Code Cup took place. If you haven't heard about it - it's a very well organized international competition, with a great onsite part, but with problem statements in Russian. Final results: http://russiancodecup.ru/round/15/results (top 5: myself, Gennady Korotkevich, Dmytro Dzhulgakov, Vladislav Isenbaev, Pavel Kunyavsky), problems: http://russiancodecup.ru/round/15/tasks. The final round lasted 3 hours, and there was online commentary during the entire competition. You can view the recording at http://russiancodecup.ru/, plus pictures at http://t.co/PxwO5lPfqF. They had personal cameras for some competitors, several other cameras on the floor, interviews, problem discussions and so on.

I had a very lucky day, solving the first five problems without mistakes quickly. I think the most important moment was the fourth problem. Here's the approximate statement in English: you are given a 1000x1000 grid of black and white cells, with top-left and bottom-right cells being black. You need to get from top-left cell to bottom-right cell. At every move, you go to an adjacent cell (sharing a side). If that cell is white, you're then teleported to a random white cell. What is the lowest expected number of moves you can achieve, assuming you follow the best possible strategy?

This is a nice problem that doesn't require complicated textbook algorithms, but rather concise thinking and implementation. I won't write the solution here so you can enjoy solving it :) In the contest, it was very important to get it right from the first attempt, it gave me a lot of breathing room.

In addition to the above commentary, here's my much less exciting screencast (still processing, hopefully will be up soon):

On Friday, TopCoder Single Round Match 592 took place. Results, problems. Top five on the picture. The round consisted of two reasonably "mainstream" problems (one on ad-hoc case study, and one on dynamic programming in combinatorics), plus one quite unusual problem. It went like this: there are N hidden non-negative integers P_i, arranged in a circle and  symmetric around zero: P_i=P_N-i for 1 <= i <= N-1. Now we calculate Q_i=sum(P_j*P_k), over all j and k such that j+k=i (modulo N). Given N non-negative integers Q_i, calculate the lexicographically smallest P_i that would give this result. N is up to 25. Again, won't spoil the problem in this post - try solving it if you haven't yet! Will describe the solution later. I was very close during the round - got the correct idea but had two bugs in my solution. You can follow my failed attempt in the screencast:

Also on Friday, Codeforces Round 202 took place, which I skipped, so I can only show you the results. Final results: http://codeforces.com/contest/348/standings, problems: http://codeforces.com/contest/348.

And finally, on Sunday, the second son of my friend, teammate and competitor Egor Kulikov and Kate was born - Petr Kulikov! Congratulations Egor and Kate!

Codeforces Round 201 and heart rate monitoring

Codeforces Round 201 took place a couple of hours ago. Results: http://codeforces.com/contest/346/standings, problems: http://codeforces.com/contest/346. Top five:

I've recorded my not very successful participation:

On a more interesting note, I've also recorded my heart rate during the round:

​The highest heart rate corresponds to hacking other solutions, and to trying to finish the solution to the hardest problem before the contest ends, which makes sense. What's a bit more strange is that the lowest heart rate corresponds to thinking about the hardest problem. Maybe that's why I didn't manage to solve it in time? :)

Codeforces Round 200 and Gomory-Hu tree

 

Codeforces Round 200 took place yesterday night. Congratulations to Codeforces for this milestone and for quite impressive 2372 participants! Division 1 results: http://codeforces.com/contest/343/standings, problems: http://codeforces.com/contest/343. Of course, congratulations to Gennady for winning yet again :) Here are the top 5 participants, the only 5 who could solve all problems:

The problemset involved two relatively straigtforward problems, two problems solved using standard ideas (binary search on answer + greedy for C, ordering vertices by dfs enter/exit time to translate subtrees into subsegments + interval tree for D), and one problem that I couldn't solve :) The problem asked about finding the longest Hamiltonian path in a graph where edge costs are maximum flows between pairs of vertices in a given graph.

It's actually quite a shame that I didn't know what to do at first, since this question is quite close to my area of research back at university. However, the problem seemed to come from a textbook, so I turned to Google. "pairwise maximum flow matrix" and "pairwise maximum flows" didn't give useful results, but "pairwise minimum cut" showed "We use a Gomory-Hu tree to represent all the pairwise min cuts implicitly." in the snippet of the third result, and finally "gomory-hu" returned the Wikipedia article that described the structure of pairwise minimum cuts in a undirected graph, precisely what we need in this problem. After reading that article, I'm pretty sure I studied this before but forgot about it.

The structure, decribed by Gomory and Hu (pictured above, photos from http://www.ralphgomory.com/ and http://cseweb.ucsd.edu/~hu/) is: we can find n-1 pairs of vertices, then find the minimum cut for each pair, forming the Gomory-Hu tree with those cuts as edge weights, such that the minimum cut for any pair of vertices is the minimum of weights of edges on the path connecting those vertices in the tree. The Wikipedia article gives more details, as well as the actual algorithm: http://en.wikipedia.org/wiki/Gomory%E2%80%93Hu_tree. I think it's amazing, and I encourage you to understand it!

Having found this with about one hour to go, I still couldn't solve the problem. I've spent quite some time implementing the algorithm and debugging it, and then the question of finding the longest Hamiltonian path remains. When I finished everything after the contest, my solution was still giving wrong answers - because the Wikipedia article apparently has a bug in it, or because I'm reading it wrong. When they describe the contracted graph G', they say that it contains original graph's edges within X, plus edges from X to S. But I could only get it to work after I've also added edges within S (obtained in a similar manner - by projecting the edges from the original graph). I hope there are people reading my blog who have better knowledge of the Gomory-Hu algorithm - is it indeed incorrect in Wikipedia, or do I read it wrong?