PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
For an array A, the score of a permutation P is defined to be:
- -1, if P_i = i for any 1 \le i \le N
- Otherwise, the count of i such that A_{P_i} \le A_i.
You’re given A. Find any permutation P that attains maximum score.
EXPLANATION:
Since N \ge 2, it’s always possible to find a permutation P with P_i \neq i for all indices i.
This means we can always end up with a non-negative score.
Let’s try to understand what’s going on with the score.
Suppose there’s one person standing at each index from 1 to N. The person at index i is pointing to index P_i.
The score then increases by 1 for each person who is pointing to a number that’s not larger than the one they’re standing on.
Importantly, each person points to one index, and each index has exactly one person pointing to it.
With this perspective, it’s easy to see that achieving a score of N-1 is certainly always possible.
One way is as follows: let’s arrange indices in descending order of their values, i.e. consider the order of indices i_1, i_2, \ldots, i_N where A_{i_1} \ge A_{i_2} \ge\ldots\ge A_{i_N}.
Now,
- Make person i_1 point to index i_2, i.e. set P_{i_1} = i_2.
This makes the condition satisfied for index i_1. - Make person i_2 point to index i_3, i.e. set P_{i_2} = i_3.
Again, this satisfies the condition for index i_2. - In general, for each 1 \le j \lt N, set P_{i_j} = i_{j+1}.
This will end up satisfying the condition for each of these indices, for N-1 in total. - Finally, set P_{i_N} = i_1.
Index i_N is the only index that might not have the condition satisfied for it.
Now that we know achieving a score of N-1 is always possible, the next question should be: when is it possible to achieve a score of N? After all, that’s the best we can hope for.
For this, we need every element to be able to point to some other element that’s not larger than it.
Let the smallest element in A be m.
Observe that if there’s only one copy of m in the array, then it’s impossible for it to point to something else not-larger than it; so in this case the best score is just N-1.
Otherwise, there are several copies of m - and to satisfy the condition for all of them, they must all point to each other in some way or another.
This is doable: if their positions are x_1, x_2, \ldots, x_k then just set P_{x_1} = x_2, P_{x_2} = x_3, \ldots, P_{x_k} = x_1.
However, note that in doing so, we’ve exhausted all these elements - that is, nothing else can point to them.
So, we need to essentially recursively solve the problem for the remaining elements now.
That means the same analysis applies to the second-smallest element: if it has only a single occurrence, we’re forced into a score of N-1; otherwise our only option is to make all of its occurrences point to each other.
The same then applies to the third-smallest element, then the fourth-smallest, and so on.
In general, we obtain the following result:
If there exists an element in A that appears exactly once, the maximum possible score is N-1. Otherwise, the maximum possible score is N.
We’ve already seen how to obtain a score of N-1, and the construction for a score of N (when it’s possible) follows from what we did above: for each element, if its k\ge 2 occurrences are at x_1, x_2, \ldots, x_k then set P_{x_1} = x_2, P_{x_2} = x_3, \ldots, P_{x_k} = x_1.
TIME COMPLEXITY:
\mathcal{O}(N) or \mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
pos = [ [] for _ in range(n+1) ]
ones = 0
for i in range(n):
pos[a[i]].append(i)
if len(pos[a[i]]) == 1: ones += 1
if len(pos[a[i]]) == 2: ones -= 1
ans = [0]*n
if ones > 0:
print(n-1)
b = [(a[i], i) for i in range(n)]
b.sort()
for i in range(n):
ans[b[(i+1)%n][1]] = b[i][1] + 1
else:
print(n)
for lst in pos:
for i in range(len(lst)):
j = (i+1) % len(lst)
ans[lst[i]] = lst[j]+1
print(*ans)