Google Code Jam Archive — Round 1B 2022 problems


Round 1B kicked off with a favorite Code Jam theme in Pancake Deque which had contestants’ mouths watering as they worked to serve pancakes from a deque in the optimal order. Next, Controlled Inflation required some optimizations then dynamic programming as contestants helped quickly inflate everyone’s sports balls and giant parade balloon animals. Finally, Asedatab truly put contestants to the test as they fought against an adversarial judge while trying to reset a database’s record value to 0.

andrewgu was the first one with a perfect score, and that gave them the top position in the final standings. georgerapeanu and Iftekhar_Hakim_K rounded out the top 3 with only a few more minutes of penalty. Just over 100 people managed a perfect score. Over 9000 people scored some points out of the more than 11000 that submitted a solution.

When the hidden results were revealed, the contestant in 1500th place had 85 points, which is the unofficial cutoff for advancing. The Code Jam team will spend a few days finalizing the results. You can have fun reading the analyses in the problem pages while you wait.

Congratulations to all advancers, and for everyone else, there is one more chance to advance to Round 2 in less than a week. Be sure to check the schedule to find out when Round 1C is happening in your timezone. See you there!


Pancake Deque: Written by Pablo Heiber. Prepared by Priyam Khandelwal.

Controlled Inflation: Written by Mohit Jain. Prepared by Ulises Mendez Martinez.

ASeDatAb: Written and prepared by Xiongqi (Parker) Zhang.

Solutions and other problem preparation and review by Aditya Mishra, Andy Zakharov, Antonio Mendez, Chill Chiu, Chun-nien Chan, Darcy Best, Hsin-cheng Hou, Ian Tullis, Liang Bai, Md Mahbubul Hasan, Mohamed Yosri Ahmed, Nafis Sadique, Nikita Rungta, Nour Yosri, Pablo Heiber, Ritesh Kumar, Sanyam Garg, Sudarsan Srinivasan, Swapnil Gupta, Swapnil Mahajan, Timothy Buzzelli, Ulises Mendez Martinez, Xiang Yao, and Xiongqi (Parker) Zhang.

Analysis authors:

  • Pancake Deque: Hsin-cheng Hou.
  • Controlled Inflation: Andy Zakharov.
  • ASeDatAb: Ian Tullis, Timothy Buzzelli, and Xiongqi (Parker) Zhang.

A. Pancake Deque


Pancakes are normally served in stacks, but the Infinite House of Pancakes embraces change! The restaurant's new advertising hook is to serve the pancakes from a deque, or double-ended queue.

You are a server at the restaurant, and your job is to serve every pancake in the deque. Customers will arrive one at a time, and each one gets a single pancake. You must serve each customer either the leftmost or rightmost pancake in the deque; the choice is yours. When a pancake is served, it disappears from the deque, exposing the pancake that was next to it. Or, once there is only one pancake left, your only choice is to serve that one, and then your job is complete!

Illustration of Sample #2.

Each pancake has a deliciousness level. Because customers do not get to choose which pancakes they get, each customer only has to pay for their pancake if it is at least as delicious as each of the pancakes that all of the previous customers got. (The first customer always pays for their pancake, since in that case there are no previous customers.)

How many customers will pay for their pancake, if you serve the pancakes in an order that maximizes that number?


The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ test cases follow. Each test case is described with two lines. The first line of a test case contains a single integer $$$\mathbf{N}$$$, the number of pancakes in the pancake deque. The second line of a test case contains $$$\mathbf{N}$$$ integers $$$\mathbf{D_1}, \mathbf{D_2}, \dots, \mathbf{D_N}$$$, where $$$\mathbf{D_i}$$$ is the deliciousness level of the $$$i$$$-th pancake from the left in the deque.


For each test case, output one line containing Case #$$$x$$$: $$$y$$$, where $$$x$$$ is the test case number (starting from 1) and $$$y$$$ is the number of customers who pay for their pancakes, if you serve the pancakes in an order that maximizes that number.


Time limit: 20 seconds.
Memory limit: 1 GB.
$$$1 \le \mathbf{T} \le 100$$$.
$$$1 \le \mathbf{D_i} \le 10^6$$$, for all $$$i$$$.

Test Set 1 (Visible Verdict)

$$$2 \le \mathbf{N} \le 20$$$.

Test Set 2 (Visible Verdict)

$$$2 \le \mathbf{N} \le 100$$$.

