MAKEPERM - Editorial

editorial
,
1

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)