PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
Sorting
PROBLEM:
For an array A of length N containing positive integers, form array B of length N-1 as follows:
- Set B_i = A_i + A_{i+1} for each 1 \leq i \lt N.
- Then, shuffle B.
You’re given B, find any valid A.
EXPLANATION:
Notice that if we fix the order of elements in B, and also the value A_1, all the elements of A will thereafter be uniquely fixed.
This is because we have B_i = A_i + A_{i+1}, so A_{i+1} = B_i - A_i.
So, fixing B_1 and A_1 will tell us A_2, then knowing B_2 will tell us A_3, and so on.
The only thing we need to ensure now is that all the A values obtained this way are positive.
Since A_{i+1} = B_i - A_i, this means we’d like B_i - A_i to be positive - or B_i \gt A_i.
One way to ensure this is to simply sort B, so that B_1 \leq B_2 \leq\ldots\leq B_{N-1}.
Then, choose A_1 = 1. This gives:
- A_2 = B_1 - 1 which is certainly \gt 0 (if B_1 = 1 then it couldn’t be the sum of two positive numbers anyway).
Note that A_2 is also less than B_1, since it’s obtained by subtracting 1 from it. - A_3 = B_2 - A_2.
Here, since we know A_2 \lt B_1 and B_1 \leq B_2, we also have B_2 \lt A_2. This means A_3 is positive as well.
Again, note that A_3 \lt B_2 since it’s obtained by subtracting a positive number from B_2. - This applies to every index i, in fact.
A_i = B_{i-1} - A_{i-1}, and since A_{i-1} \lt B_{i-1} will hold, A_i will be both positive, and less than B_{i-1}. Then, since B_{i-1} \leq B_i, we’ll have A_i \lt B_i so the inequality will be preserved for the next index.
So, we have a fairly simple algorithm in the end:
- Sort B.
- Set A_1 = 1.
- For each i = 2, 3, 4, \ldots, N in order, set A_i := B_{i-1} - A_{i-1} to reconstruct A.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
b = list(map(int, input().split()))
b.sort()
a = [1]
for i in range(n-1): a.append(b[i] - a[i])
print(*a)