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!

Wednesday, December 28, 2016

A black radius week

Last week was very calm, as most algorithmic competition websites have called it a year or are busy preparing special New Year-themed competitions.

Nevertheless, AtCoder held its Grand Contest 008 right on Christmas Day (problems, results, top 5 on the left, analysis). In breaking with AGC tradition, the problems were quite technical and tedious this time. Big congratulations to apiad who has managed to get all of them accepted and won!

I have spent all 110 minutes on the attractive-looking problem F, severely underestimating the amount of things that can go wrong in its solution (I got it accepted after about 5 more minutes of debugging after the end of the contest). The problem simply asks: given a tree with some subset of its vertices colored black, consider all subsets of its vertices defined as "all vertices at distance at most d from some black vertex a" (for all combinations of d and a), and return the number of different such subsets. When the same subset is defined through several combinations of d and a, it must still be counted only once.

(Moscow Christmas on the left - compare to last year :)) In my previous summary, I have mentioned an interactive Open Cup problem: you needed to give a checkmate to a lone king on a 8x8 chessboard using just one piece - the amazon, that can move both as a queen and as a knight. To makes things harder, you are playing blindfolded and do not know the king's position or moves. More precisely, you are given the initial position of the amazon, and need to output such sequence of at most 50 moves that the king that starts in any position that is not checked by the amazon and makes any legal moves will eventually be checkmated at some point in this sequence, and will not be stalemated before that.

There are multiple approaches described in the post-match discussion, highlighting the fact that the problem allowed one's creativity to shine. However, the solution described by Endagorion also allows to answer the extra question I posted last week: how short can such sequence of moves be if the amazon starts at a1?

It turns out this shortest sequence is "a1 a2 b3 b4 c5 c6 c5 d4 d3 d4 e5 e6 e5 f4 f3 e5 f6" (16 moves). And to prove this, Endagorion simply runs a breadth-first search over all reachable states of the game. The state of the game, in this case, is the position of the amazon plus the set of positions where the opposite king can be. At first glance it seems like we might get 64*264 states, but in practice the number of reachable states is much, much lower - most likely because the set of reachable squares for the king fills any unattacked area reasonably quickly, and thus we get much fewer possibilities (just 312400 states are reachable, and only 54520 of those are traversed before we find a way to checkmate definitely).

Thanks for reading, and check back in 2017! Happy New Year!

Monday, December 19, 2016

An amazon week

On Wednesday, TopCoder SRM 703 - the first TopCoder round after the TCO - took place (problems, results, top 5 on the left). Endagorion has claimed the victory thanks for an amazingly fast solution for the 1000 - he submitted it in just over 7 minutes! It turns out that a similar problem has appeared before, and he could reuse most of the code. Nevertheless, congratulations on the flawless execution!

Codeforces Round 385 on Saturday has gathered 8 nutella-rated participants, including the top 3 (problems, results, top 5 on the left, analysis). Tourist has guaranteed himself the first place in just over an hour, but couldn't solve everything because of extremely tricky geometric problem D. Congratulations on the win!

Here's problem E which has propelled him to the top, in a slightly simplified form: you are given n words with total length up to m, and need to check whether there exists a cyclic string that has at least two different decompositions into those words, in O(nm) time. For example, for a set {"aa", "aba", "ba", "bab"} the cyclic string "ababa"="babaa" has two decompositions: "aba" + "ba", and "bab" + "aa".

Finally, Open Cup 2016-17 Grand Prix of Peterhof has (probably?) wrapped up 2016 for many ACM ICPC teams (results, top 5 on the left). Problem E was the most unusual and thus the most creative: you needed to give a checkmate to a lone king on a 8x8 chessboard using just one piece: the amazon, that can move both as a queen and as a knight. To makes things harder, you are playing blindfolded and do not know the king's position or moves. More precisely, you are given the initial position of the amazon, and need to output such sequence of at most 50 moves that the king that starts in any position that is not checked by the amazon and makes any legal moves will eventually be checkmated at some point in this sequence, and will not be stalemated before that. Can you figure out how to do it? How short can such sequence of moves be if the amazon starts at a1?

Thanks for reading, and check back next week!

Sunday, December 18, 2016

A dfs week

Codeforces Round 383 was the main event of the last week (problems, results, top 5 on the left, analysis).  TooDifficult has regained the second place in the overall rankings thanks to his victory; his 2017 ACM ICPC World Finals rival mnbvmar is now ranked sixth thanks to his second place in this round. Well done!

