booboo-and-upsolving-circuits

The hero of this story is a toddler named BooBoo. Inspired by the legendary competitive coder Gena, BooBoo has also started preparing to race to the top of the ranks.

BooBoo is going to practice N different problems in the exact given order over the next M days. For each problem, he writes down the amount of time q_i he will take to think and code the i^{th} problem (He is quite good at estimating!). Before starting on the problems, he took advice from experienced competitive programmers on his practice routine and almost all of them advised him to keep his daily load at the minimum possible and avoid over training.

Since BooBoo already has N problems to solve, he asks you to find the minimum time T such that training everyday for a time t_i ≤ T is sufficient to solve all the N problems in M days.

Note : Unlike in real world, you cannot think on a problem on one day and solve it on the other day. You need to do it on the very same day!

Input Format:

The first line contains two space separated integers N and M. The next line contains N space  separated integers denoting the time q_i required to solve the i^{th} problem.

Output Format:

The output consists of one integer, the minimum time T as described in the problem statement.

Constraints:

1 ≤ N ≤ 10^5
1 ≤ M ≤ N
1 ≤ q_i ≤ 10^{12}

SAMPLE INPUT
5 3
1 2 2 1 3

SAMPLE OUTPUT
3

Explanation

By setting T = 3, we can solve 1st two questions on day 1, next two on day 2 and 5th one on day 3.

Source: hackerearth | Difficulty: EASY
Tags: Sorting

Greedy algorithms


Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'

def reqday(arr , val , m):
	day = 1
	hrs = 0
	for i in range(len(arr)):
		if hrs + arr[i] > val:
			day += 1
			hrs = arr[i]
		else:
			hrs += arr[i]
	if day <= m:
		return 1
	else:
		return 0
	


n , m = [int(x) for x in input().split()]
time = [int(x) for x in input().split()]
l = max(time)
h = 1000000007**2
while l < h:
	mid  = (h + l) // 2
	p = reqday(time , mid , m)
	if p :
		h = mid
	else:
		l = mid + 1
print(l)
		


t,n = list(map(int,input().split()))
a = list(map(int,input().split()))
z = sum(a)
high = z
low = int(z/t)
while low<high:
	mid = int((low+high)/2)
	count = 1
	flag = 0
	num = mid
	for x in a:
		if x>num:
			if x>mid:
				low=mid+1
				flag = 1
				break
			else:
				num = mid-x
				count+=1
		else:
			num=num-x
	if flag==0:
		if count>n:
			low = mid+1
		else:
			high = mid
mid = int((low+high)/2)
print(mid)
			


#!/usr/bin/env python
# encoding: utf-8

def gao(x, a, n, m):
	i = 0
	times = 0
	while i < n:
		j = i
		y = x
		times += 1
		while j < n and a[j] <= y:
			y -= a[j]
			j += 1
		if j == i:
			return False
		i = j
	return True if m >= times else False

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))

lb, ub = 0, sum(a)
while ub - lb > 1:
	mid = (lb + ub) / 2
	if gao(mid, a, n, m) == True:
		ub = mid
	else:
		lb = mid

print(ub)


def get_req_days(q, rate):
	r = rate
	days = 1

	for q_i in q:
		if q_i > rate:
			return 100000

		if q_i > r:
			r = rate
			days += 1
		r -= q_i

	return days

N,M = [int(x) for x in input().split()]
q = [int(x) for x in input().split()]

best_r = None

while best_r==None:
	min_r = 1;
	max_r = sum(q)
	while min_r<=max_r:
		mid_r = (min_r+max_r)//2;
		days = get_req_days(q, mid_r)

		if days==M:
			best_r = mid_r
			max_r = mid_r-1
		elif days>M:
			min_r = mid_r+1
		else:
			max_r = mid_r-1
	M -= 1

print(best_r)


from math import ceil
n,m=list(map(int,input().split()))
lis=list(map(int,input().split()))
l=1
r=10**18
while l<r:
	mid=(l+r)/2
	days=0
	cur=0
	worked=0
	while cur<n and days<m:
		worked=0
		while cur<n and worked<mid:
			worked+=lis[cur]
			cur+=1
		if worked>mid:
			cur-=1
		days+=1
	if cur==n and days<=m:
		r=mid
	else:
		l=mid+1
print(r)


n,m = list(map(int,input().split()))
Q = list(map(int,input().split()))

def is_solvable(n,m,Q,t):
	i = 0
	tt = t
	while i < n:
		if Q[i] > tt:
			return False
		if t - Q[i] < 0:
			t = tt
			m -= 1
		t -= Q[i]
		i += 1
		if m <= 0:
			return False
	return m > 0

def bin_search():
	st = 1
	end = 10**17
	prev_mid = 0
	while st < end:
		mid = (st+end)/2
		if is_solvable(n,m,Q,mid):
			prev_mid = mid
			end = mid - 1
		else:
			st = mid + 1
	if is_solvable(n,m,Q,st):
		return st
	else:
		return prev_mid

print(bin_search())


def possible(threshold,v,M):
	count = 0
	sum = 0
	for ele in v:
		if ele > threshold:
			return False
		if sum+ele <= threshold:
			sum += ele
		else:
			count = count + 1
			sum = ele
	count = count + 1
	return count <= M

N,M = [ int(_) for _ in input().split() ]
t = [ int(_) for _ in input().split() ]
total = sum(t)

