Squares under a hyperbola
This is an interesting and simple problem. If the question asks for(4,4) instead of (3, 3), then it is quite difficult. My old code runs for 1.3 second to get the answer for (3, 3). I read the discussion immediately after I solved the problem a year ago. One Eulerian raise the question to find the largest S_n for (4, 4). I tried it with my poor code, I found that I got an out-of-memory error. I added a comment in my old code then left. What a bad habit!
This time, after I thought it over, I find I have plenty of room for further optimization. The first optimization is to prune the tree as early as possible. After that I reduce the runtime to 0.6 second for (3,3). I used the same code to solve (4,4). It takes 37 seconds, still too long! I then found that some extra and fancy manipulation of my algorithm is totally unnecessary! I used a stack to solve the problem. This time, the run time is quite satisfactory.
(3, 3) 20 ms
(4, 4) 6 seconds
No comments:
Post a Comment