Is my approach wrong?

Revision en1, by brdy, 2017-12-13 22:51:24

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

I wrote multiple solutions for this problem:

O(n+nlogn^2) Solution - I wrote this slower solution to compare with my faster one
O(n+logn^3) Solution - My original solution

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) <-- the person who suggested this also acknowledged my prefix/suffix were correct

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?

Tags binary search, usaco

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English brdy 2017-12-14 02:50:07 348
en1 English brdy 2017-12-13 22:51:24 1577 Initial revision (published)