Hello everyone!

After one year, I am back to translating Looking for a Challenge 2. At this rate, I will finish in 2060 :)

Today, I am looking at "The Motorway" from 2013 (see page 79 for English task statement).

Abridged problem statement

There are $$$n$$$ entry points along a motorway. The $$$i$$$th entry point is located $$$a_i$$$ metres from the start of the motorway.

Byteasar would like to build $$$n+1$$$ tollbooths on the motorways so that:

• The tollbooths are evenly spread out so that the distance between consecutive tollbooths is the same
• Between every two consecutive entry points, there is a tollbooth (it is acceptable for a tollbooth to be positioned exactly at one of the entry points).
• There is a tollbooth before the first, and after the last entry point (or exactly at).

Formally, an arrangement of tollbooths can be described by the position of the leftmost booth $$$b_0$$$ and a distance $$$l$$$ between consecutive tollbooths. The tollbooths would be positioned at $$$b_0, b_0 + l, b_0 + 2l, \ldots, b_0 + nl$$$. The $$$j$$$th entry point must be positioned in the interval $$$[b_0 + (j-1)l, b_0 + jl]$$$.

Your job is to find the minimum and maximum possible $$$l$$$ where an arrangement exists. Give your answer within an epsilon of $$$10^{-8}$$$.

Bounds: $$$3 \leq n \leq 10^6$$$, $$$0 \leq a_i \leq 10^9$$$

Solution

Translation note: Initially, I was planning to faithfully translate the (very thorough and detailed!) solutions from Polish, but that turned out to be a lot of effort... so instead, I have decided to use the original solutions as more of a reference.

For conciseness, we will use $$$s$$$ instead of $$$b_0$$$. We will also focus on finding the minimum $$$l$$$ (maximum $$$l$$$ will be similar). Let's rewrite the condition. For $$$0 < i < n$$$, we need the $$$i$$$th tollbooth to lie between entry point $$$i-1$$$ and $$$i$$$. So,

Note that $$$\frac{a_{i-1}}{i}$$$ and $$$\frac{a_{i}}{i}$$$ are constants, so we'll denote them $$$L_i$$$ and $$$R_i$$$ respectively:

(This doesn't take into account the requirement that there should be a tollbooth before the first and after the last entry point, but one can introduce virtual entrypoints at -infinity and infinity to accommodate for this. Perhaps there is a more elegant way.)

Thus, we can interpret the condition on the $$$i$$$th tollbooth as constraining $$$l$$$ to an interval $$$[L_i, R_i]$$$. What about the $$$-\frac{s}{i}$$$? This represents a shift of the interval by $$$s$$$, scaled by $$$\frac{1}{i}$$$.

For a fixed choice of $$$s$$$, we can easily determine the intersection of all intervals in linear time, thus we can determine the range of possible $$$l$$$ in linear time. That's great, but there are too many possible choices of $$$s$$$.

To save us, we need to observe that we can binary search on $$$s$$$. One can imagine that as $$$s$$$ increases, the interval $$$[L_i, R_i]$$$ sliding to the left. Intervals with larger $$$i$$$ slide more slowly (as it is scaled by $$$\frac{1}{i}$$$).

Claim: The values of $$$s$$$ that admit a valid solution form an interval. Informal proof: If two intervals are "moving" in the same direction, then the interval that represents their overlap is also "moving" in that direction. Furthermore, the "time" that they overlap is contiguous. This extends to the intersection of multiple moving intervals by induction.

Claim: Maximising $$$s$$$ also minimises $$$l$$$. Informal proof: If two intervals are "moving" in the same direction, the endpoints of their overlap are also moving in the same direction. Thus, the largest value of $$$s$$$ will give the smallest left endpoint (remember that the shift is by $$$-\frac{s}{i}$$$).

These two facts allow us to binary search on $$$s$$$. If we calculate that the intervals do not overlap, we can pick any two non-overlapping intervals and check whether $$$s$$$ needs to be increased or decreased.

This gives a solution that runs in $$$O(n \log M)$$$, where $$$M$$$ is the required precision, which suffices to solve the problem.

Translation note: The polish solution described a few solutions, of which the one I provide above is one of them (I think). It also presents a linear time solution, but note that it is very difficult to implement.

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 image 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 machine will be completely empty and we will pay a maximum of $$$LC$$$, donating 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.