As I cried in a previous post, I made a mistake that avoid me of trying to improve my solution of the challenge problem ADANTS. I will first comment on that error to remember myself don’t do it again and to prevent others. After that I share my final approach to the problem.
I started trying complicated things, looking for some heuristic that minimizes the solution but every single thing I tried was very time consuming or have very poor final result. I always try to make this tests locally for two reasons: it’s faster and I don’t waste sumissions (the limit is 100 submissions for the challenge problem). The case is that I found an approach that seemed to be good but requiered fine tuning of some parameters and, inexplicably to me at that moment the time performance of my local tests were by far more time consuming that the same solution tested in CodeChef. So I was forced to make submissions to tune the parameters. It seemed like worthed it…that put me on first place of ADANT two days before the end of the contest.
On my saturday morning (I’m far-west located) my solutions was somewhere between top 6 and 8, don’t remember. So a new approach was needed. I did that and gave with a much more efficient one that put me on second or third place and with running time of less than 1 second, so there was much place to improve! Let’s do that, I said, but here is where the error would make me pay. I ran out of sumbissions…I had reach the limit. The question is, why the running time was so poor in my local tests, what was going on?! I have a modest PC but not that bad. And the key was the “-D_GLIBCXX_DEBUG” compilation flag wich I forgot to remove from my compilation instruction!!! So, lesson learned: remove D_GLIBCXX_DEBUG flag when you need to test time performance!!
Now, my approach to the problem. Finally the simplest I tried was my best:
- take as many points as time limit let you, calculate their Convex Hull and apply the movements the points of the Convex Hull (with some test to choose which point will be the final one).
- Repeat 1 while there is more than 1 position.
Of course you can not take all the points in each step so what I did was to define circles of fixed radius (centered on 256,256 for the first test and 512,512 for the other ones) and solve the problem in each circle from the outer one to the inners. That’s all. This approach finished 5 or 6 in div1.
Remember…be careful with D_GLIBCXX_DEBUG flag!!