Saturday, February 5, 2022

A Gomory-Hu week

TopCoder SRM 823 was the only round of this week (problems, results, top 5 on the left, analysis, TCO race standings). neal_wu and ksun48 were leading after the coding phase, but it all went downhill for them during the challenges. First, ksun48, who was less than 50 points away from the first place, made a quick challenge and earned -25, making neal_wu clear first with more than 50-point gap. A couple of minutes later, Kevin earned another -25. Then Neal decided to take the matters into his own hands and got a -25 of his own, which meant that while Kevin was still more than one successful challenge away, SSRS_ now needed just one +50 to take the first place and the 5 TCO race points, which he duly did closer to the end of the challenge phase. Congratulations on the victory! Neal and Kevin made two more unsuccessful challenges each, ending the round with quite bizarre -75 and -100 challenge points respectively.

In my previous summary, I have described a solution to a Codeforces problem. I'm not going to paste it here since it's very long, so please read the previous summary for context :) As the first step of my solution, I'm constructing another tree where the longest path queries become LCA queries, and then construct an inorder traversal of the new tree to answer LCA queries via RMQ queries.

tourist has pointed out this awesome comment to me, which shows that I did not really have a full understanding of what's going on when writing my solution. Indeed, let us look at the construction process of the new tree more closely and forget about future LCA queries for a second, just trying to keep the property that in the new tree the largest edge weight between any two vertices is the same as in the old tree. Then we can see that whenever we attach two subtrees to a newly created node, we don't really have to use the roots of the subtrees for that, and can use any node instead (because all edges within the subtrees have smaller weight than the currently processed edge, it does not matter which within-subtree edges will end up being used for the paths between the subtrees). And this allows us to keep all subtrees as chains, and connect them to form bigger chains, ultimately creating one big chain.

So it turns out that for any tree, we can construct a chain on the same vertices such that the maximum edge weight on the path between any two vertices is the same in the tree and in the chain, and of course the latter can be found using range-maximum queries. This chain is more or less equivalent to the inorder traversal of the auxiliary tree that was built in my solution, but I think constructing it explicitly is more beautiful and demonstrates a better understanding of the mechanics of the problem.

In an attempt to demonstrate an even better understanding of the mechanics, it seems to me that this construction is somewhat related to the Gomory-Hu construction. In fact, this construction seems to suggest that the Gomory-Hu tree can always be replaced by an equivalent Gomory-Hu chain! However, there seems to be no mention of a "Gomory-Hu chain" on the Internet, so I'm probably missing something here?

Update: Maxim Babenko has clarified the matters here: in the Gomory-Hu tree, for any pair of vertices not just the size of the minimum cut between them is equal to the size of the minimum cut in the original graph (as Wikipedia claims), but also the minimum cut itself (as a partition of the vertex set into two). In a Gomory-Hu chain the size of the cut is indeed still the same, but not the cut itself.

Thanks for reading, and check back next week!

3 comments:

  1. On Topcoder: I found an obviously wrong (TLE) submission that simply used backtracking to find the path on the 400. SSRS_ was also in my room, so I figured I should make sure I got this challenge before them. I had a max size test case prepared with a longest path of length 27 so I used that -- unfortunately unsuccessful.

    After SSRS_ passed me, I had two more challenge attempts to try to win which I took and unfortunately ended up in 2nd. Turned out the first submission I challenged was indeed TLE, I just didn't use the right test case.

    On Codeforces: https://codeforces.com/blog/entry/71568

    ReplyDelete
  2. I need your help in this pseudocode in pseint

    una empresa maneja códigos numéricos con las siguientes características: cada código consta de cuatro dígitos: el primero representa una provincia, el segundo el tipo de operación y los dos últimos, el número de la operación. escriba un programa que lea de teclado un número de cuatro dígitos, y posteriormente imprima en pantalla la siguiente información: por ejemplo si el código es 5922 provincia 5 tipo de operación 9 número de operación 22 en caso de que tenga mas de 4 dígitos en lugar del mensaje anterior, habrá que imprimir en pantalla el siguiente mensaje de error: error código no valido. si tiene menos de 4 dígitos se suponen 0 los primeros.

    Help please
    Thank you

    ReplyDelete