Test Set 3 (Hidden Verdict)

$$$2 \le \mathbf{N} \le 10^5$$$.


Sample Input
content_copy Copied!
1 5
1 4 2 3
10 10 10 10 10
7 1 3 1000000
Sample Output
content_copy Copied!
Case #1: 2
Case #2: 3
Case #3: 5
Case #4: 2

In Sample Case #1, there are two possible orders in which you can serve the pancakes. If you serve the pancake with deliciousness level $$$5$$$ first, only that one is paid for. If you serve the pancake with deliciousness level $$$1$$$ first, both are paid for.

Sample Case #2 is the image shown in the problem statement. The following are the possible orders (by deliciousness level) in which the pancakes can be served. The underlined pancakes are the ones that customers pay for.

  • $$$\underline{1}, \underline{4}, 2, 3$$$
  • $$$\underline{1}, \underline{4}, 3, 2$$$
  • $$$\underline{1}, \underline{3}, \underline{4}, 2$$$
  • $$$\underline{1}, \underline{3}, 2, \underline{4}$$$
  • $$$\underline{3}, 1, \underline{4}, 2$$$
  • $$$\underline{3}, 1, 2, \underline{4}$$$
  • $$$\underline{3}, 2, 1, \underline{4}$$$
  • $$$\underline{3}, 2, \underline{4}, 1$$$

As you can see, there are some orders in which $$$3$$$ pancakes are paid for, and none in which all $$$4$$$ are.

In Sample Case #3, all pancakes are paid for regardless of the serving order.

In Sample Case #4, regardless of which pancake you serve first, the two in the middle will never be paid for. The best you can do is serve the pancake with deliciousness 7 before the pancake with deliciousness 1000000.

B. Controlled Inflation


The lines at the air pump at your gas station are getting too long! You want to optimize the process to help customers more quickly inflate their tires, sports balls, giant parade balloon animals, and other products.

The pump is automatic: you set the pressure to a specific number of pascals and plug the pump into the inflatable product, and it will inflate as needed to that exact pressure. There are only two buttons on the pump: up and down. They increase and decrease the target pressure, respectively, by exactly $$$1$$$ pascal.

Image of air pump and soccer ball.

There is a line of $$$\mathbf{N}$$$ customers, each of whom brings exactly $$$\mathbf{P}$$$ products that they need to get inflated by the pump. You know the target pressure of each product. You can inflate the products from a customer in any order you want, but you cannot change the order of the customers. Specifically, you must inflate all products from the $$$i$$$⁠-th customer before inflating any from the $$$(i + 1)$$$⁠-th customer. In between handling two products, if those two products have different target pressures, you need to use the buttons on the pump.

The pump is initially set to $$$0$$$ pascals, and it can be left at any number after all products of all customers have been inflated. If you order the products of each customer optimally, what is the minimum number of button presses you need?


The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ test cases follow. Each test case starts with a line containing two integers, $$$\mathbf{N}$$$ and $$$\mathbf{P}$$$: the number of customers and the number of products each customer brings, respectively. Then, $$$\mathbf{N}$$$ lines follow. The $$$i$$$-th of these lines contains $$$\mathbf{P}$$$ integers $$$\mathbf{X_{i,1}}, \mathbf{X_{i,2}}, \dots, \mathbf{X_{i,P}}$$$, representing that the $$$j$$$-th product that the $$$i$$$-th customer brings has a target pressure of $$$\mathbf{X_{i,j}}$$$ pascals.


For each test case, output one line containing Case #$$$x$$$: $$$y$$$, where $$$x$$$ is the test case number (starting from 1) and $$$y$$$ is the minimum number of button presses needed to inflate all products according to their specified pressures.


Time limit: 5 seconds.
Memory limit: 1 GB.
$$$1 \le \mathbf{T} \le 100$$$.
$$$1 \le \mathbf{X_{i,j}} \le 10^9$$$, for all $$$i, j$$$.

Test Set 1 (Visible Verdict)

$$$2 \le \mathbf{N} \le 10$$$.
$$$2 \le \mathbf{P} \le 3$$$.

Test Set 2 (Hidden Verdict)

$$$2 \le \mathbf{N} \le 1000$$$.
$$$2 \le \mathbf{P} \le 100$$$.


Sample Input
content_copy Copied!
3 3
30 10 40
20 50 60
60 60 50
5 2
1 1000000000
500000000 1000000000
1 1000000000
500000000 1
1 1000000000
Sample Output
content_copy Copied!
Case #1: 110
Case #2: 4999999996

