Need Help in EDU Binary Search Step2

#	User	Rating
1	ecnerwala	3650
2	Benq	3582
3	Geothermal	3570
3	orzdevinwang	3570
5	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3532
8	Radewoosh	3522
9	Um_nik	3483
10	jiangly	3468

#	User	Contrib.
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	157
7	-is-this-fft-	151
8	SecondThread	150
9	orz	146
10	pajenegod	145

Can someone help me with Step-2 C: Very Easy Task

Problem Link : https://codeforces.com/edu/course/2/lesson/6/2/practice/contest/283932/problem/C

My Approach: if the task can be done in T time, then 1(good) else 0 (bad). So, making 1 copy of the original document will take min(x,y) time, and then both copy machines can simultaneously work.

we need to check whether n copies can be made in T time or not, if I am updating T1 = T-min(x,y) and then checking that can I make n-1 copies in T1 time. Then find the first occurrence of 1 using binary search. It is throwing me an error "Wrong Answer on test case 5"

Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define nl "\n";

bool check(int n, int x, int y, ll mid)
{
    mid = mid - min(x, y);
    n = n - 1;
    ll res = (mid / x) + (mid / y);
    return res>=n; 
}

void solve()
{
    int n, x, y;
    cin >> n >> x >> y;
    ll l =0;
    ll r =1e12; 
    int ans =-1;  
    while(l<=r)
    {
        ll mid = (l+r)/2; 
        if(check(n,x,y,mid))
        {
            ans = mid; 
            r = mid-1; 
        }
        else
        {
            l = mid+1; 
        }
    }
    cout<<ans<<nl; 
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    cout << fixed << setprecision(20);
    ll t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

Actual Approach : we need to check whether n-1 copies can be made in T time or not. Then, by using binary search find the first occurrence of 1 as it will be the least time to make n-1 copies, and then adding min(x,y) as it will be the time to make the copy of original.

AC Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define nl "\n";

bool check(int n, int x, int y, ll mid)
{
    ll res = (mid / x) + (mid / y);
    // cout<<res<<nl; 
    return res>=n-1; 
}

void solve()
{
    int n, x, y;
    cin >> n >> x >> y;
    ll l =0;
    ll r =1e10; 
    ll ans =-1;  
    while(l<=r)
    {
        ll mid = (l+r)/2; 
        // cout<<"mid : "<<mid<<nl; 
        if(check(n,x,y,mid))
        {
            ans = mid; 
            r = mid-1; 
        }
        else
        {
            l = mid+1; 
        }
    }
    cout<<ans+ min(x,y)<<nl; 
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    cout << fixed << setprecision(20);
    ll t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

I dont know, where am I making mistake, both logics seems similar to me.

Comments (4)

Show archived | Write comment?

themlotreem2008

7 months ago, # |

Well, I don't really read about your second AC code but in the first code I assume that you need to add

if (mid < min(x,y)) return false;

I also have the same issue and when I fixed it just got accepted

→ Reply

Habaxl

6 months ago, # ^ |

can you explain why?

hujo

3 months ago, # ^ |

← Rev. 3 →

It seems like the checking function $$$ 1 + \lfloor \frac{{t - \mathrm{min}}}{x} \rfloor + \lfloor \frac{{t - \mathrm{min}}}{y} \rfloor \geq n $$$ should work properly since negative numbers are still <n but if $$$t=min$$$, you will get 1 even though no copies can be made. Then again, I can't see TC5 so take it with grain of salt.

Ex: $$$1\, 5\, 7$$$

if $$$t=5$$$, $$$1 + (5 - 5)/5 + (5 - 5)/7 >=1$$$ so the function returns true

anshkush92

5 weeks ago, # ^ |

It is specifically for the case n = 1

Because you see that when t < min(x, y), to find the number of copies made, we have to do t = t - min(x, y) (Because the first copy was made at min(x,y))

When t < min(x, y) in that case t < 0 , so t / x + t / y can come 0 if t < x and t < y and in that we will get answer at t < min(x,y) even though our copy wasn't printed out yet

You can take any example in the form of 1 x y and you will get where you are getting wrong

Kanao's blog