WATERMOVE - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You have N glasses of water.
In one move, you can move all the water from one glass to another.
This must be done exactly K times.

Minimize the maximum amount of water in any glass in the end.

EXPLANATION:

Each operation forces us to combine the water in two glasses.
However, we are not forbidden to choose an empty glass - so after the first operation we can simply choose an empty glass to combine with any other glass, thus not increasing the overall water in the glasses.

This means only the first operation is important.
Our aim is to minimize the maximum value, so the optimal choice is to just combine the smallest two glasses.

Thus, the answer is the maximum of:

  • \max(A), and
  • \min(A) + \text{second\_min}(A)

Each of these can be computed in \mathcal{O}(N) time, or you can sort and compute them in \mathcal{O}(N\log N) time for an easier implementation.

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    
    print(max(a[-1], a[0] + a[1]))