In Sample Case #1, an optimal way to use the pump is:

  1. press up $$$10$$$ times, setting the pump to $$$10$$$; pump the product (from customer 1) that needs $$$10$$$ pascals,
  2. press up $$$30$$$ times, setting the pump to $$$40$$$; pump the product (from customer 1) that needs $$$40$$$ pascals,
  3. press down $$$10$$$ times, setting the pump to $$$30$$$; pump the product (from customer 1) that needs $$$30$$$ pascals,
  4. press down $$$10$$$ times, setting the pump to $$$20$$$; pump the product (from customer 2) that needs $$$20$$$ pascals,
  5. press up $$$30$$$ times, setting the pump to $$$50$$$; pump the product (from customer 2) that needs $$$50$$$ pascals,
  6. press up $$$10$$$ times, setting the pump to $$$60$$$; pump the product (from customer 2) and the two products (from customer 3) that need $$$60$$$ pascals, and finally
  7. press down $$$10$$$ times, setting the pump to $$$50$$$; pump the product (from customer 3) that needs $$$50$$$ pascals.

This is a total of $$$110$$$ button presses.

In Sample Case #2, notice that the answer can be larger than $$$2^{32}$$$.

C. ASeDatAb


A research consortium has been looking for the best possible database for three years, but they are still having problems. The database stores values as records that hold $$$8$$$-bit binary strings. Unfortunately, their implementation of the function to set the value of a record is flawed.

Each record of the database is an $$$8$$$⁠-bit binary string. The bits of the binary string are indexed from $$$0$$$ to $$$7$$$ from left to right. When an instruction to set a specific record to a new value $$$V$$$ is received, instead of setting the value to $$$V$$$ the database does the following:

  1. Choose an integer $$$r$$$ between $$$0$$$ and $$$7$$$, inclusive, and let $$$W$$$ be like $$$V$$$ but rotated by $$$r$$$ to the right. That is, the $$$((i + r) \bmod 8)$$$⁠-th bit of $$$W$$$ is the $$$i$$$⁠-th bit of $$$V$$$.
  2. Replace the current value $$$X$$$ of the record with $$$X$$$ XOR $$$W$$$. That is, the new value of the record has a $$$1$$$ as its $$$i$$$⁠-th bit if and only if the $$$i$$$⁠-th bits of $$$X$$$ and $$$W$$$ are different.
  3. Finally, return the number of bits that are $$$1$$$ in the new value to the user.

Luckily, it turns out that no matter what the initial value is or what rotation values the database chooses, it is always possible to reset the value of a record to have all bits be $$$0$$$ with no more than $$$300$$$ uses of this operation. Implement a program to interact with the database that does this.

Input and output

This is an interactive problem. You should make sure you have read the information in the Interactive Problems section of our FAQ.

Initially, your program should read a single line containing an integer $$$\mathbf{T}$$$, the number of test cases. Then, $$$\mathbf{T}$$$ test cases must be processed.

At the beginning of each test case, the record in the database is set to a value that is not 00000000. In each test case, your program must process up to $$$300$$$ exchanges.

The $$$i$$$⁠-th exchange starts with you outputting a single line containing a single $$$8$$$⁠-bit binary string to be used as the value $$$V$$$ for the operation above. Then, the judge program performs the operation as described and sends you a single line containing a single integer $$$\mathbf{N_i}$$$ representing the number of bits that are equal to $$$1$$$ in the updated value of the record.

  • If $$$\mathbf{N_i} = 0$$$, it means that you have succeeded and you must start the next test case, or finish the program if it was the last one.
  • If $$$\mathbf{N_i} = -1$$$ it means that this was the $$$300$$$-th exchange of the test case but the record never got to a value of all zeroes, so the test is failed. No further test cases will be processed.
  • If $$$1 \le \mathbf{N_i} \le 8$$$, it means that the updated value of the record has $$$\mathbf{N_i}$$$ ones and you may proceed to the next exchange to keep trying to make it contain only zeroes.

Your solution is considered correct if and only if you succeed in setting the value of the record to 00000000 for all test cases.

If the judge receives an invalidly formatted or invalid line from your program at any moment, the judge will print a single number $$$-1$$$ and will not print any further output. If you receive a $$$-1$$$, you must finish correctly and without exceeding the time or memory limits to receive a Wrong Answer judgement. Otherwise, you will receive a judgement informing the exceeded resource or the incorrect termination condition.


