A Johnson's week

Facebook Hacker Cup 2019 Round 3 was the main event of the Jul 22 - Jul 28 week (problems, results, top 5 on the left, analysis). The problems ended up a bit on the easy side, as 45 contestants solved everything and only 25 of them qualified to the onsite finals. Radewoosh was quite a bit faster in doing so, claiming the first place. Well done!

In my previous summary, I have mentioned an AtCoder problem: consider a complete directed graph on n vertices (n<=500), with the cost of the arc from i to j (i ≠ j) equal to -1 if i < j, and to 1 if i > j. Let's add n-1 more arcs with weight 0, going from i to i+1 to each i (those arcs will be parallel to the corresponding -1 arcs). For each arc with weight -1 or 1 we are given the cost of removing it from the graph, and arcs with weight 0 are not removable. What is the minimum total cost to remove some arcs in such a way that there are no cycles of negative weight remaining?

The key solution idea is borrowed from the Johnson's algorithm: the absence of negative weight cycles is equivalent to the existence of a set of vertex weights p_i, such that for every arc i->j with weight w_ij its adjusted weight w_ij+p_j-p_i is non-negative.

Applying w_ij+p_j-p_i>=0 to the non-removable zero-weight edges, we see that p_i+1>=p_i, in other words the sequence of vertex weights is non-decreasing. Let's split all weights into groups of consecutive equal weights, without loss of generality we'll first have a group of weights equal to 0, then a group of weight equal to 1, then a group of weights equal to 2, and so on.

For arcs with weight -1, w_ij+p_j-p_i>=0 means that all such arcs that are within one group must be removed, but there are no other restrictions since for such arcs i<j.

For arcs with weight 1, w_ij+p_j-p_i>=0 means that all such arcs that go two or more groups to the left must be removed, and those within the same group or going one group to the left can be kept.

This allows to implement a dynamic programming solution with O(n²) states: what is the smallest total cost of "already decided" removed arcs if we have already assigned the weights to the first i vertices and the last group of equal weights encompasses the vertices from j to i? Our transitions go from state (i,j) to state (k,i+1), and since we know two consecutive groups in a transition, we can correctly decide which additional arcs need to be removed because of that. We have O(n³) transitions, and the running time can also be O(n³) if we keep some running sums to quickly recompute the total cost of arcs that must be removed.

Thanks for reading, and check back for more!