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 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.

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!