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] — 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).
↵
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) <--
↵
↵
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] — 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).
