KitayutaMart

Review

Summary

This was a really hard problem for me. I was unable to solve it in the contest. Even after inspecting Petr's solution, it took me a while to understand and derive the actual answer for myself. Here is my summary of the approach to solve the problem -- hopefully we will be able to recreate the "correct train of thought" needed to solve this problem.

The first initial observation is that "the algorithm" for choosing apples is fixed. You will always buy the cheapest apple at any point in time, until you have $N$ total apples. The answer is the value of last apple you buy. Remember this, because we can use this fact throughout the analysis.

Now, we cannot simply "enumerate" or "list" all the apples explicitly, as $N$ and $K$ are too large to do this. But is there any efficient way to determine what this "last apple" would be?

At this point, we work backwards. What if we knew the final value of the apple? Or, what if we had a "guess" $v$ for what this value might be? Is there any way of checking whether $v$ is a good guess or a bad one? In theory, the answer is yes. Particularly, let's suppose we were able to count the total number of apples with value $\leq v$. If this number is strictly smaller than $N$, then we can be sure that $v$ is too small of a guess. This is because of our "initial observation": we will always choose the cheapest apples until we get $N$ of them. And if there are less than $N$ apples with value $\leq v$, then we must pick at least one apple with a value $> v$ in order to get $N$ apples in total. Conversely, if the answer we get is at least $N$, then we know $v$ is a good guess, and we will stop at $v$ or earlier than $v$.

This leads to a "binary search" idea. Fix a $v$, and count the total number of apples with value $\leq v$. If this is less than $N$, try a bigger $v$. Otherwise, try a smaller $v$.

There are two issues with this, though. First, $v$ might be extremely large! The numbers in the input can become as large as $2^{1000000000}$ or bigger. The second issue is: "How do we count the total number of apples with value $\leq v$?"

To answer both of these questions, and to (hopefully) lead to further insights, we both look at examples and draw a picture. Consider an example where $N = 30$ and $K = 10$ (you might also try smaller examples; we may use bigger examples later). To "illustrate", we draw an $K \times N$ matrix, where cell $(i,j)$ has value $i \cdot 2^{j-1}$ (the cost of the $j^{th}$ copy of apple $i$). This matrix is drawn below.

Furthermore, suppose that we have a guess for $v$. For example, let us guess that $v = 224$. Then we would choose all apples with value $\leq v = 224$. In the matrix below, we have coloured/shaded the related cells.

1248163264128256512

2481632641282565121024

36122448961923847681536

4816326412825651210242048

51020408016032064012802560

61224489619238476815363072

714285611222444889617923584

8163264128256512102420484096

9183672144288576115223044608

10204080160320640128025605120

You can verify that there are $61$ apples with value $\leq 224$. Since $61 \geq N = 30$, this $v$ is large enough.

At this point, we can play around with different values of $v$, and try to note down any observations we find. Here are a couple of these key observations (it's often helpful to write out our findings):

1. Without loss of generality, our minimum $v$ will always be an element in the table, of the form $i\cdot 2^{j-1}$ for positive integers $i$ and $j$ (with $1 \leq i \leq K$). If we have a guess for $v$ that is not an actual element of this form, we can simply decrease $v$ until we find a guess that is of this form. For example, $224 = 7\cdot 2^5$.
2. Given a fixed $v$, consider the columns in the matrix from left-to-right, and we notice a pattern: there will be a few columns where all the cells are selected, followed by columns in which the number of selected cells decreases by (approximately) half from column-to-column.

To some readers, these may seem almost obvious. But focusing on these observations helps us to answer the questions we had earlier! In particular, we can use this "pattern" to quickly count the total number of apples with values $\leq v$. Firstly, we write $v = i \cdot 2^{j-1}$ with $1 \leq i \leq K$ (which is possible from Observation 1). Then we consider the "pattern" of cells that would be selected when looking at values $\leq v$. In columns $1,2,3,...,j-1$, all K cells must be chosen. Then in column $j$, we get exactly $i$ cells. In column $j+1$ we get $\left\lfloor\frac{i}{2}\right\rfloor$ cells, and in column $j+2$ we get $\left\lfloor\frac{i}{4}\right\rfloor$ cells, and so on. This goes to 0 in a logarithmic number of steps.

We can formalize this argument. Let

**Then, for a number $v = i \cdot 2^{j-1}$ (with $i$ the largest possible such that $1 \leq i \leq K$), there are exactly

apples with value $\leq v$.**

I omit the proof, but the idea can be seen from the picture. One important detail must be discussed however: ambiguity. Some numbers, like $512$ appear multiple times in the table. This corresponds to many different ways of writing $512$ as $i \cdot 2^{j-1}$. For the proof to work (and this also turns out to be the most intuitive assumption as well), we assume that $j$ is as small as possible (equivalently, that $i$ is as large as possible) among all representations of the same number. This is the occurrence in the "left-most" occurrence of the number $v$ in the matrix. For example, we write $512$ as $8 \cdot 2^{6}$ rather than $4 \cdot 2^7$ or$1 \times 2^9$.

We notice that $S(n)$ can be counted in logarithmic time (since the parameter $n$ is cut in half iteratively), and the $(j-1)K$ part can be computed in $\Theta(1)$ time. So this answers one of our earlier questions about being able to efficiently count the number of apples for a given guess $v$.

If the numbers were smaller, we could do a binary search, and we'd be done. However, we need a way to quickly make guesses for $v$ without explicitly having to represent it -- since the number $v$ can be really large. Also, in our counting formula above, we assumed $v$ had a certain form: $i \cdot 2^{j-1}$.

To deal with these issues, we represent the number $v$ using the most natural idea based on the data we have. We always represent $v$ as a pair $(i,j)$, meaning that $v =: i \cdot 2^{j-1}$, and $i$ is as large as possible without being bigger than $K$.

At this point, I think a cleverly crafted search, similar to "Gallop search" or something like that, might be able to help us. We are simply looking for the parameters $(i,j)$ that yield a minimum $v$ so that

One problem, however, is that we don't have a nice bound on $j$. How large of a $j$ would be necessary? How small of a $j$ would be sufficient?

Now that we have a nice formula, we can use it to find the bounds we are interested in. We know that $i \leq K$. In fact, we know that $\frac{K}{2} \lt i \leq K$, because we chose $i$ to be the largest among all representations. (If $i \leq \frac{K}{2}$ then we could let $i' = 2i$ and $j' = j-1$ to get a better representation of our number $v$. This would usually be a contradiction.) Anyway, putting this together with our formula, gives us that:

Now, we want to find $(i,j)$ such that $(j-1)K + S(i) \geq N$. What is the smallest $j$ we can have? Well, we can apply the second inequality above and assume $i = K$ (since this is the largest choice of $i$ for any fixed $j$). From this we would get:

or

And note that substituting $i=K$ was valid. If $i$ is smaller than $K$, then we would need an even larger value of $j$ to compensate. Hence, we have proven the following theorem: **For any $v = i \cdot 2^{j-1}$ with $1 \leq i \leq K$, if there are at least $N$ apples with value $\leq v$, then: