PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You’re given two permutations A and B, both of length N.
You can perform the following operation:
- Choose an index i, and either increment or decrement A_i by exactly 1.
Decide if it’s possible to convert A into B, while always maintaining A_i \ne A_{i+1} for all indices i.
EXPLANATION:
Often, in tasks like this one that require checking if it’s possible to convert one object to another via some operation, it’s helpful to try and find an invariant - that is, some property that cannot be changed by the operation.
In our case, the “forbidden” state is for some pair of adjacent elements to become equal to each other.
So, it’s natural to try and look at adjacent pairs of elements, and see what happens.
Let’s look at some index i, and particularly at the relative values of A_i and A_{i+1}.
Suppose A_i \lt A_{i+1} initially.
Then, since we cannot have A_i = A_{i+1} after an operation, and each operation can only change a given value by 1, observe that after any valid operation we must still have A_i \lt A_{i+1}.
The same applies to the opposite inequality too: if A_i \gt A_{i+1}, then this will be preserved after an operation too.
So, for every index i, the inequality between A_i and A_{i+1} will be preserved after a valid operation.
This means, if we’re able to turn A into B using only valid operations, then B must satisfy the same inequalities as A as well.
That is, for some index i,
- If A_i \lt A_{i+1}, then B_i \lt B_{i+1} must hold too.
- If A_i \gt A_{i+1}, then B_i \gt B_{i+1} must hold too.
If any index fails to satisfy this property, we can immediately say it’s impossible to turn A into B.
We’ve now obtained a condition that’s necessary for the conversion.
Luckily, it turns out to be sufficient too - that is, as long as all adjacent relative inequalities are preserved, it’s always possible to turn A into B.
Proof
Without loss of generality, assume A_1 \lt A_2.
Let i be the leftmost index such that A_i \gt A_{i+1}. If no such i exists, choose i = N.
Note that i \gt 1 for sure.Now, observe that A_i \gt A_{i-1} and A_i \gt A_{i+1}.
Further, we have A_j \lt A_{j+1} for each j \lt i.
So, we can do the following:
- Repeatedly increase A_i till it becomes some absurdly large number - say, 10^{100}.
- Then, for each j = i-1, i-2, \ldots, 2, 1 in order, increase A_j till it reaches A_i - (i - j).
That is, we’re creating the sequence 10^{100}, 10^{100}-1, 10^{100}-2, \ldots when looking back from i.- Next, for each j = 1, 2, 3, \ldots, i in order, reduce A_j till it reaches B_j.
It’s easy to see that we’ll never create adjacent equal elements this way, while also ensuring that all of A_1, A_2, \ldots, A_{i} end up becoming B_1, B_2, \ldots, B_{i} respectively.
This takes care of the increasing ‘segment’ at the start of the array.
It’s easy to see that if we had a decreasing segment instead, a similar construction works: just that we instead invert addition and subtraction.Now simply repeat this process starting from index i+1 onwards, working on increasing/decreasing segments appropriately.
Note that for any segment that’s “internal”, one of its endpoints can be increased massively and the other can be decreased massively without ever creating inequalities; after which it’s easy to fix the middle values and then bring the endpoints back to normal.
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'
for i in range(1, n):
if (a[i] < a[i-1]) != (b[i] < b[i-1]): ans = 'No'
print(ans)