http://www.usaco.org/index.php?page=viewproblem2&cpid=597

I wrote multiple solutions for this problem:

My approach: - Store values, multiply them by two. This avoid errors in dealing with floating-point values - Precompute prefix and suffix: at every point store the value of radius necessary to destroy all haybales to the left (prefix) and the right (suffix). - Binary Search on Size of initial Radius (of explosion) - Binary Search of location - upper_bound/lower_bound inside to check for location, and then check if possible location using prefix/suffix values

I have tried to debug this for about a week, I asked about 4 people, and I changed my method and I still get WA with binary search.

Some things that I tried: - Wrote slower code for less chance of error; this code produces same output - Changing upper and lower values of binary search to the only possible locations of haybales (I changed it back because this had no effect)

Some things I haven't tried: - Throw away prefix/suffix and check it in O(n) <-- (now I tried, it worked)

Should I completely changed my approach? I think this approach can go. If it is just another bug (hopefully), does anyone have an idea what the bug is?

EDIT: I solved it thanks to Noam527 and WhaleVomit — wv made me realize my suffix and prefix ignored the case where the optimal simulation does not travel along adjacent hay bales. Also Noam suggested O(n) checking (which worked).