A test-driven week

The Nov 13 - Nov 19 week had one each of the usual suspects. First off, Codeforces Round 446 took place on Friday (problems, results, top 5 on the left, analysis). moejy0viiiiiv has earned his first place at the very last minute of the contest by solving D — very well done!

Then, TopCoder SRM 723 happened on Saturday (problems, results, top 5 on the left, analysis, my screencast). Only ksun48 was able to solve the hard problem, but it took him so long that his score was on par with scores people got for their medium problem, and the first place was decided during the challenge phase.

And finally, the Open Cup Grand Prix of Siberia wrapped up the week on Sunday (problems, results, top 5 on the left). Team Past Glory has continued their streak which is now up to 4 consecutive victories, this one by a mere 29 penalty minutes. Well done!

Problem 2 in this round is a good example of a problem that is not so hard to solve in some way, but is harder to solve in a way that is really easy to code without bugs. This is an interactive problem happening on the faces of a cube with each face divided into n times n cells (n<=300). You are located on some cell on some face of the cube, facing one of the four cardinal directions, and your goal is located on some cell on some face of the cube, but you don't know where you are located and where the goal is located. All you can do is to issue commands left, right or forward, with the first two causing you to rotate in place by 90 degrees, and the last one causing you to move one cell in the direction you're facing, with moving through the sides of the cube handled in the natural way. For each move forward, the system tells you whether your new cell is closer, farther or at the same distance from the goal as the old one. The distance is defined as the Euclidean distance between the centers of the cells. You need to stop moving at the goal cell after using at most 100n commands. Which approach is the easiest to implement here?

In my previous summary, I have mentioned a Codeforces problem: how many permutations of size n have the following property: if you go from left to right, and keep track of the maximum seen so far, there will be no time where it will not change for k consecutive steps, except if it's already equal to n. n and k are up to a million, and the answer needs to be returned modulo 10⁹+7.

First, let's come up with a standard but slow solution. We'll do dynamic programming that finds the number of such permutations of size m<=n that the last element is the maximum and there's always an update to the maximum in each k consecutive steps when we go from left to right. In order to find this number, we iterate over the step p where the previous maximum appeared: it has to be between m-k and m-1. Then we need to multiply the answer for p by the number of ways to choose which m-p-1 numbers out of m-2 form the numbers on positions between p+1 and m-1, and in which order, which turns out to be simply (m-2)!/(p-1)!, so our final formula becomes:

dp[m] = sum(dp[p]*(m-2)!/(p-1)!, m-k<=p<=m-1)

This looks to be O(n²), but we can now notice that (m-2)! can be moved outside the sum, and the remaining sum can be computed in O(1) if we store prefix sums of dp[p]/(p-1)!, bringing the overall running time to O(n).

You can watch as I code the solution in the screencast to see my proposed way of implementing such solutions: start by implementing the quadratic approach, get it to pass the sample cases, then start implementing the optimizations one by one while keeping it passing the sample cases. One step that I did not make but should have is to also add a few random cases that are still small enough for the quadratic solution to handle to the samples, and make sure the outputs don't change on them while optimizing, too.

Thanks for reading, and check back for more!