Robot in a Hallway
Contest: Educational Codeforces Round 133 (Rated for Div. 2)
Difficulty rating: 2000
Tags: data structures, dp, greedy, implementation, ternary search

There is a grid, consisting of $$$2$$$ rows and $$$m$$$ columns. The rows are numbered from $$$1$$$ to $$$2$$$ from top to bottom. The columns are numbered from $$$1$$$ to $$$m$$$ from left to right.

The robot starts in a cell $$$(1, 1)$$$. In one second, it can perform either of two actions:

- move into a cell adjacent by a side: up, right, down or left;
- remain in the same cell.

The robot is not allowed to move outside the grid.

Initially, all cells, except for the cell $$$(1, 1)$$$, are locked. Each cell $$$(i, j)$$$ contains a value $$$a_{i,j}$$$ — the moment that this cell gets unlocked. The robot can only move into a cell $$$(i, j)$$$ if at least $$$a_{i,j}$$$ seconds have passed before the move.

The robot should visit all cells without entering any cell twice or more (cell $$$(1, 1)$$$ is considered entered at the start). It can finish in any cell.

What is the fastest the robot can achieve that?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$m$$$ ($$$2 \le m \le 2 \cdot 10^5$$$) — the number of columns of the grid.

The $$$i$$$-th of the next $$$2$$$ lines contains $$$m$$$ integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$0 \le a_{i,j} \le 10^9$$$) — the moment of time each cell gets unlocked. $$$a_{1,1} = 0$$$. If $$$a_{i,j} = 0$$$, then cell $$$(i, j)$$$ is unlocked from the start.

The sum of $$$m$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each testcase, print a single integer — the minimum amount of seconds that the robot can take to visit all cells without entering any cell twice or more.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
4
3
0 0 1
4 3 2
5
0 4 8 12 16
2 6 10 14 18
4
0 10 10 10
10 10 10 10
2
0 0
0 0

Example output:
5
19
17
3

Editorial:
Let's first consider the possible paths across the grid that visit all cells. You can immediately think of two of them. The first one is: go right to the wall, turn into the other row and return. Let's call it a hook. The second one is: go down, go right, go up, go right and so on. Let's call it a snake.
Turns out, these two are basically the two extremes of all paths. You can start with a snake and turn into a hook when you wish. You can see that once you move right twice in a row, you can only continue with a hook. And as long as you didn't move right twice, you are just doing a snake.
Let's fix some path across the grid. What will its minimum time be? Calculate it iteratively. If you want to enter the next cell, and it's still locked, wait until it isn't. So there are some seconds of waiting (possibly, zero) before each cell.
However, why not instead do the following. Let's calculate the sum of waiting time required and wait for that amount of seconds before starting to move. All cells will be visited at the same time as before or even later. Thus, they will surely be unlocked if they were in the original plan.
So the goal is to calculate the minimum amount of time required to wait in the start, then add the movement time to it.
Once again, the path is fixed. Let the $$$k$$$-th cell of the path be $$$(x_k, y_k)$$$. If you start after waiting for $$$t$$$ seconds, then you reach the $$$k$$$-th cell at time $$$t + k$$$ ($$$k$$$ is $$$1$$$-indexed). Thus, the $$$k$$$-th cell should have $$$a_{x_k, y_k} \le t + k - 1$$$. If all cells satisfy this condition, then the path can be done after waiting for $$$t$$$ seconds at the start.
Let's rewrite it into $$$t \ge a_{x_k, y_k} - k + 1$$$. So, the condition tells us that $$$t$$$ should be greater or equal than this value for all cells. In other words, $$$t$$$ should be greater or equal than the maximum of the values over all cells.
Study the formula. Imagine we have some path with a known length and want to append a cell to it. That's pretty simple. Just update the maximum with the value with the corresponding cell and increase the length.
What if we wanted to prepend a cell to it? Turns out, it's not that hard as well. Every cell in the path gets its value $$$k$$$ increased by $$$1$$$. From the formula, you can see that this actually decreases the value of each cell by $$$1$$$. So the maximum decreases by $$$1$$$ as well. The only thing left is to update the maximum with the value of the new first cell. Well, and increase the length again.
Finally, let's learn how to choose the best path. We can iterate over the length of the snake part. The hook part is determined uniquely.
It's easy to maintain the maximum on the snake. Just append the new cell to the path.
How to glue up the hook part to that?
Well, actually, realize that the formula allows us to glue up two paths into one. Let path $$$1$$$ have length $$$n_1$$$ and maximum $$$\mathit{mx}_1$$$ and path $$$2$$$ have length $$$n_2$$$ and maximum $$$\mathit{mx}_2$$$. To make path $$$2$$$ start after path $$$1$$$, we just decrease its maximum by $$$n_1$$$. The resulting path has length $$$n_1 + n_2$$$ and maximum $$$\max(\mathit{mx}_1, \mathit{mx}_2 - n_1)$$$.
Let's look closer into what the hooks look like. They start in some column $$$j$$$, traverse all the way right, then left up to the same column $$$j$$$. If the snake part took both cells in its last column, then that's it. Otherwise, the hook has to take the final cell in the last column — column $$$j-1$$$.
If we manage to precalculate something for hooks that start in some column $$$j$$$ and end in column $$$j$$$, then we will be able to use that. Appending the final cell is not a hard task, since we know its index in the path ($$$k = 2 \cdot m$$$).
Let $$$\mathit{su}_{i,j}$$$ be the waiting time required for a hook that starts in cell $$$(i, j)$$$ and ends in a cell $$$(3 - i, j)$$$ as if the path started with the hook (cell $$$(i, j)$$$ is the first one).
$$$\mathit{su}_{i,j}$$$ can be calculated from $$$\mathit{su}_{i,j+1}$$$. Prepend it with a cell $$$(i, j)$$$ and append it with a cell $$$(3 - i, j)$$$.
The only thing left is to find the best answer. I found the most convenient to start with a snake of length $$$1$$$ (only cell $$$(1, 1)$$$) and progress it two steps at the time:
1. update the answer;
2. progress the snake to the other cell of the current column;
3. update the answer;
4. progress the snake into the next column.
Overall complexity: $$$O(m)$$$ per testcase.