Robot in a Hallway (Codeforces 1716C)
Tags: Greedy, 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: 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: 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.


Sample Inputs:
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

Sample Outputs:
5
19
17
3

Solution (Python):
t = int(input())
for _ in range(t):
    m = int(input())
    alist = []
    alist.append([int(ele) for ele in input().split()])
    alist.append([int(ele) for ele in input().split()])
    alist[0][0] = -1
    blist = [[0 for _ in range(m + 1)], [0 for _ in range(m + 1)]]
    for j in reversed(range(m)):
        for i in range(2):
            blist[i][j] = max(alist[i][j] + 2 * (m - j), alist[1 - i][j] + 1, blist[i][j + 1] + 1)
    cur = -1
    ans = float('inf')
    k = 1
    for j in range(m):
        k = 1 - k
        ans = min(ans, max(blist[k][j], cur + 2 * (m - j)))
        cur = max(cur + 1, alist[k][j] + 1)
        cur = max(cur + 1, alist[1 - k][j] + 1)
    print(ans)

Solution (Python):
standard_input = '5\n3\n0 0 1\n4 3 2\n5\n0 4 8 12 16\n2 6 10 14 18\n4\n0 10 10 10\n10 10 10 10\n2\n0 0\n0 0\n3\n0 0 2 \n3 3 2\n'
for _ in range(int(input())):
    c = int(input())
    a = [list(map(int, input().split())) for _ in range(2)]
    a[0][0] = -1
    pos = (0, 0)
    dync = [0 for _ in range(c)]
    y = 0
    for x in range(c - 1):
        y = not y
        curr = max(a[y][x] + 2, a[y][x + 1] + 1)
        dync[x + 1] = max(curr, dync[x] + 2)
    top = list(range(0, c, 2))
    latestTime = 0
    for x in top[::-1]:
        dist = (c - x) * 2 - 1
        if x + 1 < c:
            curr = max(a[0][x] + dist + 1, a[0][x + 1] + dist, a[1][x] + 1, a[1][x + 1] + 2)
        else:
            curr = max(a[0][x] + 2, a[1][x] + 1)
        latestTime = max(latestTime + 2, curr)
        dync[x] = max(dync[x] + dist, latestTime)
    bottom = list(range(1, c, 2))
    latestTime = 0
    for x in bottom[::-1]:
        dist = (c - x) * 2 - 1
        if x + 1 < c:
            curr = max(a[1][x] + dist + 1, a[1][x + 1] + dist, a[0][x] + 1, a[0][x + 1] + 2)
        else:
            curr = max(a[1][x] + 2, a[0][x] + 1)
        latestTime = max(latestTime + 2, curr)
        dync[x] = max(dync[x] + dist, latestTime)
    print(min(dync))

Solution (Python):
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    a[0] = -1
    a_p1 = [a[i] + i for i in range(n)] + [-2000000000]
    a_m1 = [a[i] - i for i in range(n)] + [-2000000000]
    b_p1 = [b[i] + i for i in range(n)] + [-2000000000]
    b_m1 = [b[i] - i for i in range(n)] + [-2000000000]
    for i in range(n - 2, -1, -1):
        a_p1[i] = max(a_p1[i], a_p1[i + 1])
        a_m1[i] = max(a_m1[i], a_m1[i + 1])
        b_p1[i] = max(b_p1[i], b_p1[i + 1])
        b_m1[i] = max(b_m1[i], b_m1[i + 1])
    preCost = 0
    ans = max(b_p1[0], a_m1[0] + 2 * n - 1)
    for i in range(0, n, 2):
        preCost = max(preCost, a[i] + (n - i) * 2 - 1, b[i] + (n - i) * 2 - 2)
        ans = min(ans, max(preCost, a_p1[i + 1] - (i + 1), b_m1[i + 1] + 2 * n - i - 2))
        if i == n - 1:
            break
        preCost = max(preCost, a[i + 1] + (n - i) * 2 - 4, b[i + 1] + (n - i) * 2 - 3)
        ans = min(ans, max(preCost, b_p1[i + 2] - (i + 2), a_m1[i + 2] + 2 * n - i - 3))
    print(ans + 1)
T = int(input())
while T:
    solve()
    T -= 1