WARRIORCHEF - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Author: notsoloud
Tester: apoorv_me
Editorialist: iceknight1093

DIFFICULTY:

1433

PREREQUISITES:

Sorting or binary search

PROBLEM:

Chef has H strength, and needs to fight N enemies - the i-th of them has strength A_i.
If Chef’s resistance is X:

  • Any enemy with strength A_i\leq X can be defeated without losing any strength.
  • Any enemy with strength A_i \gt X can be defeated by losing A_i strength.

Find the minimum resistance Chef needs to defeat all the enemies, and still have positive strength remaining in the end.

EXPLANATION:

Suppose Chef’s resistance is X. Then,

  • Enemies with A_i \leq X don’t really matter, so we can ignore them.
  • Enemies with A_i \gt X cause Chef to lose exactly A_i health.
    So, the total amount of health lost by Chef is exactly the sum of all such A_i.
    Our objective is to find the smallest X that allows this quantity to be strictly smaller than H.

With this observation made, there are a couple of different ways to solve this problem.

Solution 1 (Sorting)

Let’s sort the array A, so that A_1 \leq A_2 \leq\ldots\leq A_{N}

In this sorted order, notice that the amount of strength lost by Chef will always be of the form (A_i + A_{i+1} + \ldots + A_N); because:

  • If Chef loses strength when fighting A_i, surely he’ll also lose strength when fighting something higher.
  • If Chef doesn’t lose strength when fighting A_i, surely he’ll not lose strength when fighting something lower.

So, let’s find the largest i such that (A_i + A_{i+1} + \ldots + A_N) \geq H (which also means A_{i+1} + \ldots + A_N \lt H).
If no such i exists, say i = N+1.

Then, X = A_i is the answer, since:

  • If X \lt A_i, then Chef will lose at least (A_i + A_{i+1} + \ldots + A_N) strength, which is \geq H and not allowed.
  • If X = A_i, then Chef can lose at most (A_{i+1} + A_{i+2} + \ldots + A_N) strength, which is \lt H and hence what we want.

So, X = A_i is the smallest resistance that satisfies the condition.

Solution 2 (Binary search)

Notice that if Chef can win with resistance X, he can also win with any resistance \gt X.
So, we can apply binary search to find the smallest applicable X.

To check if Chef can win with resistance X, it’s enough to directly apply the observation we made at the start: sum all the A_i that are larger than X, and check if it’s \lt H.

TIME COMPLEXITY

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

CODE:

Editorialist's code (Solution 1, Python) 
for _ in range(int(input())):
    n, h = map(int, input().split())
    a = sorted(list(map(int, input().split())))[::-1]
    ans, sm = 0, 0
    for x in a:
        sm += x
        if sm >= h:
            ans = x
            break
    print(ans)
Editorialist's code (Solution 2, Python) 
for _ in range(int(input())):
    n, h = map(int, input().split())
    a = list(map(int, input().split()))
    lo, hi = 0, 10**5
    while lo < hi:
        mid = (lo + hi)//2
        req = sum(x for x in a if x > mid)
        if req >= h: lo = mid + 1
        else: hi = mid
    print(lo)