Why Brute Force Worked But Binary search doesn't?

help
,
1

I was solving the question from recent contest Starters 13

I tried it to do it using Binary Search but got WA while brute force worked can any one tell me why this happened ??

Here is my code

bool is ( int P , int a , int ar , int mid , int midp ) {
    int tr = mid * ( ar * a + midp ) ;
    if ( tr > P ) return 0 ;
    return 1 ;
}

void Go () {    
    int P = 0 , a = 0 , b = 0 , c = 0 , x = 0 , y = 0 ;
    cin >> P >> a >> b >> c >> x >> y ;

    int bb = 0 , cc = 0 ;
    int low , high ;

    low = 0 , high = P ;
    while ( low <= high ) {
        int mid = low + ( high - low ) / 2 ;
        if ( is(P,a,x,mid,b) ) {
            bb = mid ;
            low = mid + 1 ;
        } else {
            high = mid - 1 ;
        }
    }

    low = 0 , high = P ;
    while ( low <= high ) {
        int mid = low + ( high - low ) / 2 ;
        if ( is(P,a,y,mid,c) ) {
            cc = mid ;
            low = mid + 1 ;
        } else {
            high = mid - 1 ;
        }
    }
    cout << max ( bb , cc ) << '\n' ;
}
2

i think greedy is most optimal solution for this que.
i also thought of using binary search but found O(1) solution!!

1 Like
3

yeah my O(1) solution worked but I want know why binary search doesn’t worked
? As I know Binary Search also works greedily .

4

hmm ok!

5

Binary search works when the function is monotonic so if you have correctly implemented binary search then only reason of getting wrong answer must be that this function is not monotonic.

Read article for binary search. Here it’s mentioned about that property:

6

You’ve missed out most of your code so it’s hard to tell where the error lies, but this:

looks like very overflow-ish.

It’s pretty easy to find out for (almost) sure.

2 Likes
7

Thanks for pointing out bro .
You was right it gave me Runtime error due to overflow when I added
that line .

Can you tell more pragma directives which are useful in CP .

1 Like
8

It was monotonic function .