IOI 2025/1 was surprisingly mathy

(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 change. However, if $M<P_{N-1}$, then the store manager will get angry and chase Sheldon out. Suppose Sheldon knows $N$ and $P_0$. Prove that he can always make a series of purchases to end up with exactly $i$ copies of the fries with label $i$ for each $0\le i\le N-1$.

Okay, I'm not sure that that was much better than the original statement, so if that was unclear, just click on the link above.

Anyway, I proceeded to think about this in the shower, and to my surprise, solved it in my head pretty quickly. This post will be about my thought process (or at least, what I remember of it) and some general thoughts about this problem.

Preliminary thoughts

• I wonder how we're supposed to get $i$ copies of the $i^\text{th}$ thing. A sensible way would be to get one copy of everything with label $\ge1$, then one copy of everything with label $\ge2$, etc.
• But that doesn't work: if we try to pay too much, we'll instead get the label $0$ thing, which is bad.
• This is actually quite powerful: it means that we can't ever pay $\ge P_0$.
• What happens if we pay $P_0-1$? Well, we get a copy of $1$, and then probably some other stuff. Then we need to get two copies of $2$ without getting any more copies of $1$, which we don't even know the price of. That sounds bad. Maybe we could binary search for it...? No, no way that's going to work.
• Let's try small cases. If $N=2$, this works and we're done. If $N=3$...well actually, we don't have much a choice. If we choose anything $<P_0-2$, then we could end up buying nothing, which is bad. $P_0-1$ seems to be not great, so let's try $P_0-2$. If we end up buying $1$, then we know $P_1$, so we can just pay $P_1-1$ twice. If we buy $2$, then we can do $P_0-1$ and $P_0-2$ again. If we buy both...we know $P_1+P_2$, so we can just pay their average or average minus one or something and we're good. Interesting.

Generalising

• We probably can go downwards and find $P_{N-1}$ using this method: at each stage, let $M$ be the largest possible value for $P_{N-1}$. Then we can't buy nothing, since at worst we will at least buy $N-1$. 
• Does this end up with our payments going down? Probably. We can use the fact that $P_{N-1-i} \ge P_{N-1}+i$ for each $i$. Then, suppose in the previous step we've bought $N-1-i_1,\ldots,N-1-i_k$ where $0\le i_1 <\cdots < i_k$, then we can add the relevant inequalities to get $$kP_{N-1} + (i_1+\cdots+i_k) \le \text{amount paid}.$$
• This means that our next $M$ should be something like $\frac{\text{amount paid} - (i_1 + \cdots + i_k)}{k}$ or I guess the floor of that, which is $<P_{N-1-i_k}$ since $i_k>0$.
• This actually tells us something even stronger: the most expensive thing bought is strictly decreasing in price.
• So in fact, within $N$ moves, we'll end up buying just $N-1$, so we know $P_{N-1}$.
• Moreover, we can't have bought too many things, since $i$ can only be bought in the first $i$ guesses.
• This has to be substantial progress.

Completing the algorithm

• What next? Well, I suppose it'd make sense to go back upwards. Or maybe we should buy out whatever we need of the $N-1$ first? I guess we could do that whenever we want, so we should just do that later.
• Can we find out what $P_{N-2}$ is? Here's an observation: trying to buy $N-2$ while avoiding $N-1$ is sort of like trying to buy $N-1$ while avoiding buying nothing.
• With this in mind, we could maybe repeat what we did above but instead always choose the largest possible value for $P_{N-2}$? But that's not very efficient - starting from zero will make us buy too many things.
• What we can do instead is look at the last purchase before we bought the single $N-1$ and proceed from there instead.
• I guess the one difference is that now if we buy a copy of $N-1$, we should also subtract that from the amount paid when computing the maximal possible price of $N-2$.
• How do we know that we haven't bought too many copies of $N-2$? Oh, we can just look at the most expensive item again - these are distinct from everything we've found so far.
• Wait, what about if we've already used up all our $N-2$s? That means before we bought the single $N-1$, we made $N-2$ guesses, each of which ended up with a copy of $N-2$. That meanst that the last of these must have been a single $N-2$ and maybe an $N-1$, in which case we know $P_{N-2}$ already and can just move on to $N-3$.
• Right, in general if the most expensive thing bought in the guess before buying the single $N-1$ is $N-2$, then we automatically know $P_{N-2}$, so we can move back up.
• Surely we can keep going and this just works?

Formalising the proof

• Suppose we already know $P_{N-1},\ldots,P_{N-j+1}$ and we want to find $P_{N-j}$. Then, out of all the previous purchases, look at all the most expensive items and out of the ones that are more expensive than $N-j$, pick the cheapest. Then, we can keep guessing the highest possible price for $N-j$ as above. In each stage, the most expensive item is cheaper than the previous, and is something that hasn't ever been a most expensive item.
• We can view this as a tree with root node $0$, then our process to find $P_{N-1}$ gives us a path $0, i_1,\ldots, i_k = N-1$. Then, we're branching out from $i_{k-1}$ to get another path until we hit $N-2$, then branching out from the penultimate edge from that, etc., moving backwards in the tree whenever we're at a node $N-j$ such that we know all prices from $N-1$ to $N-j$ inclusive. In this way, we have a tree whose nodes are labelled exactly $0$ to $N-1$, so we can't have bought more than our quota.
• Then, we can just buy items individually, since we know all their prices.
• Oh, I guess we're done.

Remarks

A simplification

Actually, all we needed for this proof to work is a way to go from a guess to another guess whose most expensive object is cheaper. So instead of having to deal with adding up $i_1$ to $i_k$ to get some error term, we can just take (the floor of) the average of the prices, and maybe $-1$ from that if $k=1$.

In particular, this means that $P_0-1$ as a first guess is actually fine, contrary to what my intuition said.

On the problem

I did this in my head in about 10 minutes, so I was a little disappointed because I still wasn't done showering. I think this is probably around an easy-medium level in the IMO: probably too hard for P1/4, but also a little too easy for a P2. In a way, I don't see how one could fail to at least find a winning algorithm: you're very restricted on legal moves, and if you just keep doing any sensible thing, you end up with a working algorithm. Writing out a proof for why this actually works requires a bit more insight: you have to keep track of the most expensive item in each purchase, but that's about it. In the IOI, though, you don't actually have to write out a proof; you just need to convince yourself that it works and then implement it.

It's thus extremely surprising to me that out of 330 IOI participants, only 53 solved this fully (source); that's a lower solve rate than this year's IMO P3! Maybe it's hard to implement? I guess I should try to sketch an algorithm...

A sketch of an implementation

• Set a variable $a$ to be $N-1$: this represents the highest label whose price we don't know.
• Initialise three lists of length $N-1$: these represent, respectively:
• the purchase whose most expensive item is $i$ for each $i$
• the total cost of that purchase
• the number of times we've purchased item $i$
• Submit $P_0-1$.
• For each response:
• In the index corresponding to the most expensive item bought, save a list (consisting of the items bought, in increasing order of label) and the total cost (i.e. amount paid minus the change).
• For each item bought, increment the number of times we've purchased it.
• For each item whose label is $\ge a+1$, remove it from the list and subtract its price from the total cost.
• If the most expensive item has label $a$, do the following while loop:
• If we've already made a purchase with most expensive item $a$ (which was previously $a+1$):
• Save the price for $a$.
• Look through all the lists of purchases corresponding to the more expensive items, and if $a$ was bought then (in which case it has to be the last item in the list), remove $a$ and subtract its price.
• If not, break the loop.
• Decrease $a$ by $1$.
• If $a=0$, then terminate the outer loop.
• Else, look for the largest index $b$ which is $<a$ such that we've already made a purchase with most expensive item $b$. Then, submit the floor of the average cost of that purchase (minus one if $b$ was the only item).
• For each item, look at how many we're missing and pay its exact price the relevant number of times.

If I'm not wrong, this is $O(N^2)$? It's $O(N^3)$ if you don't notice that you just have to look at the last item in the list, and instead iterate through the whole list. Even the latter is fast enough; the bounds on $N$ are $2\le N \le 100$.

On the problem (continued)

...that wasn't too difficult, I think. Maybe people decided that their time would be better spent getting marks on the other problems. Shrug.

Anyway, difficulty aside, I think this is a really nice combi problem: I like how there's some leeway in performing the algorithm, but proving that any of the variation works relies in some insight into the underlying structure of the problem. (Possibly I'm biased because I like structural combi.) This wouldn't be out of place in the IMO. In fact, I personally believe this would have been better placed in the IMO than the IOI since it would force contestants to actually have to know why the algorithm works, but I'm sure people would disagree with that.

IOI vs IMO

This problem highlights some key differences between the IOI and the IMO: both would require finding a correct winning algorithm, but after that the tasks diverge. In the IMO, one would have to actually prove that the algorithm works (so finding the relevant structures/monovariants), and then write out said proof. In the IOI, on the other hand, one has to convert this into code (that runs within the relevant time/memory parameters).

This is also reflected in the partials: in the IOI, one could get up to 39/100 by just dealing with various special cases ($N=2,3$, and some very strict conditions on the price differences). On the other hand, in the IMO these would probably not be worth any marks. Conversely, partial progress in the IMO which got up to the point of finding $P_{N-1}$ (along with a proof that this hasn't broken anything) would probably be worth 3/7, but is useless in the IOI (though I suppose one could in theory get 3/100 from the $N=2$ case).