HIGHWAYBYPASS from INOI 2014.

The solution on the INOI Practice Server goes something like this

rght[r][c][x] = (rght[r][c-1][x-1] + down[r][c-1][d]);

down[r][c][x] = (down[r-1][c][x-1] + rght[r-1][c][d]);

Where rght[r][c][x] is the number of paths to (r,c) that use at most ‘x’ consecutive moves in some direction (at some point in the path), and similarly for down[r][c][x].

But I think there is a flaw in this argument. I’ll try to give a counterexample.

Let the starting square be (0,0). I move 4 to the right, 2 down and 2 right, ending up at (2,6).

This is one of the ways that corresponds to rght[2][6][4] (Since the maximum number of consecutive segments is 4). Note that this path passes through (2,5) and (2,4).

Now according to the inductive step of the DP solution, the number of ways to reach (2,6) from (2,5) using at most 4 segments is the number of ways to reach (2,5) from (2,4) using at most** 3 segments. But while assuming this, the path we discussed above is omitted! **

That path provides a way to reach (2,5) from (2,4) using ** 4 segments.** And it is also a way to reach (2,6) from (2,5), still using only 4 segments.

Please let me know whether this is compensated for elsewhere in the algorithm.