zephyr_23's blog

By zephyr_23, history, 3 months 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  

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I missed exactly these cases too.

  • »
    »
    3 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Try this test case:-

    1

    5 1

    6 7 3 5 4

    4

    If your mistake is same as mine, then it would print 1 as it will consider 3 as a candidate for swapping but it cannot be used. Answer should be -1. I got A.C now.

»
3 months 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.