mdtareque's blog

How to approach this problem with binary search?
By mdtareque, history, 8 years ago, In English

This problem has a tag binary-search and also on a2oj ladder it's given under binary search. Div2 : B http://codeforces.me/contest/492/problem/B

I solved it by plain sorting the array and finding the max difference as given in the editorial.

But, I would like to know how to solve this by binary search? Any hints/pointers please? I am curious to do this with a new approach.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
8 years ago, # |
← Rev. 6   Vote: I like it +5 Vote: I do not like it

First of all add 0 and l(length of the street) in array(if they are not exist). Then sort it. Now use the binary search. Assume that middle of ours range is minimum radius. Then we go trough the array and check whether ours "middle point" is fit. If is it, then high = mid, else low = mid.

(Sorry for my poor English)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Hi, Thanks a lot for your help. :) Submitted using binary search . 19285506

    It is fully commented, if you have any suggestion for code imporovement please let me know.

    → Reply