INTWOS - Editorial

Sugar Rush - EDITORIAL:

Practice

Contest

Author: kishen1912000, alphatron99

Editorialist: kishen1912000

DIFFICULTY:

EASY

PREREQUISITES:

Binary Search

PROBLEM:

Given N piles of chocolates with C_i chocolates in the i^{th} pile, and in a turn you can pick a pile and eat at most K chocolates from it. Find the minimum K such that you can eat all chocolates in at most D turns.

QUICK EXPLANATION:

Do a binary search on [1, max(C_i)] for K.

EXPLANATION:

As we can observe, the value of K will be in the range [1, max(C_i)]. So, we need to find the minimum K which can clear all the chocolates in at most D turns. Time taken to check if a value of K is valid, that is you can eat all chocolates, is O(N). By implementing binary search to find the value of K, we can solve this in O(NlogN) time. Also, note if D \lt N, then it is not possible to find a K.

Now, the main aim was to reduce the source code size. In python, there is a module called bisect which can be used to solve binary search problems. Check out the setter’s solution below which uses bisect_left to find the optimal K. This solution uses 297 characters. Feel free to share your approach, if it differs. Suggestions are always welcomed.

SOLUTIONS:

Setter's Solution
from bisect import bisect_left as b
import math
class t(dict):
    def __missing__(self,k):
        global f;return f(k)
def f(k):
    global A,d
    s=0
    for i in A:
        s+=math.ceil(i/k)
    return 1 if s<=d else 0
w=t()
i=lambda: [int(j)for j in input().split()]
n,d=i()
A=i()
print(-1 if d<n else b(w,1,1,max(A)))

Just a suggestion :
You should mention that user should output -1 in case it is not possible to find such value of k.