Problem analysis: Bidding (stage III, XXXIII OI)

Problem Statement

This is a communication task. There are two participants in the task – Algosia and Bajtek. At the beginning of the game, both receive a sequence of integers of length \(n\) with values generated pseudorandomly from the range \([1, m]\) with equal probability of each number occurring. In addition, an integer \(k\) is given. The players alternately bid increasingly larger integers (simultaneously declaring whether this is the end of the game or not). Algosia and Bajtek win if they bid the value: \[W = \left\lfloor \sum_{i=1}^n \frac{\min(a_i, b_i)}{k} \right\rfloor, \] simultaneously communicating that this is the final bid value. There will be \(t = 40\) such games within one test case, while the score will depend on the total number of games won.

Expected value of the number \(W\)

Before we proceed to solve the task, let's consider what the expected value of the number \(W\) looks like. The numbers \(a_i\) and \(b_i\) are independent random variables generated from a uniform distribution on the interval \([1, m]\). Thus, for each \(1 \leq i \leq n\) we have: \[ \mathbb{E}[\min(a_i, b_i)] = \sum_{x=1}^m x \cdot \mathbb{P}(\min(a_i, b_i) = x) = \sum_{x=1}^m x \cdot \left( \mathbb{P}(a_i = x, b_i \geq x) + \mathbb{P}(b_i = x, a_i > x) \right) = \] \[ = \sum_{x=1}^m x \cdot \left( \frac{1}{m} \cdot \frac{m - x + 1}{m} + \frac{1}{m} \cdot \frac{m - x}{m} \right) = \sum_{x=1}^m x \cdot \frac{2(m - x) + 1}{m^2} = \frac{2}{m^2} \sum_{x=1}^m (mx - x^2) + \frac{1}{m^2} \sum_{x=1}^m x = \] \[ = \frac{2}{m^2} \left( m \cdot \frac{m(m+1)}{2} - \frac{m(m+1)(2m+1)}{6} \right) + \frac{1}{m^2} \cdot \frac{m(m+1)}{2} = \frac{(m+1)(2m+1)}{6m} \approx \frac{m}{3}. \]

Using the linearity of expected value, we obtain: \[ \mathbb{E}[W] \leq \mathbb{E}\left[ \sum_{i=1}^n \frac{\min(a_i, b_i)}{k} \right] = \frac{1}{k} \sum_{i=1}^n \mathbb{E}[\min(a_i, b_i)] \approx \frac{nm}{3k}. \]

Let \(S = \sum_{i=1}^n \min(a_i, b_i)\). The solutions for all subtasks will be based on finding the exact value of the number \(S\) by raising the bid. Note that the only information a player receives from their partner is the increment of the bid amount. Therefore, we will base our communication on the values of successive increments. If the communication protocol requires too many messages or significantly increases the bid value, both players will simply overbid the value of \(W\) and lose.

Subtask 1 – \(k = 1\)

The chance that any \(a_i\), \(b_i\) will have very small values (e.g., less than \(7\)) is negligible. The players will sequentially agree on who has the smaller element value at a given position for each \(1 \le i \le n\). Both players maintain an auxiliary variable \(x\) (initially \(x = 0\) for each new position), which serves as a guaranteed lower bound. On their turn, the player analyzes their number \(v\) at the \(i\)-th position and makes one of two types of moves:

If their number \(v \ge x + 7\), they increase the bid amount by exactly \(1\). This is a safe message to the partner meaning: "my number is large enough that we can keep looking". After this move, both players simply increase \(x\) by \(1\).
Otherwise, if \(v < x + 7\), the player increases the bid by the value \(R = v - x - 1\). Due to the fact that in previous turns the partners have already confirmed having sufficiently large values, the increment \(R\) will be at least \(2\), and the bidding player is certain that their number is strictly smaller than the partner's number (because the partner just increased the bid by \(1\), so their number is greater than \(x + 6\)). Increasing the bid amount by more than one is an unambiguous signal to the other player that they are resolving this very position. The partner, seeing the increment \(R\), can easily reconstruct the exact minimum value at this position, which is exactly \(x + R + 1\). At this point, both players add the found minimum to their sums and move on to the next index.

When the players go through all \(n\) positions in this way, they already know the exact sum of minimums \(S\). The player whose turn it is can simply calculate the final result \(W = \lfloor \frac{S}{k} \rfloor\) and bid it, ending the game.

Subtask 2 – \(n = 10, m = 25\,000, k=200\)

