A week with H2

IPSC 2015 was the main event of the week (problems, results, top 5 on the left, analysis). The scoreboard looks suprisingly similar to last year: R+T+J on the top with 35 points (great job!), then HoChockiGon. The Polish team is now closer to the first place, with a 3 point gap instead of 6 points a year ago.

Among the problems my team didn't solve, I'm particularly disappointed not to solve problem H2 which was a very nice "classical" problem: you're given an undirected graph, and need to color its vertices into red and blue in such a way that the total number of edges between the red vertices is as close as possible to the total number of edges between the blue vertices. The solution is very simple and elegant, and after seeing it you don't understand how you could've missed it in the first place :)

TopCoder Open 2015 Round 2B was the other contest this week, with another 40 advancing to the final online selection stage (problems, results, top 5 on the left, parallel round results). One could compete onsite in San Francisco or online, and most fittingly the top 5 are all based in California (how many were actually onsite?). Congratulations to ACRush on continuing the 100% record in TopCoder in 2015, both in algorithm and in marathon!

Finally, let me come back to a problem I mentioned last week: you are given a row of n devices, each consuming some subset of k<=8 different resources when turned on, and producing some amount of energy when turned on. For each l from 1 to n you need to find the smallest r such that it's possible to turn on some devices from the segment [l;r] such that no two devices turned on consume the same resource, and that the total energy of the devices turned on is at least z.

When the left boundary l is fixed, we can use the following dynamic programming: start moving the right boundary r to the right, and maintain the highest possible energy we can obtain from each possible subset of resources in a 2^k-element array, spending O(2^k) operations on updating the dynamic programming array with a new device, As soon as the highest possible energy for the "all resources" exceeds z, we're done.

Now suppose we've ran this algorithm for some l, and now need to switch to l+1. First, it's easy to see that r will not decrease, so we should be able to just continue our dynamic programming from where we left off, and thus process all data in O(n*2^k) time. But we've missed an important step: we also need to somehow "remove" the l-th device from our dynamic programming array, and it's not clear how to do that.

However, if we had to remove the r-th device from the dynamic programming array instead of l-th device, it would be easy: we can just remember the state of the dynamic programming array before we added r-th device, and revert to that. In other words, we know how to work with a stack, but need to work with a queue. And of course, the computer science has the answer: one can emulate a queue using two stacks! Ever wondered if this textbook construction is practical? Well, now you know.

Having two stacks instead of one queue makes checking if we can produce at least z units of power slightly more difficult, but it still takes only O(2^k) operations since we need to iterate over all ways to split the set with k elements into two, and the total running time of this solution is thus O(n*2^k).

Thanks for reading, and check back next week for the Challenge24 results (a picture from last year from the official website is on the left)!

Tweet