Robot in a Hallway 题解（补题）
题目原文
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
The first line contains a single integer t (1≤t≤10^4) — the number of testcases.
The first line of each testcase contains a single integer m (2≤m≤2⋅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),…,a(i,m) (0≤ai,j≤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⋅10^5.
Output
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.
Example
1 | input |
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output
题目大意
给定2行m列的矩阵, 矩阵中每个元素都有一个”解锁时间”, 必须等待时间达到解锁时间后才能到达(不能在到达解锁时间的同时走上去), 从左上角开始, 每一分钟可以在矩阵内上下左右移动一格或者原地等待, 要求出能够经过所有元素一次且仅一次的路径的最短耗时(初始时时刻为0, 且左上角被认为已经走过)
分析
事前
这道题当时进行了思考但没有做出, 回头看一眼, 好家伙, div2第三题难度就2000, 超出博主当前的能力水平, 一反div2的友好常态, 跟第二题相比简直是质的飞跃, 看来是这次出题人大发慈悲(苦笑). 之后博主看官方题解发现自己的思路正确, 但在动态规划的实现中因为没有发现更多隐含的性质没法做出, 决定补题后写下这篇题解
切入点
可以注意到一旦往左或往右的一段路径达到2格就必须延此方向一直走到头, 否则会引发矛盾无法遍历所有格子, 换句话说, 想要移动到另一行, 要么当前在第一列或最后一列, 要么当前在的那一列的左边所有格子都必须已经遍历过, 因此合法的路径被限定在以下两条规则中:
1.先从起点出发向下, 沿S型路径前进若干格(也可以先不动)
2.向右一直走到头, 换行再折回来, 遍历所有未遍历的格子(简称迂回路径)
由此可以遍历所有可能的路径, 暴力遍历必然超时
需要想到如何高效推算出各路径所花时间
大致思路
每次求一遍路径耗时肯定超时, 我们可以把路径拆成两段: S型路径段和剩下的迂回路径段, 动态规划递推求出各迂回路径耗时, 从起点开始枚举每一个S路径段, 与对应的路径段拼接计算耗时, 此时还有一些问题没解决:
1.怎么规范地求耗时
2.拼接路径后怎么计算耗时
3.迂回路径怎么表示和递推求解
4.拼接路径怎么对应
路径耗时计算
一条固定的路径所花时间按模拟法求的话思考比较复杂, 可分为两部分: 移动时间(必然固定)和等待时间, 在之后的计算中两者完全分开直到求最终答案
设路径上当前已等待总时间为t, 当前到了第k个格子, 其坐标为a[xk][yk]; 则必须t≥a[xk][yk]-k+1, t足够就不需要再等待, t不够就补上, 由此可以遍历完整路径后求出最小等待时间, 这也方便了之后的路径拼接
拼接路径
既然只用考虑等待时间了, 假设A路径长度为n1, 等待时间为mx1, B路径等待时间为n2, 等待时间为mx2, A终点可到达B起点, 注意到一条路径上小于最大值的等待时间相当于不用等, 而且拼接后B路径的等待时间中就免去了A路径的移动时间, 相当于补上B单独时没算的从A起点走过来的移动时间, 则拼接后等待时间为max(mx1,mx2-n1). (这样就免去了重新计算, 大大降低时间复杂度)
递推求迂回路径
迂回路径耗时可以倒推, 是因为具有以下性质:
假设 su[i][j] 表示从 a[i][j] 开始迂回路径到 a[3-i][j] 的最少等待时间, 注意到 su[i][j] 可由 a[i][j], su[i][j+1], a[3-i][j] 三部分推导出, 由拼接路径方式可得:
- su[i][j] = max(a[i][j], su[i][j + 1] - 1, a[3-i][j] - (2 * (m - j + 1) - 1))
由此即可递推求解, 注意其中减去的长度容易弄错
对应拼合路径
这个就比较简单了, 分奇偶列模拟S型路径每前进一格求一次对应迂回路径, 需要注意除最后一列外每列两格中有一个对应的迂回路径需要再补上最后一格
官方题解（英语）
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 (xk,yk). 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(xk,yk)≤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≥a(xk,yk)−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 n1 and maximum mx1 and path 2 have length n2 and maximum mx2. To make path 2 start after path 1, we just decrease its maximum by n1. The resulting path has length n1+n2 and maximum max(mx1,mx2−n1).
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⋅m).
Let 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).
su(i,j) can be calculated from 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:
update the answer;
progress the snake to the other cell of the current column;
update the answer;
progress the snake into the next column.
Overall complexity: O(m) per testcase.
官方代码
动态规划一般难点不在代码上, 这里需要注意其下标从0开始, 而题解从1开始, 式子稍有不同, 边界条件特殊处理
1 | INF = 2 * 10**9 |