Time limit: 10 seconds.
Memory limit: 1 GB.
$$$1 \le \mathbf{T} \le 100$$$.
$$$-1 \le \mathbf{N_i} \le 8$$$ for all $$$i$$$.

Test Set 1 (Visible Verdict)

The initial value of the record is chosen uniformly at random from all $$$8$$$-bit binary strings that are not 00000000.

Each rotation value is chosen uniformly at random, and independently of all previous choices and interactions.

Test Set 2 (Visible Verdict)

The judge is adversarial. This means, among other things, that the judge can change the initial value or rotation values as long as it is consistent with all interactions. The initial value is guaranteed to never be 00000000.

Testing Tool

You can use this testing tool to test locally or on our platform. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. For more information, read the instructions in comments in that file, and also check out the Interactive Problems section of the FAQ.

Instructions for the testing tool are included in comments within the tool. We encourage you to add your own test cases. Please be advised that although the testing tool is intended to simulate the judging system, it is NOT the real judging system and might behave differently. If your code passes the testing tool but fails the real judge, please check the Coding section of the FAQ to make sure that you are using the same compiler as us.

Download testing tool

Sample Interaction
00011001 has $$$3$$$ ones.
Judge informs you that there are no ones in the record, so this case is complete.

Analysis — A. Pancake Deque

Test Set 1

For the first test set, we could try a brute force solution for this problem. Given a remaining deque of pancakes $$$\mathbf{D}$$$, we could choose to serve the next customer from either the front or back of the deque. Meanwhile, we could update the maximum deliciousness of the pancakes served every time we decided to serve a pancake out. We could use a recursive brute force method to simulate the process.

Given that every time we have two choices for serving the pancake (either the first or the last one) , the overall time complexity of the approach will be $$$O(2^\mathbf{N})$$$, which is sufficient to solve the first test set.

Notice that the brute force method can be improved by using memoization to record the current optimal solution for a partial deque. There are $$$\binom{\mathbf{N}}{2} + \mathbf{N} = \frac{\mathbf{N}\cdot(\mathbf{N} + 1)}{2}$$$ partial deques in total to take into consideration. Therefore, this will reduce the time complexity down to $$$O(\mathbf{N}^2)$$$.

Test Set 2

The same approach cannot be applied to the second test set, since it will result in a time limit exceed. Therefore we need a more clever way other than trying to serve the pancakes brute-force. We could quickly make an observation that, if the deliciousness of the pancakes we could serve at some point are $$$\mathbf{D}_\text{left}$$$ and $$$\mathbf{D}_\text{right}$$$, it will always be better to serve the one with less deliciousness. To prove this, we could do a quick analysis. For simplicity, let us assume that $$$\mathbf{D}_\text{left} \le \mathbf{D}_\text{right}$$$ , and denote $$$\mathbf{D}_\text{max}$$$ as the greatest deliciousness of the pancakes served out so far. If $$$\mathbf{D}_\text{left} \lt \mathbf{D}_\text{max}$$$, this means that the pancake will be served out free no matter when we serve it, so we could easily serve it out now and will not affect our final answer. Otherwise, since $$$\mathbf{D}_\text{left} \le \mathbf{D}_\text{right}$$$ it will always be better to serve $$$\mathbf{D}_\text{left}$$$ first, or else $$$\mathbf{D}_\text{max}$$$ will be updated to at least $$$\mathbf{D}_\text{right}$$$. In that case $$$\mathbf{D}_\text{left}$$$ will be served out free. Therefore we could summarize into a criteria for serving pancakes: serve out $$$\min(\mathbf{D}_\text{left}, \mathbf{D}_\text{right})$$$, and update $$$\mathbf{D}_\text{max}$$$ if needed. For each customer, this criteria takes $$$O(1)$$$ time to perform, therefore the total time complexity of this approach is $$$O(\mathbf{N})$$$.

Test Data
info We recommend that you practice debugging solutions without looking at the test data.

Analysis — B. Controlled Inflation

The key observation is that for each customer, either the increasing or decreasing order of target pressures will produce an optimal solution. That is, no other permutation of products will result in a strictly lower number of button presses. Let's prove this.

