Is my approach wrong?
Difference between en1 and en2, changed 348 character(s)
http://www.usaco.org/index.php?page=viewproblem2&cpid=597↵

I wrote multiple solutions for this problem:↵

<spoiler summary="O(n+nlogn^2) Solution - I wrote this slower solution to compare with my faster one">↵
https://hastebin.com/panuwapaza.cpp↵
</spoiler>↵

<spoiler summary="O(n+logn^3) Solution - My original solution">↵
https://hastebin.com/vixilasaxi.cpp↵
</spoiler>↵


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(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 [user:Noam527,2017-12-14] and [user:WhaleVomit,2017-12-14] &mdash; 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).

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)