walnutwaldo20's blog

By walnutwaldo20, history, 3 years ago, In English

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!

Read more »

 
 
 
 
  • Vote: I like it
  • +44
  • Vote: I do not like it

By walnutwaldo20, history, 3 years ago, In English

With the new change of having Master starting at 2100, there is a bug with the rating changes in the contests tab of some people's profiles.

If you look here (sorry I don't know how to insert an image), my latest rating change, where "Became Master" should be, instead says "Became Candidate Master" again.

This is not a huge issue, but I thought I should point it out so it could be fixed by the Codeforces team.

There is a chance you might not see this, MikeMirzayanov, so I'll just tag you in case.

Thanks and have a great day!

EDIT: with some other people, there are some weirder issues with title changes being shown when they are not supposed to be. Ex. linpaws

Read more »

 
 
 
 
  • Vote: I like it
  • +69
  • Vote: I do not like it