minimum = None

while minimum is None:
	low = 0
	high = total
	while low <= high:
		mid = ( low + high )/2

		if possible(mid,t,M):
			minimum = mid
			high = mid - 1
		else:
			low = mid + 1
	M = M - 1

print(minimum)


def get_req_days(q, rate):
	r = rate
	days = 1

	for q_i in q:
		if q_i > rate:
			return 100000

		if q_i > r:
			r = rate
			days += 1
		r -= q_i

	return days

N,M = [int(x) for x in input().split()]
q = [int(x) for x in input().split()]

best_r = None

while best_r==None:
	min_r = 1;
	max_r = sum(q)
	while min_r<=max_r:
		mid_r = (min_r+max_r)//2;
		days = get_req_days(q, mid_r)

		if days==M:
			best_r = mid_r
			max_r = mid_r-1
		elif days>M:
			min_r = mid_r+1
		else:
			max_r = mid_r-1
	M -= 1

print(best_r)


def possible(threshold,v,M):
	count = 0
	sum = 0
	for ele in v:
		if ele > threshold:
			return False
		if sum+ele <= threshold:
			sum += ele
		else:
			count = count + 1
			sum = ele
	count = count + 1
	return count <= M

N,M = [ int(_) for _ in input().split() ]
t = [ int(_) for _ in input().split() ]
total = sum(t)

minimum = None
count = 0

while minimum is None and count != 10:
	low = 0
	high = total
	while high - low > 1:
		mid = ( low + high )/2

		if possible(mid,t,M):
			minimum = mid
			high = mid
		else:
			low = mid
	M = M - 1
	count += 1


if count == 10:
	low = 0
	high = total
	minimum = total

	while high - low > 1:
		mid = ( low + high )/2

		if possible(mid,t,M):
			minimum = mid
			high = mid
		else:
			low = mid
print(minimum)


#
import fileinput
import numpy as np

def tenta(line,n,m,t):
	i=0
	vtemp=0
	c=0

	while i<n:
		vtemp+=line[i]
		if vtemp > t:
			vtemp=0
			c+=1
			if c>=m:
				return 0
		else:
			i+=1
	return 1

i=0
for line in fileinput.input():
	if i == 0:
		n=int(line.split()[0])
		m=int(line.split()[1])
	else:


		lin=np.fromstring(line,sep=" ",dtype=int)
		a=np.amax(lin)
		ini=int(a)
		total=np.sum(lin)
		p=int(total/m)
		if ini < p:
			ini = p

		fim = a+p+2

		b=tenta(lin,n,m,ini)
		
		if b == 1:
			print(ini)

		else:        
			while True:
					part=int((ini+fim)/2)
					
					new=tenta(lin,n,m,part)
					
					if new == 1:
						fim = part
					elif new == 0:
						ini = part
					if fim-ini == 1:
						break
			print(fim)
	i+=1
		
	




#!/usr/bin/env python

def days(t):
	res = 0
	cur = 0
	for i in range(n):
		if cur + q[i] > t:
			res += 1
			cur = 0
		cur += q[i]
	if cur > 0:
		res += 1
	return res


n, m = list(map(int, input().split()))
q = list(map(int, input().split()))

l = max(q)
r = int(1e18)
while r - l > 1:
	mid = (l + r) / 2
	if days(mid) > m:
		l = mid + 1
	else:
		r = mid

while days(l) > m:
	l += 1

print(l)


def get_req_days(q, rate):
	r = rate
	days = 1

	for q_i in q:
		if q_i > rate:
			return 100000

		if q_i > r:
			r = rate
			days += 1
		r -= q_i

	return days

N,M = [int(x) for x in input().split()]
q = [int(x) for x in input().split()]

best_r = None

while best_r==None:
	min_r = 1;
	max_r = sum(q)*2
	while min_r<=max_r:
		mid_r = (min_r+max_r)//2;
		days = get_req_days(q, mid_r)

		if days==M:
			best_r = mid_r
			max_r = mid_r-1
		elif days>M:
			min_r = mid_r+1
		else:
			max_r = mid_r-1
	M -= 1

print(best_r)


def possible(threshold,v,M):
	count = 0
	sum = 0
	for ele in v:
		if ele > threshold:
			return False
		if sum+ele <= threshold:
			sum += ele
		else:
			count = count + 1
			sum = ele
	count = count + 1
	return count <= M

N,M = [ int(_) for _ in input().split() ]
t = [ int(_) for _ in input().split() ]
total = sum(t)

minimum = total

low = 0
high = total
while low <= high:
	mid = ( low + high )/2
	if possible(mid,t,M):
		minimum = mid
		high = mid - 1
	else:
		low = mid + 1


print(minimum)


def check(val):
	cnt, curr = 1, 0
	
	for elem in board:
		if(curr + elem > val):
			cnt += 1
			curr = elem

		else:
			curr += elem

	return cnt <= M


def main():
	global board, M
	
	N, M = list(map(int, input().split()))
	board = list(map(int, input().split()))
	
	Tbeg, Tend = max(board), int(1e17 + 100)

	while(Tbeg < Tend):
		Tmid = (Tbeg + Tend) >> 1

		if(check(Tmid)):
			Tend = Tmid
		else:
			Tbeg = Tmid + 1

	print(Tend)

##########################################
##########################################
##########################################
if(__name__ == "__main__"):
	main()