A random walk week

The New Year week featured contests from the two usual platforms. First off, TopCoder held its SRM 704 on Thursday (problems, results, top 5 on the left, my screencast). I have almost shot myself in the foot by blindly challenging sky58's medium with a big testcase at the start of the challenge phase on the ground that he has been compiling and testing this problem right up to the end of the coding phase, suggesting he found a testcase where his solution fails but could not fix it in time. I got -25, but luckily Swistakk has returned the favor a couple of minutes later with a -25 of his own, and I was again within one challenge of the top which I was able to find in the remaining minutes.

To be completely honest, I have made another unsuccessful attempt at shooting myself in the foot during this match. The hard problem was about constructing a directed graph with at most 20 vertices with the given amount k (up to 100000) of Hamiltonian paths from the first vertex to the last one. I was having a hard time trying to come up with a working approach, so I've decided to fall back to one of the standard approaches that often work in this kind of constructive problems: a random walk. We start with some graph, then repeatedly add random edges while it has too little Hamiltonian paths, or remove random edges while it has too many, until we happen to get the exact amount.

However, just finding the number of Hamiltonian paths in an arbitrary graph with 20 vertices would require exponential time, which practically meant that I could make only a few random steps in the allotted two seconds, which was clearly not enough. So I've tried to find a family of graphs where, on one hand, I could find the number of Hamiltonian paths quickly, and on the other hand, the family should be rich enough that it can have any number of Hamiltonian paths up to 100000, and preferably have any number of paths achievable in very many different ways, in order for the random walk to be able to stumble upon one.

I was able to find such family relatively quickly: it would be almost acyclic graphs, where we have arcs from each vertex i to vertex i-1, and all other arcs go "to the right" - from each vertex i to vertices with numbers j>i. Counting the number of Hamiltonian paths in such graph is a relatively straightforward dynamic programming task, because whenever we make a "jump" vertex j when previously the largest visited vertex was i<j-1, we have to immediately go to the left through vertices j-1, j-2, ..., i+1 in this order, as we have no way of reaching them later. And the family seems reasonably expressive - for example, if we take all possible edges to the right, the number of paths would be 2^n-3 (we choose the subset of vertices we "jump" to), and if we take only edges from each i to i+1, there's just one path, with other configurations falling somewhere in between and hopefully covering each number many times.

I was so happy to find this family that I rushed to code this solution immediately, and submitted it as soon as I realized that it seems to work fast enough (always less than a second) at least on random inputs. However, I was by no means certain that it works in all cases - it might well be that some specific number of paths is harder to achieve, and since I only had a 2x-4x margin, a moderately higher number of random steps required would cause my solution to time out.

The shooting oneself in the foot aspect is that it's really easy to come up with a deterministic solution for the problem within this family of graphs. In fact, the fact that the maximum graph has the number of paths equal to a power of two strongly points toward that deterministic solution. And indeed, all other accepted solutions for this problem do exactly that. Somehow it didn't even occur to me to think in this direction during the round :) Can you see this final step?

One day later, Codeforces held its traditional Good Bye 2016 round (problems, results, top 5 on the left, my screencast). It was Gennady's turn to shoot himself in the foot this time, as he was not careful enough when challenging and earned -50 points for an unsuccessful attempt that proved decisive.

This round had a few interesting problems, but I think problem E was the most educational - it did not require much beyond putting together several standard approaches, but required a good understanding of those approaches to do so. You were given a string of digits s of length 200000, and at most 200000 queries, each query being a certain substring q_i of this string. For each query, you need to remove the smallest number of characters from this substring q_i in such a way that the resulting string contains 2017 as a subsequence, but does not contain 2016 as a subsequence.

Finally, let me turn your attention to another traditional contest that is still running: the Prime New Year Contest at SnarkNews. As usual, it includes only problems that were given in a team contest in 2016 but were not solved by any team there. You have plenty of time to try your hand at the hardest problems of 2016, as the contest runs until January 10. The solutions for three problems were described in this blog, so you can get a head start :)

Thanks for reading, and check back next week!