Напоминание: в случае технических проблем любого характера, вы можете использовать m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

Why does this solution work?

Правка en1, от 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?

Теги #binary search, atcoder, minimario

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский brdy 2017-12-24 05:12:08 815 Initial revision (published)