SIMO Retiree Blog

(Glen here.) Recently, there was some discussion about this year's IOI in a group chat, and Ker Yang remarked that the first task, " Souvenirs ", was basically a math question. Of course, I had to have a look. The original description is pretty long, so here's a rewriting in a more math olympiad style: Sheldon is buying french fries from a fast food restaurant, which sells fries in $N$ different sizes (with packagings labelled from largest to smallest from $0$ to $N-1$), with integer costs $P_0 > P_1 > \ldots > P_{N-1} > 0$. To buy fries, Sheldon can pay $\$M$ where $M$ is a positive integer, and then define a sequence $i_1,i_2,\ldots$ as follows: $i_1$ is the smallest integer such that $P_{i_1}\le M$, and in general, $i_k$ is the smallest integer $>i_{k-1}$ such that $P_{i_k} \le M - P_{i_1} - \cdots P_{i_{k-1}}$. If no such $i_k$ can be defined, the sequence terminates. Then, Sheldon receives the fries with labels $i_1,i_2,\ldots$ along with his chang...

(Yu Peng here) Sometimes, you feel like you should be on the right track in solving a problem, but your solution falls short a little, due to issues like having a suboptimal bound, or having a condition you need but isn't true. At other times, you could just be struggling to find the optimal construction. At such times, it would often do you good to take a step back, and think about how you can optimise your solution.

(Yu Peng here) For this post, I'll go through a common idea in competitive programming - dynamic programming - and some of my thought processes when I apply it to problems.