Is my approach wrong?

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

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


  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)