Help with CSES problem Factory Machines

general
, ,
1

Link to the problem: CSES - Factory Machines
My Approach: If it is possible to make m products in d days then it is also possible to make m products in d+1 days, and if it is not possible to make m products in d days then it is also not possible to make m products in d-1 days. Using this property we can apply binary search to find the smallest number of days in which we can make the given number of products. As for the upper bound, the worst case will be when I have to make 10^9 products and I have only one machine which takes 10^9 days to make one product, so the total time taken in this case will be 10^18.

Following is my code:

#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;
const int mxn = 2e5 + 5;
const ll inf = (1LL<<62);

int n; ll t, arr[mxn];

bool check(ll d)
{
    ll cnt = 0;
    for(int i=0; i<n; i++)
        cnt += (d/arr[i]);
    if(cnt < t) return false;
    return true;
}

ll findDays()
{
    ll low = 1, high = 1e18+5, days = 0;
    while(low <= high)
    {
        ll mid = low+(high-low)/2;
        if(check(mid))
        {
            days = mid;
            high = mid-1;
        }
        else
            low = mid+1;
    }
    return days;
}

int main()
{
    FASTIO
    cin >> n >> t;
    for(int i=0; i<n; i++) cin >> arr[i];
    cout << findDays() << "\n";
    return 0;
}

The above code works for all the test cases except for two, where it gives a WA.
Following is one of them:

25 1000000000
1000000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

My code gives the answer as 768614336414205720 whereas the correct answer is 41666667.

Can anybody please point out the error in my code which leads to such an answer?

2

The check function overflows the boundaries for long long int.24*5*1e17 is too big to store in long long int.

2 Likes
3

Thanks for pointing that out :smile:. Any workarounds?

4

Adjust the high limit to be more precise. Take the minimum element in the time array, multiply it with t. Set this as high initially.

This does pass the test cases, but looking at the constraints, 1e18 is possibly reached. Instead, just change your cnt variable to a double, and it should AC.

3 Likes
6

It worked :smile:. But what is the reason behind this? Is it because the machines with smaller production time will ultimately be able to achieve the target at most in those many days if we simply ignore the other machines?

7

Yup. But still, the machine with the lowest time can possibly take 1e9 time, and there can be 1e9 tasks, so it is possible to reach 1e18 as the initial high value.

But maybe then cnt won’t reach a very high value because of the small values added at each step? I’d just skip the thought, and recommend just changing cnt to a double.

1 Like
8

Or you could just return the function the first time cnt crosses t…

1 Like
9

That might work as well. :smile: Thanks.

10

Just return true when c is greater than t for first time.