Why does this solution work?

Revision en1, by brdy, 2017-12-24 05:12:08

Here is the Atcoder ARC/ABC — D problem from today's contest.

https://arc088.contest.atcoder.jp/tasks/arc088_b

The editorial describes an O(n) solution.

My question is about a different solution. When I first saw this problem I thought binary search on the radius would work, but quickly discarded the idea because I could not think of a correct "check" function to see if a given radius works.

However, minimario proved me wrong.

Here is his code: https://hastebin.com/qefuquxoke.cpp

In his check function, he assumes that "k to n is fixed" and "0 to n-k-1 fixed", which seems to be the basis of the function's logic. (I ran his code by hand, but it still feels like magic to me)

Can anybody elaborate on the reasoning behind this solution?

Tags #binary search, atcoder, minimario

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English brdy 2017-12-24 05:12:08 815 Initial revision (published)