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?
No comments:
Post a Comment