Editorial - TFTWN

general
, , , ,
1

Problem Link

Practice
Contest

Author: Vaibhav Chaurasia
Editorialist: Rudransh Tripathi

Difficulty

Cakewalk

Prerequisites

Binary Search

Problem

Aanchal likes to visit different restaurants and try the dishes they offer. One day she decides to visit this restaurant called The Food Town. There are N chefs working there and they take specific amount of time T to cook any of the dishes. Aanchal knows the time T_i (time taken by each chef to prepare a dish). Chefs can work simultaneously on different tables, and she can make any chef/chefs work for her to prepare required Q dishes. She notes the minimum time required to make all Q dishes. But she is a moody girl and does not like 3 or any of its multiples and considers it as bad timing. If the minimum time comes out to be bad, she rated her visit as BAD EXPERIENCE otherwise GOOD EXPERIENCE.

Quick Explanation

Just use binary search.

Explanation

You are given N chefs and asked the minimum time these chefs require to prepare Q dishes such that the i chef creates a dish in T{_i} time.
We check all the possible outcomes between 0 and 10^{18} using binary search.
For some value solution we use binary search, we are left with the task of checking whether we can create Q dishes in solution time. To do this, observe that it’s optimal for every chef to work simultaneously. Then, in solution time, chef i can create \lfloor{\frac{solution}{Ti}}\rfloor dishes.
Overall, the N chefs can prepare \sum_{i=1}^{N} \lfloor{\frac{solution}{Ti}}\rfloor dishes. If this solution \geq Q, then solution is valid. Finally, check divisibility by 3.

Solution

C++ Solution 
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {
	
	ll n;
	ll q;
	cin >> n >> q;
	vector<ll> vec(n);
	for(ll i=0;i<n;i++)
	{
	    cin >> vec[i];
	}
	ll lo=0,hi=1e18,ans=0;
	while(lo <= hi)
	{
	    ll mid = (lo + hi)/2;
	    ll temp=0;
	    for(ll i=0;i<n;i++)
	    {
	        temp+=(mid/vec[i]);
	        if(temp>=q)
	        {
	            break;
	        }
	    }
	    if(temp >=q)
	    {
	        ans=mid;
	        hi=mid-1;
	    }
	    else
	    {
	        lo=mid+1;
	    }
	}
	if(ans%3==0)
	{
	    cout << "BAD EXPERIENCE"<< "\n";
	}
	else
	{
	    cout << "GOOD EXPERIENCE" << "\n";
	}
	
	
	return 0;
}
Python Solution 
#Author: rt24
from math import floor
from sys import stdin, stdout 

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

left = 1
right = int(1e18)

while left < right:
    mid = (left + right) // 2
    #print(str(mid) + " " + str(left) + " " + str(right))
    ans = 0
    for i in range (0, n) :
        ans += min(mid // ar[i], 1e9)

    if ans >= q:
        right = mid
    else:
        left = mid + 1

#stdout.write(str(left))
if left % 3 == 0:
    print("BAD EXPERIENCE")
else:
    print("GOOD EXPERIENCE")
4 Likes