# ARRAYSTATE - Editorial

Author: raysh07
Tester: tabr
Editorialist: iceknight1093

Cakewalk

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