PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
Greedy, (technically) Dynamic Programming
PROBLEM:
Given a 2\times N grid, can you swap the values in some of its columns (so \text{swap}(A_{1, i}, A_{2, i})) such that there exists a right-down path from (1, 1) to (2, N) whose values are non-decreasing?
EXPLANATION:
Let’s analyze the structure of a right-down path from (1, 1) to (2, N) (without caring about the values, for now.)
Since we start in the first row and end in the second, we certainly must move down at least once.
Suppose our first down move is in column x, so we move from cell (1, x) to (2, x).
Observe then that all moves other than in column x are forced.
Specifically, before column x we’re forced to move right to reach (1, x), and after column x we’re forced to move right to reach (2, N), so our path will look like
Suppose we fix the column x that we make the single down move in.
In this column, we then must swap values to ensure A_{1, x} \le A_{2, x} since we move top to bottom; which of course is always possible.
On the other hand, for all columns other than x, we only really care about one value in each, so we can freely decide which one we want to use.
To have the best chance of keeping the path non-decreasing, it’s clearly best to use the smallest possible value we can use at each step when moving left to right; since using a large value earlier might force us to move to a smaller value later on (which we don’t want).
Without loss of generality, let’s assume that we have A_{1, i} \le A_{2, i} in every column i.
Then, we have the following:
- In column 1, it’s best to start at A_{1, 1}.
- In column 2, it’s best to move to A_{1, 2} if we can.
- This is impossible if A_{1, 1} \gt A_{1, 2}, in which case we move to A_{2, 2} instead.
- This is also impossible if A_{1, 1} \gt A_{2, 2}, in which it’s impossible to even move to column 2 and we immediately say no solution exists.
- In column 3, the same logic holds: if it’s possible to move to A_{1, 3}, we should do so; if not we’re forced to move to A_{2, 3}, and if neither work, no solution can exist.
- This applies to every column till we reach column x.
- At x, we must be able to move to A_{1, x}, after which we move down to A_{2, x}.
- Beyond column x however, the same initial logic holds: if it’s possible to move to the smaller value, we do so; otherwise we move to the larger value; and if both fail then no solution can exist
This gives us a simple linear-time check for when we fix x to be the “down-column”.
Trying every choice of x will give us a solution in quadratic time, which is correct but too slow.
To optimize the above solution, we can store some intermediate results.
First, note that the section of the algorithm before column x didn’t really depend on x at all - it was just a simple greedy choice on the prefix.
So, let’s store \text{prefix}[i] to be the minimum possible last value on the path if we make the greedy choices till column i.
This is simple to compute, just following the earlier greedy choice:
- If A_{1, i} \ge \text{prefix}[i-1], then we have \text{prefix}[i] = A_{1, i}
- Otherwise, if A_{2, i} \ge \text{prefix}[i-1], then we have \text{prefix}[i] = A_{2, i} instead.
- If both checks fail, it’s impossible to reach column i at all, which we signify by setting \text{prefix}[i] = \infty (in practice, just some value larger than 2N since all values in A are \le 2N).
This allows all the \text{prefix}[i] values to be computed in \mathcal{O}(N) time.
Note that doing this allows us to easily skip one part of the check for x being a valid “down-column”: we just need to check if \text{prefix}[x-1] \le A_{1, x}.
It would be nice if we were able to precompute something similar for the part after x as well.
With a little thought, it turns out we can!
Rather than perform the greedy from columns x+1 to N in order, let’s try to perform the greedy from columns N to x+1 in descending order.
Done this way in reverse, it’s easy to see that it’s better to always choose the higher available value; since that will give us more options to go down as we move left.
Thus, we can define \text{suffix}[i] to be the optimal value in column i if we do the greedy from column N in descending order.
\text{suffix}[i] can be computed from \text{suffix}[i+1] and the values A_{1, i} and A_{2, i} just as \text{prefix}[i] was computed.
Once both \text{prefix}[i] and \text{suffix}[i] are known for all i, observe that column x is a valid “down-column” if and only if:
- \text{prefix}[x-1] \le A_{1, x}, and
- \text{suffix}[x+1] \ge A_{2, x}
So, if some x satisfies this condition the answer is "Yes", otherwise the answer is "No".
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a1 = [0] + list(map(int, input().split())) + [2*n + 1]
a2 = [0] + list(map(int, input().split())) + [2*n + 1]
for i in range(n+2):
if a1[i] > a2[i]:
a1[i], a2[i] = a2[i], a1[i]
pref = [0]*(n+2)
for i in range(1, n+2):
if a1[i] >= pref[i-1]: pref[i] = a1[i]
elif a2[i] >= pref[i-1]: pref[i] = a2[i]
else: pref[i] = 2*n+1
suf = [2*n+1]*(n+2)
for i in reversed(range(n+1)):
if a2[i] <= suf[i+1]: suf[i] = a2[i]
elif a1[i] <= suf[i+1]: suf[i] = a1[i]
else: suf[i] = 0
ans = 'No'
for i in range(1, n+1):
if a1[i] >= pref[i-1] and a2[i] <= suf[i+1]: ans = 'Yes'
print(ans)