Triangles containing the origin
A wonderful problem! If the radius is changed to 1200, I would say the difficulty is close to recent problems.
I did not notice how valuable it is when I first tried to solve it. My old code runs for 8 seconds. This time, I checked the discussion, I realized that I was almost doing brute force work on this problem. I used some wonderful properties of the problem, the run time is reduced to 0.07 second. Daniel challenged everyone for the case of r = 500. My code needs 34 second. I run Robert_Gerbicz's code. Oh, my god, 0.04 second, even faster than my r=105!
I reviewed his code, and found the trick that I missed. He is doing such a great job! There is some combinatoric property that we may explore. But this is not the end of the story! Robert find a much better algorithm and he can extend the problem to the case r = 2000000 solved in less than 1 minute!!!
IMHO, Robert beat everyone on this problem!
This is a great problem. I learned a great deal from Robert. I recommend everyone to take a look on Robert's second algorithm.
No comments:
Post a Comment