Difference between these 2 codes[and a few questions]

First of all here is the link to the problem:

(http://codeforces.com/contest/448/problem/D)

Now I'll post my last 2 submissions because I don't understand something about them:

[Accepted submission]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>


#define fl(n)    for(int i = 0; i < n; i++)

#define ll   long long
#define nl   endl
#define pb   push_back
#define mp   make_pair
#define PII  pair<int,int>

#define EPS  1e-9
#define INF  1e9


using namespace std;

ll binsearch(ll n, ll m, ll k){
ll low  = 1, high = n*m+1, mid;

while(low < high){
    mid = (low+high) >> 1;
    ll x = 0;
    for(ll i = 1; i <= n; i++){
        x+= min(m, (mid-1)/i);
    }
    //cout << low << " " << high << " " << mid << nl;
    //if(x == k) return mid;
    if(x >= k) high = mid;
    else low = mid+1;
}
return low;
}

int main()
{
    ll n, m, k;
    cin >> n >> m >> k;

    cout << (binsearch(n,m,k)-1);


    return 0;
}



[Wrong answer submission]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>


#define fl(n)    for(int i = 0; i < n; i++)

#define ll   long long
#define nl   endl
#define pb   push_back
#define mp   make_pair
#define PII  pair<int,int>

#define EPS  1e-9
#define INF  1e9


using namespace std;

ll binsearch(ll n, ll m, ll k){
ll low  = 1, high = n*m+1, mid;

while(low < high){
    mid = (low+high) >> 1;
    ll x = 0;
    for(ll i = 1; i <= n; i++){
        x+= min(m, (mid-1)/i);
    }
    //cout << low << " " << high << " " << mid << nl;
    if(x == k) return mid;
    if(x > k) high = mid;
    else low = mid+1;
}
return low;
}

int main()
{
    ll n, m, k;
    cin >> n >> m >> k;

    cout << (binsearch(n,m,k)-1);


    return 0;
}


Basically the only difference between them was 1 line of code which is:

~~~~~
if(x == k) return mid;
~~~~~

^ in the WA submission

I commented that line of code above and changed the high value condition in the binsearch to

~~~~~
if(x >= k) high = mid;
~~~~~

Instead of just x > k, and it got accepted. and I am wondering why that made a difference?

Edit: Also I tested a part where I removed the -1 from this equation:

~~~~~
x+= min(m, (mid-1)/i);
~~~~~
But I had to remove the -1 from the cout

~~~~~
cout << (binsearch(n,m,k)-1);
~~~~~

It got accepted aswell xD, I thought the equation could only work with a -1 since we look for elements smaller than k? or am I missing something?

Thanks in advance!
Last edited on
Instead of just x > k, and it got accepted. and I am wondering why that made a difference?


It should be pretty obvious that removing a return inside of a loop affects the code path and values returned from that function.

Why did you make a change to your code that you didn't understand?
Last edited on
Well infact I just wanna know why the >= conditions works over the > condition
Well infact I just wanna know why the >= conditions works over the > condition

That was not the only difference so looking at that in isolation is kind of silly.
Topic archived. No new replies allowed.