Weird Behavior of Binary Search.

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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

5 лет назад, # |

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

5 лет назад, # ^ |

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