dx24816's blog

IOI 2016 Aliens
By dx24816, history, 5 years ago, In English

Hello,

Can someone provide and explanation of the DP optimization used to get 100 points on Aliens of IOI 2016? I read their solution, but I still don't see how introducing the constant C helps you solve the problem. I also don't see the purpose of the g function they introduce.

Problem:https://ioinformatics.org/files/ioi2016problem6.pdf Solution: https://ioinformatics.org/files/ioi2016solutions.pdf

-dx24816

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

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Here's an explanation for the same trick on a different problem: https://codeforces.com/blog/entry/49691

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Another article: https://codeforces.com/blog/entry/68778

→ Reply