Subtask 1

We observe that we can maintain a state ~(r, c, flip)~. Note that the flip state is simply a boolean.

Now finally, in order to optimize this to ~\mathcal O(N^2)~ states with an ~\mathcal O(N)~ transition, we need to observe that there are only ~3N~ relevant columns, those being the ones to the left, on top of, and to the right of the lasers. Proof is left as an exercise to the reader.

This finally yields us a partial solution.

Time Complexity: ~\mathcal O(N^3)~

Subtask 2

First, observe that for any ~(r, c)~, only one flip state is actually relevant. Since we process row-by-row, we can reject states such that ~(r, c, flip)~ would have us vaporized.

Now, we need to optimize our transition.

To do that, note that for each cell, either it is optimal to walk down (flip as needed), or it is optimal to walk just past the laser in the next row. This is simply because it is never optimal to walk farther. If we want to walk farther, we can instead wait until we are on the next row to walk farther.

This allows us to optimize our transition to ~\mathcal O(1)~.

Time Complexity: ~\mathcal O(N^2)~

Subtask 3

For this subtask, we need to optimize both our state and our transition.

To do that, let's throw our state into a segment tree for fun. Now, we want to transition in sub-linear time. To do that, let's break our transition into three parts.

Consider the two lasers, the one in the current row and the one in the next row. Split the sections into left, middle and right. Each section has the same flip state.

Now for all three sections, they can walk down (flipping as needed) into the next row. Alternatively, they can walk to the other side of the laser in the next row.

To do this efficiently, we need a segment tree, make ~3~ queries, and then ~6~ updates.

The segment tree needs to support range addition. Also, in order to calculate walk distance for a range and query that, the segment tree should be initialized with the distances from the left and right side. Then we want to query for the minimum ~v + d~ over a range, where ~d~ is the walking distance. Then we need to be able to point update as well.

Implementation details are left as an exercise to the reader. A policy-based implementation is strongly recommended. Specifically, we can write our update and query traversals once, and provide a function to be called at each node, as the "policy". This Wikipedia article may be of help.

Time Complexity: ~\mathcal O(N \log N)~

Final Notes

Initially, this problem was proposed with the ability for Moses to go up. However, the reference solution, and many other implementations, did not correctly consider this. As such, in the middle of the contest, the constraint on Moses's movement was added. If this affected you, you can request to be unrated.