Sugar Rush - EDITORIAL:
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, so print -1.
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)))