In my previous summary, I have mentioned an unsolved NEERC 2016 problem where your program explores a maze with at most 20 rooms which look exactly the same. Each room of the maze has the same amount m (also at most 20) of outgoing one-way passages which also look exactly like one another, arranged in a circle. The only way not to get completely lost in this maze is to use the fact that each room also has a movable rock. Initially there's a rock is in the center of each room. When you leave a room, you can put the rock next to any outgoing passage, and moreover, you can choose whether to put it to the left or to the right of this passage (that means that there are 2m ways to put it). If you ever arrive in this room again, you will see whether the rock is placed to the left or to the right of a passage - but since all passages look the same, you won't have any other information! So now you will be able express the number of the passage to take, and the number of the passage to move the rock to by the number in clockwise order starting from the one marked with the rock when you arrive. Your goal is to visit all rooms in at most 20000 steps.

The solution is explained with pictures in the published analysis PDF (problem I), but let me repeat the outline here. We will implement a depth-first traversal of our graph. However, depth-first traversal sometimes needs to go back, and we can't do that since the passages are one-way. However, since the graph is strongly connected (it looks like I forgot to mention this property in the problem statement summary), there's always some way to get back. The main idea is: when leaving the vertex for the last time, mark the passage that leads as high up as possible in the depth first search tree. This way when we find ourselves in an already processed vertex, we can just follow the marked passages to get back to the current depth first search path. And inside that path, we will mark the passages that lead down this path, so that when we return to this path, we can then get down to the vertex that's being currently processed by the dfs. We can use left/right positioning of the rock to distinguish the vertices on the path ("grey") and the already processed vertices ("black"). There are some more technical details to the solution, but all ideas are above.

I find this problem very appealing for multiple reasons, one of them being that the solution is "tight": the amount of information we can store in the visited rooms turns out to be barely enough to perform the traversal. How can one come up with such tight problems?

Monday, December 5, 2016

A maze week

Last week was quite a bit calmer than its predecessors. On Monday, Code Festival 2016 wrapped up the festivities with its Grand Final (problems, results, top 5 on the left, online mirror results, analysis). It was W4yneb0t's day, as he managed to deny tourist a somewhat expected victory by solving the same amount of problems, but a more expensive set of them. Big congratulatons!

I did not cover a lot of ACM ICPC regionals this season, but now is a good time to start :) ACM ICPC 2016-17 NEERC took place on Sunday in St Petersburg, Barnaul, Tbilisi and Almaty (problems, results, top 5 on the left). One of the main events of the year for most of ex-USSR algorithmic competition community, and the main event of their entire algorithmic competition career for many teams who practice for multiple years for this one chance to advance to the World Finals. One can experience a very wide spectrum of emotions just by watching the NEERC award ceremony where some teams are full of joy and are not at all shy to share that moment with everybody, while others ruminate over the far-reaching consequences of just one bad day. Nevertheless, the community stays very close and friendly, and kudos to everybody for keeping the spirit going! And last but not the least, congratulations to the team SPb SU Base on the victory!

Problem I was left unsolved in the onsite competition, and it's a pity since I find it really beautiful. It's an interactive problem where your program explores a maze with at most 20 rooms which look exactly the same. Each room of the maze has the same amount m (also at most 20) of outgoing one-way passages which also look exactly like one another, arranged in a circle. The only way not to get completely lost in this maze is to use the fact that each room also has a movable rock. Initially there's a rock is in the center of each room. When you leave a room, you can put the rock next to any outgoing passage, and moreover, you can choose whether to put it to the left or to the right of this passage (that means that there are 2m ways to put it). If you ever arrive in this room again, you will see whether the rock is placed to the left or to the right of a passage - but since all passages look the same, you won't have any other information! So now you will be able express the number of the passage to take, and the number of the passage to move the rock to by the number in clockwise order starting from the one marked with the rock when you arrive. Your goal is to visit all rooms in at most 20000 steps.

The problem statement is quite abstract, so I encourage you to read in full in the PDF (problem I), especially the sample input/output. After you understand what's going on, however, I find it really exciting to solve!

In my previous summary, I have mentioned a CERC problem that had to do with bipartite matchings. You were given a bipartite graph with at most 20 vertices in each part (40 together). A set s of its vertices was called nice if there existed a matching that covers it - in other words, such that for every vertex from s there was an adjacent edge that belongs to the matching. Note that it's not necessary for each end of the matching edges to be in s. Each vertex also had an integer weight. Your goal was to count the number of nice sets (out of at most 240 total sets) with total weight exceeding the given threshold t.

I won't describe its detailed solution, but I will mention the main idea that makes this problem tractable. At first sight, we have 240 sets which is way too much to handle one-by-one. However, it turns out that a set s consisting of some set x of vertices of the first part and some set y of vertices of the second part can be covered by a matching if and only if both x can be covered by a matching and y can be covered by a matching (but those don't have to be the same matching)! This idea allows to reduce the number of sets to consider to 220, which is tractable.

Thanks for reading, and check back for this week's summary!