Note that Algosia can send her numbers to Bajtek encoded in binary, starting from the most significant bit. Let's fix \(1 \le i \le n\). Then, for each \(j \in \{ \lceil \log_2(m) \rceil - 1, \dots, 1, 0 \}\) Algosia can check the value of the \(j\)-th bit in the number \(a_i\) and increase the bid by \(\texttt{bit value} + 1\) (since we must bid strictly larger values, and bits take the value \(0\) or \(1\)). In turn, Bajtek can always raise the bid by \(1\), thereby not conveying any information to Algosia. At the same time, Bajtek remembers which bit and from which number he should receive from Algosia in her next move. Then, after Algosia transmits all the bits, Bajtek knows the entire sequence \(a\), so he can easily calculate the value of \(W\) and bid it.

Let \(X\) be the bid placed by Algosia and Bajtek just before the end of a given game. It is clear that the players are able to win if and only if \(X \le W\) (otherwise they have overbid and it's too late). Let's estimate the expected value of \(X\) in this case. Since the numbers \(a_i\) are drawn with equal probability from the interval \([1, m]\), we can assume that each bit independently takes a random value as well. Let \(K = \lceil \log_2(nm)\rceil\). Then the expected value associated with sending one number is about \(K \cdot \frac{1 + 2}{2}\) due to Algosia's communication (on average, half the time a given bit will be set or cleared) and \(K \cdot 1\) due to Bajtek's messages ("empty moves"). In total, we get: \[ \mathbb{E}[X] \approx n \cdot K \cdot \left(\frac{3}{2} + 1\right). \] In turn, using the formula calculated earlier above, we see that \(\mathbb{E}[W] \approx 417\), while \(\mathbb{E}[X] \approx 375\). Such a solution wins almost all games with a large margin.

Subtask 3 – \(n = 10, m = 25\,000, k=300\)

The sad fact about the previous solution is that for every message from Algosia, there is a bid increase of \(1\) by Bajtek, which contributes nothing. Let's not completely abandon the idea of sending bits to each other, though: let the players divide the numbers in half and parallelly transmit the corresponding binary-encoded numbers to each other. For example, Algosia will send Bajtek the numbers \(a_i\) for even \(i\), and Bajtek will send Algosia \(b_j\) for odd \(j\).

Note that each of them will want to transmit the same total number of bits to the other person (that is, \(\frac{nK}{2}\)), so both will finish transmitting information at the same time. Therefore, it is not difficult to implement a strategy for transmitting these bits, since players can independently increase the bid by \(1\) or \(2\). After broadcasting all their messages, Algosia and Bajtek look at what their partner sent them. Now Algosia knows what the values are at the positions that Bajtek transmitted, and vice-versa. So Algosia now knows the value of \(s_A = \sum_{i=1}^{\frac{n}{2}} \min(a_{2i}, b_{2i})\). Bajtek, in turn, knows \(s_B = \sum_{i=1}^{\frac{n}{2}} \min(a_{2i-1}, b_{2i-1})\).

Now it is enough for Algosia to send the binary encoded value of \(s_A\) to Bajtek in an analogous way. Bajtek can raise the bid by \(1\) while waiting for Algosia to send him all the bits of \(s_A\). After receiving this information, Bajtek already knows the value of \(s_B\) and \(s_A\), so he can calculate \(S = s_A + s_B\) and bid the value \(W = \lfloor \frac{S}{k} \rfloor\).

Let's estimate the expected value of \(X\) in this case. Each player sends \(\frac{nK}{2}\) bits, and then Algosia sends another \(K\) bits related to the value of \(s_A\). We obtain: \[ \mathbb{E}[X] \approx nK \cdot \frac{3}{2} + K \cdot \left(\frac{3}{2} + 1\right) . \] In turn, using the formula derived above, we have that \(\mathbb{E}[W] \approx 278\) and \(\mathbb{E}[X]\approx 262\), which allows us to score full points in this subtask.

Subtask 6 – \(k = 4500\)

Method I – improving the above solution

Note that in the above solution, the players mindlessly send all the bits of their numbers at positions of a specific parity. Let's look at the situation where Algosia sends the bits of the number \(a_1\) to Bajtek in order from the most significant bits. At the same time, Bajtek sends Algosia the bits of the number \(b_2\), also in order from the most significant bits. However, Bajtek also knows the value of \(b_1\), so at the first possible moment when Algosia sends him the \(j\)-th bit of \(a_1\), and it differs from the \(j\)-th bit of \(b_1\), Bajtek can react and ask Algosia to stop sending the bits of \(a_1\). Raising the bid by \(3\) will serve this purpose. Then Algosia will know that Bajtek has a different \(j\)-th bit than her, so if her \(j\)-th bit is \(0\), then Bajtek has \(1\) at this position, and if her \(j\)-th bit is \(1\), then Bajtek has \(0\) at this position. In both cases, both players know who has the smaller value at this position. Algosia can therefore move on to transmitting the bits of the number \(a_3\) and so on. Symmetrically, Algosia will react to differing bits of numbers sent by Bajtek.

In this solution, special care should be taken with the fact that due to the randomness of the numbers \(a_i\) and \(b_i\), the players will not necessarily finish sending bits to each other at the same moment. Because of this, it's necessary to have a special message informing the other player that they have already finished transmitting all their bits. This can be done, for example, by raising the bid by \(4\), and then sending only "empty" moves that increase the bid by \(1\) or inform the partner about differing bits, as described above.

In the end, both players again know their sums \(s_A\) and \(s_B\), so Algosia can send Bajtek the binary encoded value of \(s_A\) in an analogous way as before, and Bajtek, upon receiving this information, already knows the value of \(S = s_A + s_B\) and can bid the value \(W = \lfloor \frac{S}{k} \rfloor\).

Let's again estimate the expected value of \(X\) in this case. Let's fix \(1 \le i \le n\). Assume that Algosia is sending the bits of the number \(a_i\). Note that the probability that the first \(k\) bits of the numbers \(a_i, b_i\) are the same is \(\frac{1}{2^k}\). Thus, the probability that Algosia will have to transmit exactly \(j\) bits is also \(\frac{1}{2^{j}}\) for \(1 \le j \le K\) (because Algosia will send those bits of \(a_i\) that match the bits of \(b_i\) and one additional bit, after receiving which it will be decided who has \(\min(a_i, b_i)\)). We thus obtain that the expected value associated with sending one number is roughly: \[ \sum_{j=1}^K \frac{1}{2^j} \cdot j \cdot \frac{3}{2} + 3 \approx 6 \]

In turn, the expected number of "empty" moves comes from the difference in the times the players finish transmitting bits. Without going into mathematical details, it is: \(\sqrt{\frac{4 * n}{\pi}} \approx 35.7\). Intuitively, however, we can understand that since the bits in all numbers are random, the players should usually finish sending bits to each other at similar times.

Therefore, the expected value associated with transmitting the result and the number \(s_A\) or \(s_B\) is: \[ \mathbb{E}[X] = 6n + K \cdot \left(\frac{3}{2} + 1\right) + 35.7 \approx 6102. \] In turn, using the formula derived at the beginning, we have that \(\mathbb{E}[W] \approx 6666\) for \(k=5000\).

Method II – binary search

The previous solutions sent the bits of the numbers \(a_i, b_i\) to each other. Let's now try a slightly different approach. Let Algosia and Bajtek jointly communicate who has the smaller of the numbers at index \(i\) using binary search. We now maintain a number \(x\), initially equal to \(\frac{m}{2}\). The communication rule is as follows: Algosia and Bajtek will inform each other whether their number (respectively \(a_i\) or \(b_i\)) is greater than or not greater than \(x\). Let raising the bid by \(1\) mean that the player's number is strictly greater than \(x\), and raising it by \(2\) – that it is less than or equal to \(x\). We have the following possibilities:

If the sum of both players' bid increases is \(3\), then the player who raised the bid by \(1\) possesses a number less than or equal to \(x\), and consequently a number smaller than the partner's number. The players can now move on to considering the numbers at the \(i+1\)-th position. Such a situation occurs with a probability of \(\frac{1}{2}\).
Both players raised the bid by \(1\) or \(2\) simultaneously. Let's assume without loss of generality the first case. Then both players have numbers \(a_i, b_i\) strictly greater than \(x\). Therefore, we can simultaneously update the intervals defining the ranges for binary search for both players and continue such communication further.

Let's re-estimate the expected value of such a solution. Let \(T\) be a random variable describing the process described above for a certain fixed index \(1 \le i \le n\). Then with a probability of \(\frac{1}{2}\) and after a bid increase of \(3\), the process of resolving the owner of the minimum ends. Otherwise, with an equal probability of \(\frac{1}{4}\), the bid increases by \(2\) or by \(4\) and the process continues. We thus obtain the equation: \[ \mathbb{E}[T] = \frac{1}{2} \cdot 3 + \frac{1}{4} \cdot (2 + \mathbb{E}[T]) + \frac{1}{4} \cdot (4 + \mathbb{E}[T]), \] from which it easily follows that \(\mathbb{E}[T] = 6\). Therefore, the expected value of \(X\) in this case also amounts to \(6n + K \cdot \left(\frac{3}{2} + 1\right) \approx 6042\), which gives similar results to the previous solution, but is much simpler to implement.

Further optimizations

To score the full pool of points, Algosia and Bajtek must limit the expected bid increase from \(6n\) to about \(4.5n\) during the first phase of resolving who has the minimum at each position. This can be achieved using two optimizations of the above binary search solution: combining messages and changing the search interval division ratio.

Optimization 1 (subtask 8, \(k = 6500\)) – Combining multiple messages into one

To understand this optimization, let's trace a standard step of binary search. Usually, Algosia checks her number against the middle of the interval (let's denote it as \(mid\)) and sends this information to Bajtek. Next, Bajtek checks his number against the same \(mid\) and sends the result back to Algosia. Only after these two bids do both fully know the result, can narrow down the interval, and jointly calculate a new, subsequent \(mid\). This means that two bids are performed for each binary search step.

