SUB12 - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

Binary search

PROBLEM:

You are given two arrays A and B of length N.
For each i, do one of the following exactly B_i times:

  • Add 1 to A_i, or add 2 to some A_j for j \neq i.

Find the minimum possible value of \max(A) after all operations have been performed.

EXPLANATION:

A very common strategy when attempting to minimize the maximum of several values, is to instead try to make all the values small enough: this will automatically make their maximum also small.

In particular, let’s check if, for a fixed value of M, we’re able to make all the final A_i values be \leq M.
If we’re able to achieve this then the answer is certainly \leq M; otherwise it’s certainly \gt M.

How do we perform this check?
Well, each operation with us adds either 1 to some value or 2 to some value.
Since we’re aiming to minimize, it’s intuitive to try and make as many of the operations be +1 rather than +2.

In particular,

  • If A_i + B_i \gt M, then we need to “move” (A_i + B_i) - M operations away from this index to other indices.
    Each operation moved will result in the value at this index reducing by 1, and the value at some other index increasing by 2.
  • If A_i + B_i \leq M, then we have some extra space at this index to accommodate external operations.
    Specifically, since each external operation will result in an increase of 2, we can accommodate \left\lfloor \frac{M - A_i - B_i}{2} \right\rfloor operations at this index.

So, for each i, we know either the number of operations it must send, or the number of operations it can receive.
If the total number of receives is more than or equal to the number of sends, we’ll be able to make everything \leq M; otherwise we cannot.

If M is fixed, the check for the answer being \leq M is easily performed in linear time.

Let f(M) be a boolean function, with it taking the value True if \text{answer} \leq M and False otherwise.
It should be clear that f is a monotonic function, i.e. if f(M) is true then f(M+1) is also true, and if f(M) is false then f(M-1) is also false.

So, we’re only interested in the smallest value of M for which f(M) is True.
This can be found by binary searching on M, which completes the problem.

There are a couple of things to be careful about here.

  1. The limits of the binary search.
    A reasonable starting point is to have the lower bound at \max(A), and the upper bound at \max(A) + \max(B).
  2. Be careful with overflow in the middle of the binary search, specifically during the \text{mid} = \frac{\text{lo} + \text{hi}}{2} step.
    While the final value is definitely going to be \leq 2\cdot 10^9, the \text{lo} + \text{hi} expression can be as large as 4\cdot 10^9 which exceeds the limit of signed 32-bit integers.

TIME COMPLEXITY:

\mathcal{O}(N\log(\max(A) + \max(B))) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    
    lo, hi = max(a), 2 * 10**9
    while lo < hi:
        mid = (lo + hi) // 2
        
        # can I make everything <= mid?
        need = have = 0
        for i in range(n):
            if a[i] + b[i] <= mid:
                d = mid - (a[i] + b[i])
                have += d//2
            else:
                need += (a[i] + b[i]) - mid
        
        if have >= need: hi = mid
        else: lo = mid + 1
    print(lo)
2 Likes