KitayutaMart

Review

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.

(The shaded cells of the original figure — the apples with value $\leq 224$ — are shown in bold.)

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:

This gives us a lower bound on $j$ for valid $(i,j)$ pairs. But we are actually interested in an upper bound on $j$. If we draw more pictures, look at more examples, or go back to our formulas, we realize that this value $j^*$ actually tells us a lot more than we thought! We can actually prove another lemma: if $j > j^*$ and $i > \frac{K}{2}$, then the value $(j-1)K + S(i)$ will be at least $(j^*-1)K + S(K)$. So any minimal $v$ will have $j \leq j^*$. This is best shown with a picture. I omit such a picture, or a detailed explanation/proof, but it also follows from the inequalities above. I encourage the reader to prove why this is true.

In any case, we have therefore discovered that, once we have found $j^*$, our "optimal" (minimal) $v$ will be of the form $i \cdot 2^{j^*-1}$ for some $1 \leq i \leq K$. With this information, we can use a simple binary search on $i$, checking whether $(j^* - 1)K + S(i) \geq N$ at each step or not. Once we've found our minimal $i^*$, we output the answer $v = i^* \cdot 2^{j^*-1}$ (modulo the number $1,000,000,007$, as asked in the problem statement.)

Pseudo-code:

S(n):
  answer := 0
  while(n > 0):
    answer += n
    n = n / 2
 
  return answer
 
lastPrice(N,K):
  Let jstar = ceil((N - S(K)) / K) + 1  # The optimal j^*
 
  low = 1
  high = K
  while low < high                      # binary search
    i := (low + high) / 2
    if (jstar - 1)*K + S(i) >= N:       # how many apples no more than v = i*2^(j*-1)?
      high = a
    else
      low = a+1
 
  istar = low                           # same as high
  return istar * power(2, jstar - 1) MODULO 1,000,000,007

Key observations:

• When choosing apples, the order is fixed. We always choose the least costly apple first, and then repeat until we have $N$ apples. This simple observation helps to point us in the right direction. We know that the algorithm for choosing apples is simple, so we can exploit its "greedy" properties later to achieve a good algorithm for counting the apples.
• Consider a minimum guess $v$. Then $v$ must be an element of the form $i \cdot 2^{j-1}$ for some $1 \leq i \leq K$. Moreover, without loss of generality, we can assume that $i$ is maximal among all such representations of $v$. A rather obvious observation. But its helpful to write it down. This characterization actually allows us to focus our attention on "special" values of $v$.
• Consider a guess $v$ of the form $i \cdot 2^{j-1}$ with $1\leq i \leq K$ and $i$ maximal over all such representations. Then, the total number of apples with value $\leq v$ is exactly $(j-1)K + S(i)$, where $S(i) := i + \left\lfloor i/2\right\rfloor + \left\lfloor i/4\right\rfloor + ... + \left\lfloor i/8\right\rfloor + ...$ This was the key formula that enabled us to solve the counting problem! Once we have this formula, the problem becomes much easier to solve.
• Consider a value $v = i \cdot 2^{j-1}$ such that at least $N$ apples have value $\leq v$. Then it must be the case that $j \geq j^*$, where $j^*:= \left\lceil\frac{N - S(K)}{K}\right\rceil + 1$. This can be proven from the formula above, and by using the fact that $i \leq K$. Basically, as long as $j < j^*$, then you can prove that $(j-1)K + S(i) \lt N$. The statement above is the contrapositive of this (and is therefore equivalent).
• Consider the minimal $v = i \cdot 2^{j-1}$ such that at least $N$ apples have value $\leq v$. Then $j \leq j^*$, as defined above. This is the upper bound to match the lower bound. This tells us that for any optimal $v$, there is a single $j^*$ that we must use. It simply remains to find the $i$. Note that this statement can be proven using the observation that $i \gt \frac{K}{2}$ whenever $j > j^* \geq 1$. Why? Because if $i \leq \frac{K}{2}$ then $v = (2i) \cdot 2^{j-2}$. And this is a representation with a bigger value of "$i$", so this would contradict our choice of representation. Once you have this fact, you can subsitute this inequality into the formula (some how...) and eventually derive the result. Alternatively, you can draw some pictures, which make a lot more sense.
• Once $j^*$ is fixed, we can binary search on $i$ to find the final answer. This is because the matrix is increasing in $i$ (obviously). So we can binary search, and use our formula to check whether $i$ is too small or not.

References

Problem-solving techniques used:

Learning points:

• When you get stuck, spend some time looking at reasonable examples. In the contest, I spent a lot of time trying to write down observations about the problem, but with no success. I think the best approach would have been to work out a reasonable example with particular guesses for $v$, to get an idea about how to actually solve the problem. The core ideas needed to solve it became fairly "obvious" once you look at enough examples, but can be mysterious if you are simply looking at the algebra. I'll try to internalize this for the future.
• Beware of going down the wrong path. This might be impossible to detect without simply developing a better intuition. But I spent most of the contest thinking about a "SQRT Decomposition" approach. I was thinking, if $K$ is large, try one algorithm; if $K$ is small, try another. And the difference between "large" and "small" was likely going to be around $sqrt(10^9)$ or something similar. I was trying this approach because it seemed like a reasonable approach based on other problems I've solved. But it was completely wrong. Instead, I should have stopped and focused on generating correct insights about the specific problem, rather than trying to use "a specific trick" (such as SQRT Decomposition) to solve the problem. I need to get better at recognizing bad ideas.

Topics:

• Math / Formulas / Counting
• Binary Search
• Observation / Insight
• Greedy

Related problems:

Coming soon.