Sunday, April 9, 2017

A dominator week

First of all, please note that there's still a bit more than 3 hours left in the Google Code Jam qualification. You can still hop on the Code Jam train!

The last week was of the extremely busy type. First off, Codeforces Round 407 took place on Wednesday (problems, results, top 5 on the left, analysis). -XraY- and Um_nik stood out from the pack by solving all problems, and slightly better speed has earned -XraY- his first - but definitely not his last - victory of the week. Congratulations!

A Swiss-resident-only Helvetic Coding Contest 2017 took place on Saturday (results, top 5 on the left). Just like last year, the problems will be used for an online mirror some time later, so I will not spoil you the fun of solving them.

AtCoder Grand Contest 012 took place at the same time (problems, results, top 5 on the left, analysis). -XraY-'s second (but still not his last) victory was more clear-cut than the first one, as he managed to solve five problems fifteen minutes faster than everybody else, and was the only one at the top without any penalty minutes. Well done!

A few hours later TopCoder Open 2017 has taken off with its Round 1A (problems, results, top 5 on the left). With the top 250 active coders receiving a bye into Round 2, the contest has once again given semi-retired veterans a chance to shine, and it seems that ACRush did not forget how to win TopCoder rounds :) Congratulations!

Sunday took off with Open Cup 2016-17 Grand Prix of Tatarstan (problemsresults, top 5 on the left), where -XraY- has earned his third and final victory of the week, this time together with his team - amazing!

Problem E was of the kind that I prefer to give on my own contests, as it makes preparing the testcases very easy: with just two numbers in the input :) On a more serious side, here's what it was about: you are given two numbers n and k. You need to choose the smallest amount of pairs (a,b) such that 1<=a,b<=k for each pair, and such that any sequence of n not necessarily distinct numbers, each between 1 and k, will contain at least one of your chosen pairs as a subsequence.

Can you see the solution? Can you prove it?

Finally, Russian Code Cup 2017 Qualification Round 1 wrapped up the week on Sunday evening (problems, results, top 5 on the left, analysis). Even though the main goal here was to get into the top 200, there was still a scoreboard and it was possible to get the first place - which eatmore did thanks to flawless execution without any incorrect attempts. Way to go!

In my previous summary, I have mentioned a couple of problems. The first one went like this: you are given 300 trees on the same set of 300 vertices. You want to pick exactly one edge in each tree, remove those, then add the edge you removed from i-th tree to the (i+1)-th tree, for all i (the edge from the last tree is added to the first one), in such a way that the resulting graphs are still trees. How many ways are there to do that, modulo 109+7?

Let's say we picked the edge x-y in the first tree. After we add it to the second tree, a cycle consisting of this edge and the (only) simple path from x to y in the second tree will be formed, so we need to remove any edge in the said simple path to obtain a tree again. This edge in turn will define a path on the third tree where we need to pick an edge to remove, and so on. After we make a full cycle, we need to get back to the first edge.

If we fix the edge we pick in the first tree, we can use dynamic programming to find the number of ways to pick the edge to remove in the first a trees, such that b-th edge of the a-th tree is removed. This dynamic programming has O(n2) states, each state can be processed in O(n) (we need to traverse the corresponding path in the next tree), and we have O(n) outside iterations for the edge of the first tree, so the total running time is O(n4).

However, we can notice that the innermost O(n) is used to support an operation "add a constant to all edges of the tree along the given path". Here's how we can do it faster. Every path in a tree always goes towards the root until we reach the lowest common ancestor, then away from root. Now, instead of having values on edges and adding a constant c to the entire path from x to y, we can have values in vertices in such a way that the value for each edge is computed as the sum of values of vertices in the corresponding subtree, and then in order to add a constant to a path we need to add c to vertices x and y, and subtract 2c from lca(x, y) - just 3 numbers to be updated. This makes handling of each dynamic programming state O(1), and the total running time is now O(n3).

The second problem was: you are given a directed acyclic graph with 200000 vertices and 500000 arcs. We're going to remove one of its arcs. For each vertex v of the graph, you have to answer a question: is it true that v is guaranteed to be reachable from vertex 1, no matter which arc we remove?

This problem is closely related to the concept of dominator tree. Here, we would define that arc a dominates vertex v, if one must pass through a when going from 1 to v. Our goal is to tell if there are any dominating arcs for each vertex.

It turns out the following approach (corrected by Shubham in comments below - thanks!) works: assuming we have topologically sorted our graph from left to right, let's compute the leftmost dominating arc (or the fact there's no dominating arc) for each vertex. The computation will also go from left to right, and work like this for vertex u: if for each vertex reachable from 1 that have arcs into u the leftmost dominating arc is the same, then this arc is the leftmost dominating arc for u as well. If that's not the case, but there's just one vertex v reachable from 1 that has an arc into u, then the arc from v to u is the leftmost dominating arc for u (note that in this case v has no dominating arcs).

So far, everything is somewhat intuitive and easy to prove, but here comes the insight: in all other cases, there are no dominating arcs for u! Suppose it's not the case, and some arc a dominates u. We have at least two vertices reachable from 1 that have arcs into u, and the don't have the same dominating arc. Thus a can't be directly incoming to u, and at least one of the vertices that have arcs to u doesn't have a as its dominating arc, which leads to a contradiction since then we can bypass a on our way to u, too.

Thanks for reading, and check back next week!

No comments:

Post a Comment