ADJSUMLOST - Editorial

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:

  1. Sort B.
  2. Set A_1 = 1.
  3. 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)

This topic was automatically closed after 2 hours. New replies are no longer allowed.

This topic was automatically opened after 1 minute.