Weird Behavior of Binary Search.

№	Пользователь	Рейтинг
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

№	Пользователь	Вклад
1	maomao90	174
2	awoo	165
3	adamant	161
4	TheScrasse	160
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	orz	146
9	SecondThread	145
9	pajenegod	145

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;
}

Комментарии (5)

Показать архивные | Написать комментарий?

manik.jain

4 года назад, # |

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

→ Ответить

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

4 года назад, # ^ |

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