Instead, players can "interleave" their messages. Let's assume it's Bajtek's turn. Algosia, in her previous move, has already passed him her answer for the current \(mid\). Bajtek now does two things in a single move:

He checks his own number against the current \(mid\). Since he already knows Algosia's answer from the previous turn, this information completely resolves the current step. Bajtek already knows how the interval should be narrowed down and can independently calculate a new, next \(mid'\) for the subsequent step of this binary search.
Instead of waiting for Algosia to send the appropriate information about the relative value of \(a_i\) with respect to \(mid'\), Bajtek immediately checks his number against the newly calculated \(mid'\).

In his move, Bajtek thus encodes two pieces of information: his answer for the old \(mid\) (which allows Algosia to update the interval) and his answer for the new \(mid'\) (which immediately starts a new step). Since each answer takes one of two values (less-than-or-equal or greater), this gives a total of 4 combinations. The player therefore bids, declaring a bid increase by a value from the set \(\{1, 2, 3, 4\}\).

When Algosia receives this message, she reads Bajtek's result for the old \(mid\) from it, updates her interval herself, and then reads Bajtek's answer for the new \(mid'\), which allows her to immediately proceed to point 1 above. Thanks to this, every single bid by the partner advances the joint search by one full step forward!

Estimation of the expected value for the first optimization

Let's consider how this clever compression of messages affects the total expected increase in the bid amount. Since in standard binary search we always divide the interval exactly in half, the probability that the player's number is in the lower half (LOWER) is \(\frac{1}{2}\), just as it is in the upper half (HIGHER).

Since both variants are always equally probable, each of the \(4\) combinations encoded in the player's message has the same probability of occurrence, equal to \(\frac{1}{4}\). The expected bid increase in just one step is therefore: \(\frac{1 + 2 + 3 + 4}{4} = \frac{10}{4} = 2.5\).

When does the search for a given index end? The search comes to an end exactly when the players "miss" each other with their answers – that is, they fall into the (LOWER, HIGHER) or (HIGHER, LOWER) case. Then it is unambiguously known who has the smaller number. The probability of such a situation in a single step is \(\frac{1}{2}\).

Since the chance to resolve an index in each step is \(\frac{1}{2}\), we can calculate the expected number of bid increases (random variable \(T\)) from the formula: \[\mathbb{E}[T] = 2.5 + \frac{1}{2}\mathbb{E}[T] \implies \mathbb{E}[T] = 5.\]

Therefore, the total expected value \(\mathbb{E}[X] = 5n + \frac{5}{2} K \approx 5042\), whereas for \(k=6500\) we have \(\mathbb{E}[W] \approx 5128\), thus this solution wins all games in this subtask with a safe margin.

Second optimization (and full solution): asymmetric division

In standard binary search, we set the \(mid\) value exactly in the middle of the interval. However, because of this, the bid values \(1, 2, 3, 4\) are equally probable. What if, instead, we divide the interval asymmetrically into two parts, so that values \(1\) and \(2\) are bid more frequently, and \(3\) and \(4\) less frequently?

Let the binary search interval therefore be divided such that the LOWER region covers \(p\%\) of the interval, and the HIGHER region \((1-p)\%\). We will choose the value \(p\) later to optimize the expected value of the sum of bid increases. Let's assume our encoding looks as follows:

Increment 1: both landed in LOWER. Probability of such a situation: \(p^2\).
Increment 2: partner in LOWER, player in HIGHER. Probability: \(p(1-p)\).
Increment 3: partner in HIGHER, player in LOWER. Probability: \(p(1-p)\).
Increment 4: both landed in HIGHER. Probability: \((1-p)^2\).

The expected increase of the bid in one step is therefore: \[1 \cdot p^2 + 2 \cdot p(1-p) + 3 \cdot p(1-p) + 4 \cdot (1-p)^2 = 4 - 3p\] When does the comparison of values at a given index end? When players fall into the (LOWER, HIGHER) or (HIGHER, LOWER) case. The chance of this is \(2p(1-p)\). In that case, the expected sum of bid increases to finish processing one index (random variable \(T\)) is: \[\mathbb{E}[T] = \frac{4-3p}{2p(1-p)},\] which reaches its local minimum on the interval \([0, 1]\) for \(p = \frac{2}{3}\). Then \(\mathbb{E}[T] = 4.5\).

Thus we obtain that \(\mathbb{E}[X] \approx 4542\) and \(\mathbb{E}[W] \approx 4761\), which allows us to score the maximum number of points with a probability close to \(1\):)