ARRAYSTATE - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You’re given a sorted array A.
Perform the following operation K times:

  • Delete (one copy each of) the smallest and largest element in A, and append their sum to A.

Find the final array.

EXPLANATION:

We have A_1 \leq A_2 \leq \ldots \leq A_N.
Let’s analyze what happens when we repeatedly perform the operation.

  • In the first step, we of course choose A_1 and A_N, delete them, and append A_1 + A_N to A.
  • In the second step, note that the maximum is now A_N + A_1, because A_N by itself was already the largest element - so adding a positive number to it makes it larger than anything else.
    The smallest element, now that A_1 is gone, is A_2.
    • So, we delete (A_1 + A_N) and A_2 from the array, and insert their sum (A_1 + A_2 + A_N).
  • In the third step, we similarly see that the maximum is (A_1 + A_2 + A_N), while the minimum is A_3.
  • More generally, just before performing the i-th step, the maximum element will be
    A_1 + A_2 + \ldots + A_{i-1} + A_N, while the minimum will be A_i.
    The other elements (at indices i+1 to N-1) will remain as they are.

So, after K steps,

  • The elements A_{K+1}, A_{K+2}, \ldots, A_{N-1} will remain in A.
  • The maximum element will be (A_1 + A_2 + \ldots + A_K + A_N).

This means the solution is to just print the array

[A_{K+1}, A_{K+2}, \ldots, A_{N-1}, (A_1+A_2+\ldots+A_K+A_N)]

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = a[k:n-1] + [sum(a) - sum(a[k:n-1])]
    print(*b)
1 Like