CodeForces Binary Search EDU -Children Holiday

general
1

Problem link:
Children Holiday

#include <bits/stdc++.h>
using namespace std;
long long countInflated(vector<int> &eachb, vector<int> &streak, vector<int> &rest, int time, vector<int> &work, int req) {
	int n = eachb.size();
	int total = 0, curr = 0, maxc = 0;
	// cout << "ind report " << " ";
	for (int i = 0; i < n; i++) {
		maxc = (eachb[i] * streak[i]) + rest[i];
		curr = (time / maxc) * streak[i];
		total += curr;
		// cout << i << " " << "work " << curr << "; ";
		work[i] = curr;
	}
	for (int i = 0; i < n; i++) {
		maxc = (eachb[i] * streak[i]) + rest[i];
		if (total < req) {
			work[i] += min((time % maxc) / eachb[i], streak[i]);
			curr += min((time % maxc) / eachb[i], streak[i]);
			total += min((time % maxc) / eachb[i], streak[i]);
		} else {
			break;
		}

	}

	// cout << "\n";
	return total;

}
int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int m, n, slowestworkertime = 0;
	cin >> m >> n;
	vector<int> eachb(n, 0);
	/**
	 * Max ballons can be inflated at
	 * each session
	 */
	vector<int> sessionb(n, 0);
	vector<int> relaxt(n, 0);
	vector<int> record(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> eachb[i] >> sessionb[i] >> relaxt[i];
		slowestworkertime = max(slowestworkertime, eachb[i]);
	}
	int low = 1, high = slowestworkertime * m, mid = 0;
	long long inflated = 0, ans = 0;
	vector<int> samp(n, 0);
	while (low <= high) {
		mid = low + (high - low) / 2;
		inflated = countInflated(eachb, sessionb, relaxt, mid, samp, m);
		// cout << "Report " << mid << " time " << inflated << "\n";
		if (inflated >= m) {
			ans = mid;
			record = samp;
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	}
	cout << ans << "\n";
	for (int i = 0; i < n; i++) {
		cout << record[i] << " ";
	}
	cout << "\n";
	return 0;
}

Can anyone please explain what is the wrong with the approach.Struck with the problem.

1 Like
2

You didn’t handle the case where m=0;
Also, the searching range is not necessarily [1 to slowestWorkerTime*m],
because the slowestWorker is also allowed to take frequent rest XD;
Furthermore, there is a problem in the following code segment,

if (total < req) {
	work[i] += min((time % maxc) / eachb[i], streak[i]);
	curr += min((time % maxc) / eachb[i], streak[i]);
	total += min((time % maxc) / eachb[i], streak[i]);
}

it should be,

if (total < req) {
        int x=min(req-total,min(streak[i],(time%maxc)/eachb[i]));
	work[i] += x;
	// curr += min((time % maxc) / eachb[i], streak[i]);
	total += x;
}

The corrected version of your code is given below: (Accepted Solution)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long countInflated(vector<ll> &eachb, vector<ll> &streak, vector<ll> &rest, ll time, vector<ll> &work, ll req) {
    ll n = eachb.size();
    ll total = 0, curr = 0, maxc = 0;
    for (ll i = 0; i < n; i++) {
        maxc = (eachb[i] * streak[i]) + rest[i];
        curr = (time / maxc) * streak[i];
        total += curr;
        work[i] = curr;
    }
    for (ll i = 0; i < n; i++) {
        maxc = (eachb[i] * streak[i]) + rest[i];
        if (total < req) {
            ll x=min(req-total,min(streak[i],(time%maxc)/eachb[i]));
            work[i] += x;
            total += x;
        } else {
            break;
        }
    }
    return total;
}
int main() {
    ll m, n;
    cin >> m >> n;
    vector<ll> eachb(n, 0);
    /**
     * Max ballons can be inflated at
     * each session
     */
    vector<ll> sessionb(n, 0);
    vector<ll> relaxt(n, 0);
    vector<ll> record(n, 0);
    for (ll i = 0; i < n; i++) {
        cin >> eachb[i] >> sessionb[i] >> relaxt[i];
    }
    if(m==0){
        cout<<0<<endl;
        for(ll i=0; i<n; i++)
            cout<<"0 ";
        cout<<endl;
        return 0;
    }
    ll low = 1, high = 1e9, mid = 0;
    long long inflated = 0, ans = 0;
    vector<ll> samp(n, 0);
    while (low <= high) {
        mid = low + (high - low) / 2;
        inflated = countInflated(eachb, sessionb, relaxt, mid, samp, m);
            ans = mid;
            record = samp;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    cout << ans << "\n";
    for (ll i = 0; i < n; i++) {
        cout << record[i] << " ";
    }
    cout << "\n";
    return 0;
}
2 Likes