PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
Given an array A, find any rearrangement of it such that the graph on N vertices with edges (i, A_i) is connected.
EXPLANATION:
When working with constructive problems, rather than try random things, it’s often helpful to try and work out some restricted cases first; and then attempt to generalize anything of interest that comes up.
For example, let’s try to solve this problem when all the elements of A are distinct, i.e for
A = [1, 2, 3, \ldots, N]
One fairly simple construction is to simple place all N elements on a large cycle, i.e. form the rearrangement
This has the edges (1, 2), (2, 3), (3, 4), \ldots, (N-1, N), (N, 1) which clearly forms a connected graph (it’s just a cycle of length N.)
Let’s now attempt to generalize the above idea to an arbitrary array.
So, say we have the array A.
Let the distinct elements that appear in it be x_1, x_2, \ldots, x_k in order from smallest to largest.
Observe that simply by using the cycle construction above, we can certainly connect all of these values.
That is, place value x_2 at index x_1, value x_3 at index x_2, and so on until value x_1 at index x_k.
This will create the cycle (x_1, x_2, \ldots, x_k) of length k, connecting these k elements.
What about the other indices?
Well, observe that for every other index, the value placed there must be some x_i (after all, the x_i are the only elements we even have.)
But as soon as we place some value at an index, that index gets directly connected to the cycle via an edge.
So, it doesn’t really matter what we do to the remaining indices - they’ll all end up joined to the cycle by a single edge anyway!
This means we can just find any rearrangement of the remaining elements into the remaining positions, and that gives us a valid solution.
To summarize, our solution is as follows:
- Let x_1, x_2, \ldots, x_k be the distinct elements appearing in A.
- For each i = 2, \ldots, k, place element x_i at index x_{i-1} of the answer; as well as placing x_1 at index x_k.
- All remaining copies of the elements can be placed at all remaining positions (there are N-k of each) in any order, and the resulting array is a valid rearrangement!
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()))
freq = [0]*(n+1)
distinct = []
for x in a:
freq[x] += 1
if freq[x] == 1:
distinct.append(x)
distinct.sort()
k = len(distinct)
ans = [0]*(n+1)
for i in range(k):
cur = distinct[i]
nxt = distinct[(i+1)%k]
ans[cur] = nxt
freq[cur] -= 1
p = 1
for i in range(1, n+1):
if ans[i] > 0: continue
while freq[p] == 0: p += 1
ans[i] = p
freq[p] -= 1
print(*ans[1:])