Is my approach wrong?

Revision en2, by brdy, 2017-12-14 02:50:07

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) <-- (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).

Tags binary search, usaco


  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)