Monday, January 16, 2017

0.636 of a year

Very early on Wednesday, TopCoder SRM 705 set the pace for the competitions in 2017 (problems, results, top 5 on the left). Tourist would have been in the 7th place even if all his solutions failed the system test, thanks to an impressive challenge phase performance. And as usual, none of the solutions did fail, so he achieved an extremely commanding victory. Congratulations!

Later that day, Codeforces held its own opening contest of 2017 - Codeforces Round 391 (problems, results, top 5 on the left, analysis). Once again tourist has combined excellent solving with excellent challenging to claim a win, but the competition was much closer this time. Well done to tourist and to his competitors!

On Sunday, Codeforces held one more round: 8VC Venture Cup 2017 Elimination Round (problems, results, top 5 on the left, analysis). In case you have not noticed the pattern of the new year, it was tourist at the top once again. Impressive consistency!

In my last summary, I have organized a vote between top 5 problems of 2016 (of course, only according to my taste). Here are its results:

5. The problem about recovering the seed used for shuffling a permutation twice - post with solution. 13 votes, author: Ivan Kazmenko.
4. The problem about turning one string into another using two operations: replace one letter, or replace all occurrences of the same letter - post with solution. 17 votes, author: Adam Karczmarz.
3. The problem about exploring a cave with identical rooms interactively - post with solution. 21 vote, author: Georgiy Korneev.
2. The problem about implementing binary search that's takes at most log(n+1)+0.1 on average, not ceil(log(n)) - post with solution. 29 votes, author: Vasiliy Mokin (not sure, please tell if it's not correct).
1. The problem about turning a matching in the plane into a non-intersecting one that's at least 0.636x as long - post with solution. 37 votes, author: Gaoyuan Chen.

Big thanks to the authors of these and all other 2016 problems!

Sunday, January 8, 2017

A week of five

In my last week's summary, I have mentioned an educational Codeforces problem: you were given a string of digits s of length 200000, and at most 200000 queries, each query being a certain substring qi of this string. For each query, you need to remove the smallest number of characters from this substring qi in such a way that the resulting string contains 2017 as a subsequence, but does not contain 2016 as a subsequence.

First, suppose there were no queries and no removed characters, just one string and the need to check if it contains 2017 and 2016 as a subsequence. That would be an extremely easy problem which allows many solutions. There's one solution, however, that lends itself well to the complications of the full problem: we will build a deterministic finite automaton that accepts only strings that contain 2017 but not 2016 as a subsequence. You can find this automaton pictured on the right, all transitions not explicitly mentioned in the picture lead from a vertex to itself. It has 6 states, A is the starting state, and E is the final state.

In order to solve the full problem, we will create a segment tree (not the one from Wikipedia, but this one). For each segment of the given string, and for each pair of states of the automaton s and t, we will remember: what is the smallest number of characters that needs to be removed from this segment in order for the automaton to reach state t, if it starts in state s? In other words, each node of the segment tree will store a 6x6 matrix, and in order to combine the matrices for two child nodes, a process similar to matrix multiplication is needed.

Note that this approach would work for any deterministic finite automaton, not just for the one pictured above.

This post wraps up the solutions for problems posted in 2016. As such, it is a good time to take a look back and find the best problem of last year! I've taken a look at the 38 problems for which I've explained the solutions in my blog, and picked 5 that appeal the most to my taste. In chronological order:

The problem about implementing binary search that's takes at most log(n+1)+0.1 on average, not ceil(log(n)) - post with solution.
The problem about turning a matching in the plane into a non-intersecting one that's at least 0.636x as long - post with solution.
The problem about turning one string into another using two operations: replace one letter, or replace all occurrences of the same letter - post with solution.
The problem about recovering the seed used for shuffling a permutation twice - post with solution.
The problem about exploring a cave with identical rooms interactively - post with solution.

Could you help me pick one?

Thanks for reading, and check back next week!

Monday, January 2, 2017

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 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 2n-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 qi of this string. For each query, you need to remove the smallest number of characters from this substring qi 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!