Be Like Hasib

Discussions Toph Problems
1

Hasib, the famous programmer, uses a little game when he teaches Binary Search to his students. He r…

Click here to read the complete problem statement.

If you need help solving this problem, mention your approach and ask specific questions. Please avoid sharing your code and asking the Community to figure out “what’s wrong”.

2

https://ideone.com/32Buck this code(Python) getting CPU limit, but same solution getting accepted while submit using C++. How can i reduce cpu usage?

3

@mhiceiuk Which Python are you using? Can you try using PyPy 3?

4

At first i submitted using python 3. Got CPU limit on 72 no test case. 2nd time i submitted using py py 3 but same results i got.

5

@mhiceiuk It looks like the issue is elsewhere.

So I downloaded your code and ran it on my computer with the test case where you are getting CPU Limited Exceeded. Before running it, inside the while loop, I added a print statement:

    else:
        hi = mid
    print(lo, hi)
print(cnt)

And, this is what I saw when I saw it:

499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
^C
Traceback (most recent call last):
  File "ideone_32Buck.py", line 25, in <module>
    print(lo, hi)
KeyboardInterrupt

So, as you can see, your while loop is stuck with the same lo and hi values. Essentially you are getting an infinite loop for that particular case.

So you need to fix your binary search code. :slightly_smiling_face:

6

Which formula should be used to compute the middle element?
mid = L+(R-L)//2
This one takes one more or less guess to get the required value

8

my code is showing wa for 72th testcase. Where is the error?

#include<bits/stdc++.h>
using namespace std;

int main() {
int n,x,count=0;
cin >> n >> x;
int lo=1,hi=n,mid;
while(hi-lo>=1){
count++;
mid=(hi+lo)/2;
if(mid<x){
lo = mid+1;
}
else{
hi = mid;
}
}
cout << count;
return 0;
}

11

The constraint on ‘n’ is 10^18, not 1018. Suffered a lot :smiling_face_with_tear:

1 Like
13

Very sad indeed.