First, note that this is true for each individual customer $$$i$$$. At one point in the process, the pump will be at the minimal pressure $$$\text{Min}_i = \min_{j=1..\mathbf{P}} \mathbf{X_{i,j}}$$$. At another point, the pump will be at the maximal pressure $$$\text{Max}_i = \max_{j=1..\mathbf{P}} \mathbf{X_{i,j}}$$$. This means that we have to reach both of them, so we will always have to press the buttons at least $$$\text{Max}_i - \text{Min}_i$$$ times, no matter the order. This can be achieved by arranging the products in either increasing or decreasing order of their target pressures.

Now, the pressure also has to be adjusted between customers, which requires pressing the buttons. Let's see why all other product orders do not improve the answer by consindering how many button presses between customers we can save. While processing the $$$i$$$-th customer, the pump will be at $$$\text{Min}_i$$$ at one point, at $$$\text{Max}_i$$$ at another point, and finally we will leave it at the pressure of the last product, $$$\mathbf{X_{i,last}}$$$. This requires at least $$$(\text{Max}_i - \text{Min}_i) + (\text{Max}_i - \mathbf{X_{i,last}})$$$ button presses, but the potential saving is at most $$$(\text{Max}_i - \mathbf{X_{i,last}})$$$, which is the least amount of additional button presses we needed to do. If the pump reaches the maximum pressure before reaching the minimum pressure, a similar relationship holds, meaning this different order does not improve the answer.

Now that we know that it is enough to consider only the increasing and decreasing orders, we will only keep track of $$$\text{Min}_i$$$ and $$$\text{Max}_i$$$ for each customer. For the test set with the visible verdict, it is enough to check all $$$2^\mathbf{N} \le 1024$$$ possibilities of choosing the increasing or decreasing order for each customer and simulate the process.

To do this more efficiently, we can use dynamic programming. Let $$$dp_{i,0}$$$ be the answer after processing $$$i$$$ customers where the products for the last customers are arranged in increasing order. Similarly, let $$$dp_{i,1}$$$ be the answer after the first $$$i$$$ customers with the products for the last one arranged in decreasing order. We will also keep track of the pressure we left the pump at, $$$l_0$$$ and $$$l_1$$$ for the increasing and decreasing orders corresponsindly. Clearly, $$$dp_{0,0} = dp_{0,1} = 0$$$ and $$$l_0 = l_1 = 0$$$ (the starting pressure). Now, assume $$$dp$$$ is calculated up to $$$i$$$. The following equations give the values for the next customer:

$$$dp_{i+1,0} = \min \begin{pmatrix} dp_{i,0} + |l_0 - \text{Min}_{i+1}| + (\text{Max}_{i+1} - \text{Min}_{i+1}), \\ dp_{i,1} + |l_1 - \text{Min}_{i+1}| + (\text{Max}_{i+1} - \text{Min}_{i+1}) \end{pmatrix}$$$

$$$dp_{i+1,1} = \min \begin{pmatrix} dp_{i,0} + |l_0 - \text{Max}_{i+1}| + (\text{Max}_{i+1} - \text{Min}_{i+1}), \\ dp_{i,1} + |l_1 - \text{Max}_{i+1}| + (\text{Max}_{i+1} - \text{Min}_{i+1}) \end{pmatrix}$$$

And update the last pressures: $$$l_0 = \text{Max}_{i+1}$$$, $$$l_1 = \text{Min}_{i+1}$$$.

Test Data
info We recommend that you practice debugging solutions without looking at the test data.

Analysis — C. ASeDatAb

Test Set 1

Whatever we try to do, the randomly-rotating judge in this test set might scuttle our plans. But we can fight randomness with randomness!

First, we can observe that if the judge ever tells us that the record has eight $$$1$$$ bits, we have all but won (as long as we have at least one interaction left). This is because we can then submit $$$11111111$$$, and no matter how the judge rotates it, the final result of XORing will be $$$00000000$$$. Because of this, if we are ever told that the record has more than four $$$1$$$s, it should be to our advantage to aim for eight 1s rather than zero 1s!

For now let's suppose the judge tells us there are $$$b$$$ bits in the record, for some $$$b$$$ between $$$1$$$ and $$$4$$$. (We will handle the other cases by symmetry, as explained above.) Let's do the following: choose a string with $$$b$$$ bits uniformly at random, then send that. Now it doesn't really matter how the judge rotates our string -- whatever the resulting rotated string is, we were just as likely to pick that in the first place.

