Although this post is directed at people who are already familiar with Alien's Trick, if you are interested in learning about it, it is based off this IOI 2016 problem, and the method of solving the problem is described here.
I am currently studying some common DP optimization tricks such as CHT (Convex Hull Trick) or Knuth's Optimization. When I got to Alien's Trick, however, it was much harder for me to wrap my head around it. I am able to follow the math and understand the reasoning behind it, but I just cannot seem to build intuition or see how someone would go about coming up with this trick on their own. Although, I know jcvb, for example, was able to get full points on the problem during the contest.
I know that jcvb and whoever came up with the problem are much more experienced than me and are very intelligent, but I feel like I am missing some sort of intuition behind what Alien's Trick is actually doing. Yes, it solves the problem, but what ideas are hidden inside the math?
Also, what is the thought process that leads to coming up with Alien's Trick? If you were an IOI 2016 contestant and saw the problem for the first time, what goes on in your mind to lead you to the intended solution?
This entire post is going by the assumption that Alien's Trick first appeared on IOI 2016, and I could very well be wrong about that. There is not much material online about Alien's Trick that I could find and I don't know if there is another name for it. Please correct me if I am mistaken, and if you could, provide a reference to where it appeared somewhere else.
Finally, I am not asking nor do I wish to take too much time from your days as I know there is a lot of stuff you all have to do, so a small insight, or even a link if this question has been answered somewhere else, would be valued a lot.
Thanks in advance, and best of luck on all of your future endeavors!
