Problem 0. Book Cartons Editorial [Binary Search Greedy]
Problem Statement: Given m cartons and each containing some bi books.We have to assign them to k students such that the student who got the maximum books that maximum value is the minimum possible in all possible valid allocation of books. Maybe this statement is confusing at first glance. Let me go through an example.
Ex. 5 cartons, 3 students. Cartons : {100, 200, 300, 400, 500}
Possible Allocations :
Allocation : {100}, {200}, {300, 400, 500}
Maximum books to a single student : 300 + 400 + 500 = 1200
Maybe we can do somewhat better in lowering the maximum.
{100, 200}, {300, 400}, {500}.
Maximum books to a single student : 300 + 400 = 700
Can we bring max to some more smaller value ?
{100, 200, 300}, {400}, {500}
Max : 100 + 200 + 300 = 600
So all above are valid allocation in the sense we are allocating books to all three students. But the best where the maximum books to a student is minimum of all is (3) one.
So How to solve this problem ? Should we generate some solutions ? Or should we check for a solution Like Whether is it possible to do some allocation considering some upper bound on the maximum value of books to a single student ?
Generating a solution in this type of problem is not optimal because If we do so we have to check for each possible solution and then select the minimum and in most cases it will lead to TLE (Time Limit Exceed) because the search space is huge.
Where on the other hand we can check for a particular allocation whether it is valid or not, but still it will take O(n) to check for each allocation validity. So should we check for each possible allocation ? No, Because then it will no bad then generating all possible solutions.
HereBinary Search comes into the picture. We know if our function is increasing (or decreasing) we can do binary search to find some particular value. Similarly the way we search in sorted array. Here instead of searching a value we will use binary search to find our solution.
Let me go through little about how we will apply binary search here. And also what increasing function ( not need to be strictly increasing) has to do with this If you don’t know.
See the above diagram. How I know function here is increasing ? Check for values say on some value say x1 as a upper bound on no. of books for a single student we need some p students to allocate all cartons. Then ask what would happen if decrease the x1 say x2 < x1. Then how many students do you need on x2 more or less.
This is how we will binary search for the value x. Value x will act as an upper bound for allocation (mean we will try to allocate each student at most x books). And we will check for this value whether this is a possible solution. ( checking will run in O(n) We will see later).
How to select value x ? . We will use some lower limit (left) and upper limit(right) of search space for x.
Now the way binary search works we will first check on mid = (left + right) / 2 . And then we will check for our allocation using the checking algorithm whether it is feasible or not. Say if the allocation requires more than k students assuming each student can’t hold any more than “x = mid” books. Then we know our search space reduces and we need to check value in a range because in this case even if we scan for a smaller value then current value = mid ( as a upper bound) we still end with having allocation which requires more than k students ( Why we can say this because the function is increasing i.e if for any x1, x2 if x1 <= x2 then prediction for f(x) is also simple f(x1) <= f(x2)). So no need to search in that space and we reduce our search space to half and now scan only in the range where x > mid && x < right most bound. (i.e l = mid + 1)
And if this is the allocation with the exact k student then we will try to minimize it more by lowering upper bound.( r = mid - 1).
Here is the checking function step decreasing function. O(n)
What about lower limit(left) and upper limit (initial).
In the worst case if there is only one student then all cartons belong to that so we Enter cod have allocate no more than the sum of all books in all cartons so that is the upper most limit ( at initial). And what about left, Suppose if the same no. of students as cartons then in that case the minimum books cartons is the minimum allocation that a student must get so the lower limit for search “x” is min( of all books in cartons). We can also start with lower limit = 0, It doesn’t matter.
Checking part:
bool check(int mid) {
int cnt = 1, temp = 0; // cnt indicate no. of student use in the allocation for some mid as upper_bound on no. of books per studnet
for(int i = 0; i < n; ++i) {
if(temp + a[i] > mid) { // If adding a[i] increase the mid then we will start allocating next student.
cnt++; // Thus we increase no. of student use.
if(cnt > k) // If this exceed k (max student we have) return 0 immediately.
return 0;
temp = a[i];
}
else
temp += a[i];
}
return 1; // If every thing above passes good then return 1.
}
Binary Search part:
int l = mn, r = mx;
// mn is minimum of all, mx is the sum of all books in all cartons.
int ans = r;
while(l <= r) {
int mid = (l + r) / 2; // Careful this may lead to overflown so better to use l + (r - l) / 2, or use long long int (C++)
if(check(mid)) { // Check for mid, if it is possible then try to minimize this upper_bound on no. of books each student.
ans = mid; // mark this as the answer till now, since it is passing checking.
r = mid - 1; // reduce range to lower the upper_bound on no. of books . So in order to reduce maximum books to single
}
else { // else if it is not possible, mean the mid require more than k student then increase the upper bound and thus l = mid + 1
l = mid + 1;
}
}
#include <bits/stdc++.h>
using namespace std;
#define hey(x) cerr << #x << " is " << x << "\n";
#define int long long int
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int> >
#define vpi vector<pair<int, int> >
#define vvpi vector<vector<pair<int, int> > >
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pii pair<int, int>
#define pb push_back
#define SZ(x) (int)(x).size()
#define F first
#define S second
#define PI 3.1415926535897932384626
#define out cout << fixed << setprecision(12)
#define fast ios::sync_with_stdio(false); cin.tie(0);
#define inf 1e12
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const double pi = acos(-1);
vi a;
int n, k;
bool check(int mid) {
int cnt = 1, temp = 0;
for(int i = 0; i < n; ++i) {
if(temp + a[i] > mid) {
cnt++;
if(cnt > k)
return 0;
temp = a[i];
}
else
temp += a[i];
}
return 1;
}
void go() {
cin >> n >> k;
a = vi(n);
int mn = inf, mx = 0;
for(int i = 0; i < n; ++i){
cin >> a[i];
mn = min(mn, a[i]);
mx += a[i];
}
int l = mn, r = mx;
int ans = r;
while(l <= r) {
int mid = (l + r) / 2;
if(check(mid)) {
ans = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
vi store;
int temp = 0;
int cnt = 0;
for(int i = n - 1; i >= 0; --i) {
if(temp + a[i] > ans) {
store.pb(-1); // -1 used to know the pos of '/' in solution
cnt++;
temp = a[i];
store.pb(a[i]);
}
else {
store.pb(a[i]);
temp += a[i];
}
}
reverse(all(store));
if(cnt > k - 1) {
for(int i = SZ(store) - 1; i >= 0; --i) {
if(store[i] == -1) {
store[i] = 0;
cnt--;
if(cnt == k - 1)
break;
}
}
}
for(int i = 0; i < SZ(store); ++i) {
if(store[i]){
if(store[i] != -1 && cnt < k - 1) {
if(i + 1 < SZ(store) && store[i + 1] != -1) {
cout << store[i] << " / ";
cnt++;
}
else {
cout << store[i] << ' ';
}
}
else if(store[i] != -1) {
cout << store[i] << " ";
}
else if(i + 1 != SZ(store)) {
cout << "/ ";
}
}
}
cout << '\n';
}
int32_t main(){
ios::sync_with_stdio(false);
cin.tie(0);
go();
return 0;
}