JigolKa's blog

Need guidance on problem
By JigolKa, history, 12 months ago, In English

Hello Codeforces,

I'm still learning binary search, and I can't understand why my implementation doesn't work for 1805C - Place for a Selfie I'm pretty sure my math is correct but maybe it's not. Here is the link to Desmos to visualize it.

Here is my latest submission 316427863. Basically, l and r are the slopes at which y=l*x and y=r*x intersect with the parabola. That's when I try to search the first element l<x<r with binary search.

Thanks for your time

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Predicate l<x<r looks like [false,...,false,true,...,true,false,...,false] and is not monotonic, thus cannot be used for binary search (unless you really understand what you are doing in some cases).

→ Reply