Блог пользователя zephyr_23

Binary search problem.
Автор zephyr_23, история, 6 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I missed exactly these cases too.

→ Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить