zephyr_23's blog

Binary search problem.
By zephyr_23, history, 7 years ago, In English

I am trying to solve this binary search problem (https://www.codechef.com/problems/FAKEBS) on codechef.

I am getting W.A on 3 tasks out of 12 and those are small tasks. I think I am missing some edge cases. Can someone please help ?

Code :- https://ideone.com/VnwXtb

Thanks.

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I missed exactly these cases too.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

The problem is that you aren't counting the numbers that need to be less than x and are less than x. Say if you encounter a number at mid which is less than x and you need a number less than x, you can't use it for swapping later on. Similar thing needs to be done for greater than x case too. You missed this point and so you are failing in those cases. I hope I am making sense.
Here's my AC code for reference : Link.
The sub_h and sub_l variables in my code are what I am talking about.

→ Reply