What are the possible outcomes? Suppose that $$$b=2$$$. Then we have a $$$\frac{1}{{8 \choose 2}} = \frac{1}{28}$$$ chance of flipping both of the two $$$1$$$s (and therefore winning!), a $$$\frac{{2 \choose 1}{6 \choose 1}}{{8 \choose 2}} = \frac{12}{28}$$$ chance of flipping one of the two $$$1$$$s and some innocent $$$0$$$ (and thus being back in the same $$$b=2$$$ boat), and a $$$\frac{{2 \choose 0}{6 \choose 2}}{{8 \choose 2}} = \frac{15}{28}$$$ chance of missing both $$$1$$$s and creating two new $$$1$$$s (taking us to $$$b = 4$$$). This may not seem too promising so far, but hang on...

Doing the same sort of analysis for the state $$$b=4$$$, we find that we end up at one of $$$b = 0, 2, 4, 6, 8$$$, with probabilities $$$\frac{1}{70}, \frac{16}{70}, \frac{36}{70}, \frac{16}{70}, \frac{1}{70}$$$, respectively. But, as we mentioned, being at $$$b=6$$$ is just the same as being at $$$b=2$$$. If we are at $$$b=6$$$, we can try to use two $$$1$$$s to flip the two 0s, in the hopes of reaching $$$11111111$$$. Similarly, being at $$$b=8$$$ is (essentially) as good as being at $$$b=0$$$. So we will lump those two probabilities into $$$b=2$$$ and $$$b=0$$$, respectively, getting transition probabilities to $$$b=0, 2, 4$$$ of $$$\frac{1}{35}, \frac{16}{35},$$$ and $$$\frac{18}{35}$$$, respectively.

Notice that if $$$b$$$ is even, we are trapped in the even-$$$b$$$-verse, randomly walking (according to those transition probabilities) until we either reach $$$b=0$$$ or reach $$$b=8$$$ or we run out of guesses. And if we are not in the even-$$$b$$$-verse, one round of sending exactly $$$min(b, 8-b)$$$ randomly placed $$$1$$$s will get us there; we leave this as an exercise. So our strategy can be to spend up to two rounds getting into the even-$$$b$$$-verse, up to 297 rounds wandering, and up to one round possibly turning a $$$11111111$$$ into a $$$00000000$$$.

What are the chances that we will succeed in those 297 rounds? Observe that until we reach a winning state ($$$00000000$$$ or $$$11111111$$$), we are always in one of two other states: $$$b=2$$$ (lumped in with $$$b=6$$$), or $$$b=4$$$. In the former case, we have a $$$\frac{1}{28}$$$ chance of transitioning to a winning state, and in the latter case, that chance is $$$\frac{1}{35}$$$. Just for ease of argument, let's pessimistically guess that we get stuck hanging around in the less advantageous $$$b=4$$$ state. But then to not win, we would still have to fail our $$$\frac{1}{35}$$$ lottery 297 times. The probability of that is $$$(1 - \frac{1}{35})^{297} \approx 0.0002$$$. So we have at least a $$$99.98\%$$$ chance of succeeding with this strategy, and that is an overly conservative lower bound!

