FOODRES - 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:

There are N types of food, the i-th has A_i units available.
M friends want to go on an adventure.
Find the maximum possible number of days they can adventure, given that:

  1. Each friend eats one unit of food everyday.
  2. A friend must eat the same type of food on all days.

EXPLANATION:

Let’s solve a slightly more restricted version of the problem first: suppose we also knew the value D denoting the number of days the adventure must go on for; and we only need to check if there’s enough food to do this.

Consider the i-th food item.
If k people want to eat it during the adventure, we’d need (at least) k\cdot D units of it available to satisfy them all, since each person eats one unit per day.
Thus, k\cdot D \le A_i must hold.

The largest valid k is exactly \left\lfloor \frac{A_i}{D} \right\rfloor, where \left\lfloor x \right\rfloor denotes the value of x rounded down to the nearest integer (a.k.a. the floor of x.)

So, with a fixed D, the maximum number of people who can possibly be satisfied equals

\sum_{i=1}^N \left\lfloor \frac{A_i}{D} \right\rfloor

If this quantity is \ge M then all M friends will be able to adventure for D days.
If this quantity is \lt M then there’s not enough food under the given constraints.

From above, we’re able to perform the check for a given value of D in \mathcal{O}(N) time.

Now, observe that if it’s possible to adventure for D days, then it’s certainly possible to adventure for \le D days as well.
On the other hand, if it’s not possible to adventure for D days, then it’s impossible to adventure for \gt D days.

This monotonicity allows us to binary search for the largest value of D that passes the check.

For the bounds of the binary search: 0 is a natural lower bound, while a trivial upper bound is \text{sum}(A).
Each check is done in \mathcal{O}(N) time, so we obtain an algorithm that’s \mathcal{O}(N\log (\operatorname{sum}(A))), which is easily fast enough.

TIME COMPLEXITY:

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

CODE:

Editorialist's code (PyPy3) 
n, m = map(int, input().split())
a = list(map(int, input().split()))

lo, hi = 0, 10**9
while lo < hi:
    mid = (lo + hi + 1)//2
    
    have = 0
    for x in a: have += x // mid
    
    if have >= m: lo = mid
    else: hi = mid-1
print(lo)
1 Like