PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: airths
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You’re given an array A of length N.
Does there exist another array B of length N such that the array C which has C_i = A_i +B_i is a permutation?
EXPLANATION:
The array B essentially allows us to increase each element of A as much as we like, since it contains non-negative integers.
The final array, after all increases have been done, should contain one occurrence each of 1, 2, 3, \ldots, N.
So,
- Some element of A should be increased to reach 1.
This is only possible if the chosen A_i is itself initially \leq 1.
In particular, the smallest element of A should be \leq 1. - Some element of A (other than the one chosen above) should be increased to reach 2.
Again, this means A should contain an element that’s \leq 2 other than the one that’s chosen to be 1.
Notice that this means that the second-smallest element of A should be \leq 2. - Some element of A should be increased to 3 - so the third-smallest element of A should be \leq 3.
\vdots - More generally, for any k, the k-th smallest element of A should be \leq k.
So, the condition we’re looking for is, quite simply, that for every k from 1 to N, the k-th smallest element of A shouldn’t exceed k.
This condition is easy to check: sort A and then check whether A_i \leq i for every i.
The constraints are small enough that a quadratic implementation that repeatedly extracts and deletes the minimum element is also fast enough to get AC.
TIME COMPLEXITY:
\mathcal{O}(N)\sim \mathcal{O}(N^2) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
ans = 'Yes'
for i in range(1, n+1):
mn = min(a)
if mn > i: ans = 'No'
a.remove(mn)
print(ans)