ADANTS approach and lesson learned!

general
,
1

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. :muscle:
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. :sob: 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:

  1. 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).
  2. 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!!

3 Likes
2

My approach first approach was to create a convex hull and move along it’s path.

The thing is, all the Convex Hull Algos try to choose points in such a way so that most of the points are contained inside the perimeter. This doesn’t guarantees selection of maximum number of points in one instruction.

I got TLE. :frowning:

My Second approach was a very naive one. Just to test my theory. I kept choosing two integral points repeatedly and kept remove the first one. Albeit I got AC but this doesn’t minimize the operations. I was on the top for 7 days. yay! :smiley:

My third approach was a mixture of the above two, I was trying to choose convex hull made up of only integral points. So I just needed to save the last point of the hull every-time, because all the points are integral in between. But I guess my solution wasn’t the best. In last 3 days, some other coders got AC and I ended up being ??? maybe 4/5/6.

Also thanks for D_GLIBCXX_DEBUG flag. I will keep that in mind.

1 Like