Hello everyone!

Some of you may know that there is a sequel book Looking for a Challenge 2. Unfortunately, it is in polish, but monsoon was kind enough to translate the problems and some of the solutions to English! I really like the Polish problems, so I've decided to go through the pain of translating the solutions myself and I may as well post them somewhere for others to enjoy too. Here is the solution of the problem "Vending Machine" (see page 55 for English task statement).

By the way if you are Australian olympiad students, stop reading so that you don't spoil my lecture :)

Let's first establish the order we should buy the snacks. Suppose we want to buy a snack of type $$$i$$$ and a snack of type $$$j$$$ ($$$i < j$$$), which one should we buy first? Note that the total value of the snacks dispensed doesn't depend on the order we buy these two snacks. However, if there is only one snack of type $$$i$$$ we cannot buy snack $$$j$$$ first. So we can assume that snacks should be bought in non-descending order (i.e. from left to right).

With this observation, we could solve the problem recursively by trying all the buying strategies. Of course, such a solution will be too slow. To overcome this, we will use dynamic programming to memorize the results. It is quite tricky though, because it requires the following idea: although we buy the snacks from left to right, the buying strategy will be built from right to left.

When planning to buy a type $$$j$$$ snack, we know that we will also get snacks of types $$$1, 2, ..., j-1$$$ (if there are any), though maybe we will get them with a type $$$j$$$ snack, or maybe by buying some other snacks of type less than $$$j$$$. To help us visualise the problem, let's arrange the snacks in a 2D grid: For each snack, stack them to create a column of numbers $$$c_i$$$ of height $$$l_i$$$.

Suppose we choose to buy a type $$$4$$$ and type $$$6$$$ snack. Recall our strategy is to buy snacks from left to right. So firstly, we buy the type $$$4$$$ snack and we get $$$7+2+5$$$ (marked with circles in the above image) value, then we buy the type $$$6$$$ snack and get $$$2+5+7+2$$$ (marked with squares). Note that when we buy the second snack, we do not get a type $$$1$$$ snack, since it has already run out.

However, we can equivalently plan to buy the type $$$6$$$ snack, knowing that whatever other snacks we choose to buy, we will certainly get $$$7+2+5+7+2$$$ (marked with circle in the diagram below), and then plan to buy a type $$$4$$$ snack, remembering that we already planned to buy a snack to the right (the type $$$6$$$ snack), so we only get $$$2+5$$$ (marked with squares). Note that if we had already planned to buy $$$l_i$$$ or more snacks, then we cannot buy snack $$$i$$$ (since there are none left).

Attributing the snacks this way, we are limited to buying one snack from each row. To make things convenient, let us define $$$t[i, y]$$$ to be the sum of the first $$$i$$$ snacks in the $$$y$$$th row (treating empty cells as $$$0$$$). For example, $$$t[6, 1] = 7 + 2 + 5 + 7 + 2 = 23$$$ and $$$t[4, 2] = 2 + 5 = 7$$$. The table of prefix sums looks like this:

So our problem has been reduced to this: Select a set of cells $$$(i, y)$$$ in the grid such that:

• In each row, the selected cell must not be located to the right of the selected cell in the previous row.
• In the $$$i$$$th column, we cannot select more than $$$l_i$$$ cells.
• The sum of values $$$c_i$$$ in the selected cells must be at most $$$k$$$ (our budget).
• The sum of $$$t[i, y]$$$ of selected cells is maximised.

Suppose we are in the $$$i$$$th column and selected a number of cells in it, between $$$0$$$ and $$$l_i$$$. From the above reasoning, it can be seen that the only information we need to track is the number of cells selected in total, and our remaining budget (denote these values $$$y$$$ and $$$b$$$ respectively).

This gives us a dynamic programming solution like this ($$$s$$$ is the number of cells we choose to pick in column $$$i$$$):

$$$w[i, y, b] = \max_{0 \leq s \leq l_i} {w[i+1, y-s, b + s \times c_i] + \sum^s_{h=1}{t[i,y-h+1]} }$$$

Let's determine the complexity of this solution. Let $$$C$$$ be the greatest price snack and let $$$L$$$ be the most snacks of a single type. There are $$$n$$$ possible columns, there are $$$L$$$ possible rows and our budget is at most $$$k$$$. So there are $$$O(nLk)$$$ states in total. For each state, we compute the answer in $$$O(L)$$$ time, since we have to try taking all possible numbers of cells. So in total, it is $$$O(nL^2k)$$$.

With the constraints of the task, this gives $$$40^3 \times 64\,000 \approx 4 \times 10^9$$$ which is a bit too much. But it is enough to note that such a large limit on $$$k$$$ makes no sense. If we buy $$$L$$$ snacks with the largest value, then the vending machin will be completely empty and we will pay a maximum of $$$LC$$$, denoting the rest to charity. Therefore, we can assume that $$$k$$$ is at most $$$LC$$$, dropping the complexity to $$$O(nL^3C)$$$, which will give constraints of about $$$40^5 \approx 10^8$$$, enough to run in time.

The memory complexity is $$$O(nL^2C)$$$ which is small enough, but it can easily be reduced to $$$O(L^2C)$$$ by remembering only two layers of our table at a time.