PROBLEM LINK
Contest Problem - Diwali and Chocolate
Practice
Author: Utkarsh Goel
Tester: Arjun Kathail
Editorialist: Arjun Kathail
DIFFICULTY:
MEDIUM
PREREQUISITES:
Binary Search
PROBLEM:
N chocolate bars of lengths C1, C2,...Cn. At most K cuts can be made to divide the chocolate bars into multiple pieces. Consider the largest piece that you get after making these K cuts. Find the smallest possible length of this largest piece.
When you cut a chocolate bar of length L whose distance from an end is t (0<t<L), it becomes two chocolate bars of lengths t and L − t.
EXPLANATION:
Consider the problem whether the answer is less than or equal to X. This problem can be rephrased as whether all the chocolate bars can be cut down to the length less than or equal to X within at most K cuts. In order to cut a log of initial length Ci into those of length less than or equal to X, at least \left \lceil{\dfrac{Ci}{X}} \right \rceil -1 cuts are required. If the sum of them does not exceed K, then the answer is Yes, otherwise the answer is No.
It is sufficient to find the minimum integer X such that the answer to the question “is the answer less than or equal to X?” is Yes. Binary Search between 0 and max(C) can be applied to test different values of X. The total computation time is O(Nlog(max(C))).
SOLUTIONS:
Setter's Solution
// Setter Solution - Utkarsh Goel
#include <bits/stdc++.h>
#define ll long long
using namespace std;
//Solution using Binary Search
void solve()
{
ll n, k;
cin >> n >> k;
vector<ll> a(n);
for (ll i = 0; i < n; ++i)
{
cin >> a[i];
}
ll low = 1, high = *max_element(a.begin(), a.end());
while (low < high)
{
ll mid = (low + high) / 2;
ll count = 0;
for (ll i = 0; i < n; ++i)
{
//cuts per chocolate bar considering that max size allowed is count.
if (a[i] % mid == 0)
{
count += a[i] / mid - 1;
}
else
{
count += a[i] / mid;
}
}
if (count <= k)
high = mid;
else
low = mid + 1;
}
cout << low << "\n";
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
#ifndef ONLINE_JUDGE
freopen("input", "r", stdin);
freopen("output", "w", stdout);
#endif
ll t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
Tester's Solution
#Tester Solution- Arjun Kathail
n,k=map(int,input().split())
c=list(map(int,input().split()))
low=0
high=max(c)
#Binary Search
while (low+1)<high:
size=(low+high)//2
total_cuts=0
for i in range(n):
#cuts per chocolate bar considering that max size allowed is size.
total_cuts+=(c[i]-1)/size
if(total_cuts<=k):
high=size
else:
low=size
print(high)
Editorialist's Solution
#Editorialist Solution- Arjun Kathail
n,k=map(int,input().split())
c=list(map(int,input().split()))
low=0
high=max(c)
#Binary Search
while (low+1)<high:
size=(low+high)//2
total_cuts=0
for i in range(n):
#cuts per chocolate bar considering that max size allowed is size.
total_cuts+=(c[i]-1)/size
if(total_cuts<=k):
high=size
else:
low=size
print(high)