Gravity Falls

Observation 1: what gravity actually does

Look at one column $c$ by itself. After all falling stops, the bottom cell in column $c$ is the element from the lowest array whose length is at least $c$.

So if we read arrays from bottom to top, an array matters only when its length is a new maximum. If the previous maximum length was $p$ and this array has length $k > p$, then it contributes exactly the suffix $a[p+1], a[p+2], \dots, a[k]$ to the final bottom row.

Therefore every possible answer has the form

$$a_{i_1}[1..k_{i_1}] \Vert a_{i_2}[k_{i_1}+1..k_{i_2}] \Vert \cdots \Vert a_{i_m}[k_{i_{m-1}}+1..k_{i_m}],$$

where

$$k_{i_1} < k_{i_2} < \cdots < k_{i_m} = L,$$

and $L = \max k_i$.

Conversely, any such increasing-length chain is realizable: place those chosen arrays in that bottom-to-top order, and insert every unused array right above the first chosen array whose length is at least its own. Then it is never the lowest array in any column it occupies, so it changes nothing.

So yeah, the physics is fake. This is just lexicographic DP in a trench coat.

DP formulation

Let $F_p$ be the lexicographically minimum suffix of the bottom row after the first $p$ columns are already fixed.

If the next chosen array is $i$ with $k_i > p$, then it contributes its suffix and afterwards we continue optimally from $k_i$:

$$F_p = \min_{k_i > p} \left( a_i[p+1..k_i] \Vert F_{k_i} \right).$$

Brute force over all $i$ for every $p$ is too slow.

The right-to-left ranking trick

For a fixed state $p$, define the candidate of array $i$ as

$$S_i(p) = a_i[p+1..k_i] \Vert F_{k_i}, \qquad k_i > p.$$

Among all active arrays ($k_i > p$), the answer $F_p$ is just the minimum of these sequences.

Now process $p$ from $L-1$ down to $0$.

Suppose we already know the relative order of all relevant tails at position $p+1$. How do we compare candidates at position $p$?

All sequences $S_i(p)$ have the same total length $L-p$, so lexicographic comparison is simple:

• first compare $a_i[p+1]$;
• if they are equal, compare the remaining tail.

So each active array is fully described by the pair

$$\big(a_i[p+1],\ \text{rank of its tail}\big).$$

There are only two possibilities for that tail:

• If $k_i = p+1$, then after using this last element of array $i$, the rest is exactly $F_{p+1}$. That is the best possible tail at the next state, so its rank is $1$.
• If $k_i > p+1$, then the tail is exactly $S_i(p+1)$, whose rank we already know from the previous step.

Therefore, at step $p$:

1. add all arrays with length $p+1$ to the active set, with current tail-rank $1$;
2. for every active array, build the pair $(a_i[p+1], \text{tail-rank})$;
3. sort all active arrays by this pair;
4. compress equal pairs into equal ranks;
5. the first array in this order is the optimal choice for $F_p$.

Store that array as best[p].

Why this is correct

We prove by descending induction on $p$.

Assume that before processing $p$, every active array $i$ stores the correct rank of its tail:

• rank of $S_i(p+1)$ if $k_i > p+1$;
• rank $1$ for $F_{p+1}$ if $k_i = p+1$.

Then its full candidate at position $p$ is exactly

$$S_i(p) = [a_i[p+1]] \Vert \text{tail}.$$

Because all $S_i(p)$ have equal length, sorting by

$$(a_i[p+1], \text{tail-rank})$$

is exactly the same as sorting by the full sequences $S_i(p)$ lexicographically. After compression, the new stored rank is therefore the correct rank of $S_i(p)$.

So the first array after sorting is precisely the one minimizing $S_i(p)$, i.e. the one that gives $F_p$. Induction done. No wizardry, just bookkeeping.

Reconstruction

Start with $p=0$.

If best[p] = i, then the optimal answer next uses array $i$, so append

$$a_i[p+1], a_i[p+2], \dots, a_i[k_i],$$

and jump to $p = k_i$.

Repeat until $p = L$.

Complexity

Let $m_p$ be the number of active arrays at step $p$.

At that step we sort $m_p$ items, which costs $O(m_p \log K)$ where

$$K = \sum_i k_i.$$

Also, each array is active for exactly $k_i$ steps, so

$$\sum_p m_p = \sum_i k_i = K.$$

Hence the total complexity is

$$O(K \log K),$$

with $O(K)$ memory.

Since $K \le 2 \cdot 10^5$, this is easily fast enough.