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.


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


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