Elevator Editorial

Subtask 1: $0 \leq V \leq 1$, $V_0 = V_N = 1$, and there are no consecutive zeros.

$K = 2$

Return $[1, -1, -1, \ldots, -1, -1, 1]$.

$K = 61$

Suppose we are at floor $s$ with value $V_s$. We press the button to floor $s+1$ if $V_s = 1$ and we press button to floor $s+2$ otherwise. If the button to floor $s$ is pressed, then $V_{s-1} = 1$; otherwise, $V_{s-1} = 0$.

Subtask 2: $0 \leq V \leq 1$

$K = 30$

We use the same solution as the full solution of subtask 1. Note that we cannot recover floors where we haven't visited.

$K$ in range approximately from $32$ to $34$.

On average, there is a $\frac12$ chance of skipping a floor if the floor before is visited. We can assign a random mapping where we swap the button presses at some floors. While the expected number of recovered floors for one scenario is very high, the large number of scenarios ($T = 10^4$) reduces the achieved $K$ to about the range from $32$ to $34$.

This idea can also be used to obtain more floors from simple solutions in the next subtasks.

$K$ in range from $38$ to $40$

The following idea will be used throughout the editorial

• We choose to encode some prefix of the visited floors

• We will design a way to encode $x$ floors using a block of $y$ buttons while ensuring that at least $z$ buttons are pressed. Call this an $(x, y, z)$ encoding. The last condition is so that we visit enough floors to encode them.

In this subtask, we will use a $(2, 3, 2)$ encoding. That is, we will encode $2$ values in $3$ buttons while ensuring that at least $2$ buttons is pressed in the block. Let

• $A$ and $B$ denote the first and second values we will encode in the block;
• the numbers in this table denote the offset from the first entry in the block.

Here is one possible encoding:

Getting $K = 40$ requires some careful design of what block encode what floors; a looser design could achieve about $K = 38$ or $K = 39$. One way to do this is

• Floor $0$ press floor $1$, and encode $V_0, V_1$ using the buttons to floors $2$ to $4$.

• In the prefix strictly before floor $3i+2$ ($0 \leq i \leq 18$), we can ensure that there are at least two visited and unencoded floors. We encode the first two such floors using buttons to floors $3i+2$ to $3i+4$.

• In the prefix strictly before floor $59$, we can ensure that there are at least two visited and unencoded floors. Instead of using the 2-in-3 encoding, we can directly encode those two floors using buttons to floors $59$ and $60$.

In total, there are $2 \cdot 19 + 2 = 40$ encoded floors.

Subtask 3: $0 \leq V \leq 2$

$K = 20$

If we are at floor $s$, press the button to floor $s + V_s + 1$.

$K = 30$

We choose to encode some prefix of the visited floors. For each value $A$, encode it in blocks of $2$ according to the following table.

Note that

• this is the binary representation of $A+1$.
• this is a $(x, y, z) = (1, 2, 1)$ encoding strategy.

Subtask 4: $0 \leq V \leq 3$

$K = 15$

If we are at floor $s$, press the button to floor $s + V_s + 1$.

$K = 20$

Use a $(1, 3, 1)$ encoding strategy, such as by using the binary representation of $A + 1$:

$K = 24$

Use a $(2, 5, 2)$ encoding.

$K = 25$

We can encode in the following way:

This encodes $1 \cdot 1 + 9 \cdot 2 + 6 \cdot 1 = 25$ floors.

One way to find a $(2, 5, 3)$ encoding table is to make an educated guess: the first press presses at most one button. Then, the main problem is to match the button to four other sets of floors which contains that button. You can then solve the matching by hand or by using bitmask DP where each mask has $4 \cdot 4 = 16$ bits, and each bit is a table entry.

Below is one possible $(2, 5, 3)$ encoding:

Beyond 100 points.

So far, a solution for these values of $K$

• $0 \leq V \leq 1$, $K = 41$
• $0 \leq V \leq 3$, $K = 27$

has been found. The main idea of these solutions is to use computer searches to find the encoding tables, then use dynamic programming to determine the encoding blocks.

$0 \leq V \leq 1$, $K = 41$

The encoding tables can be found using strong pruning or advanced algorithms.

$0 \leq V \leq 3$, $K = 27$

To find the encoding tables, we generalize how the table is discovered for $K = 25$. Notice that nontrivial encodings used are $(k, 2k+1, k+1)$ encodings, which is intuititve because we are encoding $4^k$ values to encode and we have exactly $2^{2k} = 4^k$ available button states.

Define

• $\text{Lower} (t) = \{ S \subseteq {0, 1, \ldots, 2t} \text{ such that } |S| \leq t \}$

• $\text{Upper} (k) = \{ S \subseteq {0, 1, \ldots, 2k} \text{ such that } |S| \geq k+1 \}$

Observe that $|\text{Lower} (t)| = 4^t$ and $|\text{Upper} (k)| = 4^k$.

To construct a $(k, 2k+1, k+1)$ encoding:

• After the $t$-th button ($1 \leq t \leq k-1$), the set of pressed buttons is an element of $\text{Lower} (t)$.
• After the last button, the set of pressed buttons is an element of $\text{Upper} (k)$.

Hence, we now only need to match

• $1$ entry of $\text{Lower} (t)$ to $4$ of its supersets in $\text{Lower} (t+1)$;
• $1$ entry of $\text{Lower} (k-1)$ to $4$ of its supersets in of $\text{Upper} (k)$.

Duplicate the $\text{Lower} (t)$ or $\text{Lower} (k-1)$ entries $4$ times, then create a bipartite graph connecting each set to its supersets in $\text{Lower} (t+1)$ or $\text{Lower} (k)$. Then, run a maximum matching algorithm, such as Dinic's algorithm.