Weird Behavior of Binary Search.

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3611
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	Radewoosh	3415
8	Um_nik	3376
9	maroonrk	3361
10	XVIII	3345

№	Пользователь	Вклад
1	Qingyu	162
2	adamant	148
3	Um_nik	146
4	Dominater069	143
5	errorgorn	141
6	cry	138
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
10	soullless	133

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

6 лет назад, скрыть # |

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

6 лет назад, скрыть # ^ |

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