PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You have two arrays A and B, both of length N.
You can do the following:
- Choose an integer X.
- Let i be the leftmost index such that A_i \ge X
- Increment A_i by 1.
Can A be converted to B?
EXPLANATION:
Elements of A can only increase.
Thus, if A_i \gt B_i for any index i, it’s definitely impossible to make the arrays equal.
We now have A_i \le B_i for every index i.
Suppose A_i \lt B_i for some index i, so we need to increase the value at this index.
To increase A_i, we must perform an operation by choosing some X \le A_i.
However, since only the leftmost element of A that’s \ge X is modified, it’s optimal to choose exactly X = A_i; since the smaller the value of X is, the more likely it is that an element before index i gets increased instead.
Now, note that even choosing X = A_i does not provide a guarantee for A_i to increase.
In particular, if there’s an index j \lt i such that A_j \ge A_i, then A_i won’t be increased.
In fact, if such an index j exists, observe that it’s never possible to increase A_i at all!
This is because:
- If we choose X \gt A_i, the chosen index will certainly not be A_i.
Thus, A_j \ge A_i will be maintained. - If we choose X \le A_i, then we also have X \le A_j.
So, the element increased will be something strictly to the left of A_i, and not A_i itself.
In particular, once again we have A_j \ge A_i.
So, if for some index we have A_i \lt B_i but there exists an index j \lt i such that A_j \ge A_i, it’s again impossible to make A and B equal.
To check for this easily, observe that this is equivalent to: for every index i such that A_i \lt B_i, we must have A_i \gt \max(A_1, A_2, \ldots, A_{i-1}), i.e. A_i must be strictly larger than the maximum of the previous i-1 elements.
This allows us to check the condition for every index in linear time overall.
We now have the case where A_i \le B_i for all i, and also A_i \lt B_i \implies A_i \gt \max(A_1, A_2, \ldots, A_{i-1}).
In this case, it can be proven that it’s always possible to make A = B.
A simple construction is to repeatedly choose the largest index i such that A_i \lt B_i, and then choose X = A_i.
This will always result in exactly index i being chosen (because, by assumption, we know A_i is strictly larger than everything before it), so A_i will increase by 1 and both conditions will still hold.
Repeatedly performing this process will eventually make A=B.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 'Yes'
mx = 0
for i in range(n):
if a[i] > b[i]: ans = 'No'
if a[i] < b[i] and a[i] <= mx: ans = 'No'
mx = max(mx, a[i])
print(ans)