Weird Behavior of Binary Search.

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

I implemented my solution using Binary Search in this Problem A: Deadline. Issue is I'm Facing that,by changing the value of high from 1e18 to n-1, my solution which was giving wrong answer now being accepted. To be on the safe side, I kept high=1e18, but it's giving wrong answer. Any Help on this would be really appreaciated. Am I missing something conceptually on knowledge of Binary Search?

Wrong Answer due to high=1e18

Code LINK:

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli mod=1e9+7;
#define F first
#define S second
#define _READ freopen("input.txt","r", stdin);
#define pb push_back
#define _FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int main()
{
    #ifndef ONLINE_JUDGE
    _READ
    #endif
    _FAST
    lli t;
    cin>>t;
    while(t--)
    {
        lli n,d;
        cin>>n>>d;
        lli low=1,high=1e18,ans=-1;
        while(low<=high)
        {
            lli x=low+(high-low)/2;
            lli temp=x+(d+x)/(x+1);
            //cout<<x<<" "<<temp<<"\n";
            if(temp<=n)
            {
                ans=x;
                break;
            }
            else
            {
                high=x-1;
            }
        }
        if(ans!=-1 || n>=d)
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
    return 0;
}

Accepted after high=n-1

Code LINK:

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli mod=1e9+7;
#define F first
#define S second
#define _READ freopen("input.txt","r", stdin);
#define pb push_back
#define _FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int main()
{
    #ifndef ONLINE_JUDGE
    _READ
    #endif
    _FAST
    lli t;
    cin>>t;
    while(t--)
    {
        lli n,d;
        cin>>n>>d;
        lli low=1,high=n-1,ans=-1;
        while(low<=high)
        {
            lli x=low+(high-low)/2;
            lli temp=x+(d+x)/(x+1);
            //cout<<x<<" "<<temp<<"\n";
            if(temp<=n)
            {
                ans=x;
                break;
            }
            else
            {
                high=x-1;
            }
        }
        if(ans!=-1 || n>=d)
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
    return 0;
}

Comments (5)

Show archived | Write comment?

manik.jain

5 years ago, # |

try high=1e18+2 and see if that still gives you WA

→ Reply

98596

← Rev. 2 →

I believe both of your binary searches is wrong, consider the test case 1 5 9, the answer should be Yes.(two days of optimization). However, your program gives No. This is because when in your binary search low = 1, high = 2, then low + (high - low) / 2 = 1. You skip the possibility of using two days for optimization. For the high = n - 1 solution, it has the same problem but I believe it is coincidently correct under the settings of this particular problem. (or it is incorrect I am not sure)

davidberard

5 years ago, # ^ |

I agree, the function x+(x+d)/(x+1) is not monotonic so binary search should not be expected to work.

Sumanto

okay thanks, but any other way to solve the problem using binary search as the problem has tag of binary search.

The function f(x) = x+(x+d)/(x+1) is concave upwards. It means that there are two intervals, for the first interval f(x) > f(x + 1), and for the second interval f(x) < f(x + 1). So you may binary search for the first x that satisfy f(x) < f(x + 1)

Sumanto's blog