(If you're curious about the actual success probability, we can conservatively assume that we always start our journey at $$$b=4$$$, and then find the upper left cell of $$$\begin{pmatrix} 1 & \frac{1}{28} & \frac{1}{35}\\ 0 & \frac{12}{28} & \frac{16}{35}\\ 0 & \frac{15}{28} & \frac{18}{35}\end{pmatrix}^{297}\begin{pmatrix}0\\ 0\\ 1\end{pmatrix}$$$, which turns out to be about $$$0.99993 \approx 99.993\%$$$).

Of course, we still have to pass all 100 test cases in Test Set 1, and the probability of this is a bit smaller: $$$\approx 0.99993^{100} \approx 0.993$$$. But $$$99.3\%$$$ isn't so bad, and if we see an unlucky failure with this method, we can easily get another independent try by changing our code's random seed, since we have control over that source of randomness.

Test Set 2

In Test Set 2, the judge does not behave randomly and can and will choose rotation values that keep us away from reaching our goal. So, we need a strategy that is guaranteed to reset the record to all zeroes.

One way to do this is to consider the current state. Let's define a state as the set of all possible values the record could currently be set to. A key observation here is that two values that are cyclic rotations of each other are equivalent. Therefore, we can eliminate these duplicates from our sets. After the first exchange, we know how many bits are set to $$$1$$$ in the record. Thus, all potential states only have values that have the same bit count.

We can enumerate all possible values for each bit count (while removing duplicates that are cyclic rotations of another value). If we do this, we find the following sets of potential values:

  • 0 bits: $$$\{00000000\}$$$
  • 1 bit: $$$\{00000001\}$$$
  • 2 bits: $$$\{00000011, 00000101, 00001001, 00010001\}$$$
  • 3 bits: $$$\{00000111, 00001011, 00001101, 00010011, 00010101, 00011001, 00100101\}$$$
  • 4 bits: $$$\{00001111, 00010111, 00011011, 00011101, 00100111, 00101011, 00101101, 00110011, 00110101, 01010101\}$$$
  • 5 bits: $$$\{00011111, 00101111, 00110111, 00111011, 00111101, 01010111, 01011011\}$$$
  • 6 bits: $$$\{00111111, 01011111, 01101111, 01110111\}$$$
  • 7 bits: $$$\{01111111\}$$$
  • 8 bits: $$$\{11111111\}$$$

Notice that the largest of these sets (4 bits) has only 10 elements. Thus, there are at most $$$2^{10} = 1024$$$ unique states for when we have 4 bits on. This is small enough to consider all possible states and so something similar to a BFS (breadth-first search) from the state with all zeroes.

Specifically, we can consider the set of all states that we know can be forced to reach all zeroes (initially just the solved state where the record is 00000000). Then, for a given state, $$$A$$$, we can consider trying all possible values for $$$V$$$ and simulate the results of the $$$8$$$ different rotation values the judge could choose. Grouping those by their bitcounts gives us the possible states that $$$A$$$ could transition to for a specific value of $$$V$$$. If all of those states are ones we have processed, then we know that when state $$$A$$$, we can use this value of $$$V$$$ to get us closer to setting the record to all zeroes.

It turns out that if we keep repeating the above process, we will eventually process all possible states. This gives us instructions on which numbers to provide for $$$V$$$ given the current state. The alternative solution is proof provided below works to prove that this is always possible for $$$8$$$⁠-bit records.

Alternative Solution

It turns out that we can solve this problem without ever knowing the bit count after interactions (other than being told when we eventually reach 00000000).

Let's consider how we would solve this problem for a record that has only 1 bit. Since we know the value starts as not $$$0$$$, we can force the state to reach $$$0$$$ by sending $$$1$$$ to the judge. Let's call this sequence $$$P[0]$$$:


Now, let's consider a record that is $$$2$$$ bits (and is not all zeroes). Let's start by assuming that the two bits are the same. If that's the case, we can force the record to be all zeroes by sending $$$11$$$. If We haven't reached all zeroes after that, that means our initial assumption that the left and right bit were the same was incorrect. So, if we send $$$10$$$, we can make the two bits the same. Then, if we are still not all zeroes, we can send another $$$11$$$. Let's call this sequence $$$P[1]$$$:

11    // P[0] + P[0]
10    // P[0] + 0   
11    // P[0] + P[0]

Now, let's generalize this and assume that the record has $$$2^k$$$ bits and is not all zeroes. Let's assume that the left $$$2^{k-1}$$$ bits and the right $$$2^{k-1}$$$ bits are the same. If that's the case, we can use $$$P[k - 1]$$$ (but each step is appended to itself) to force the record to reach all zeroes. If we did not reach all zeroes then our assumption that the left half and right were the same was not correct.

So, we can use the first instruction in $$$P[k - 1]$$$ and append $$$2^{k-1}$$$ 0's to it. Then we can repeat all of $$$P[k - 1]$$$ (each step doubled like before) again. As long as we keep not reaching all zeroes, we repeat this process with the next instruction in $$$P[k - 1]$$$.

The following Python code shows this process for how we can generate $$$P[3]$$$ for $$$8$$$⁠-bit records:

def appendzero(s):
  return s + '0' * len(s)

def expand(s):
  return s + s

def P(k):
  if k == 0:
      return ['1']
  seq = P(k - 1)
  seq_with_zero = [appendzero(s) for s in seq]
  seq_with_copy = [expand(s) for s in seq]
  res = seq_with_copy[:]
  for ins in seq_with_zero:
      res += [ins]
      res += seq_with_copy
  return res


Statistics — A. Pancake Deque

Statistics — B. Controlled Inflation

Statistics — C. ASeDatAb