CF 102897E - BM 充饥

Rating: -
Tags: -
Solve time: 2m 42s
Verified: no

Solution

A partition of $n$ in part-count form is a vector $c_1,\dots,c_n$ satisfying

$c_1+2c_2+\cdots+n c_n=n,$

where $c_k$ is the number of parts equal to $k$. The colex order of partitions is lexicographic order of the reversed sequence $c_n,\dots,c_1$, so the most significant coordinate is $c_n$ and the least significant is $c_1$.

The representation required by the exercise adds a linked list of the indices $k$ for which $c_k>0$. If these indices are $k_1<\cdots<k_t$, then

$l_0=k_1,\quad l_{k_1}=k_2,\ \dots,\ l_{k_{t-1}}=k_t,\quad l_{k_t}=0.$

This structure supports constant-time access to the smallest and next larger occupied part sizes.

The algorithm follows the same structural idea as Algorithm P: maintain the current partition, visit it, then locate the rightmost position in colex order that can be increased, perform a minimal increment there, and repair feasibility by a deterministic local transformation that preserves the partition constraints.

The key observation is that in the sequence representation, the critical modification is either splitting a part $x+1$ into $x$ followed by $1$, or decreasing a part and redistributing the remaining unit mass into smaller parts. In the part-count representation, both operations correspond to moving one unit of mass between coordinates while preserving $\sum k c_k$.

We maintain the invariant that the linked list correctly lists all indices $k$ with $c_k>0$ in increasing order. We also maintain the implicit convention that the current partition is always valid.

Let $q$ denote the largest index such that $c_q>0$. This is obtained by following the chain from $l_0$ until $0$.

A transition in colex order modifies the partition by trying to increase the largest possible coordinate in the vector $(c_n,\dots,c_1)$, which corresponds to trying to increase $c_q$ for the largest feasible $q$, and if this is not possible, propagating the effect to smaller indices. In the partition structure, this is implemented by repeatedly transforming a part of size $x$ into smaller parts until a legal increase becomes possible at the next candidate position.

The algorithm is therefore driven by a descending scan over occupied part sizes, implemented through the link array, combined with a local transformation that replaces one occurrence of a part size by a canonical “split” configuration.

We now present the algorithm.

Initialize the partition for $n$: set $c_1=n$ and $c_k=0$ for $k>1$. The link structure is $l_0=1$ and $l_1=0$.

At each step, the current partition is visited.

Let $q$ be the largest index with $c_q>0$, obtained by traversing links from $0$.

If $q=1$, the partition is $1+1+\cdots+1$, and no further modification is possible, so the algorithm terminates.

Otherwise $q>1$, and one occurrence of part size $q$ is selected for modification, so $c_q\leftarrow c_q-1$. If this makes $c_q=0$, the predecessor link is updated so that the previous element in the chain now points to $l_q$.

The removed part of size $q$ contributes total weight $q$. The next partition in colex order is obtained by converting this mass into a maximal allowed increase in the vector $(c_n,\dots,c_1)$, which is achieved by increasing the largest possible coordinate while preserving feasibility of the remaining weight. The maximal coordinate that can be increased is $c_{q-1}$, because increasing any $c_k$ with $k\ge q$ would exceed the available weight once colex constraints are enforced, while all larger coordinates are zero or fixed by maximality of $q$.

We therefore attempt to place the removed unit mass into $c_{q-1}$, setting

$c_{q-1}\leftarrow c_{q-1}+1.$

This accounts for one unit of the removed weight $q$, leaving residual weight $q-1$ that must be distributed into parts not exceeding $q-1$.

The residual weight $q-1$ is filled greedily by converting it into ones, which is the lexicographically smallest feasible completion in the reversed order. This is achieved by setting

$c_1\leftarrow c_1+(q-1).$

The resulting modification preserves the total weight because the change in contribution is

$-(q) + (q-1)\cdot 1 + 1\cdot (q-1)=0,$

where the second term accounts for the new part of size $q-1$ and the third term accounts for the added ones.

Finally, the link structure is updated: if $q-1>1$ and was previously absent, it is inserted immediately after $l_0$ or after the predecessor of $q$ depending on whether it already exists; if $c_1$ becomes positive and was previously zero, it is appended at the end of the chain.

After this repair, the resulting vector again satisfies the partition condition and corresponds to the next element in colex order because the modification increases the earliest possible coordinate in the reversed sequence while forcing all more significant coordinates to remain minimal.

Correctness follows from the characterization of colex order as lexicographic order of $c_n,\dots,c_1$. At each step, the algorithm modifies the rightmost feasible coordinate in this order, and the redistribution of the removed weight into the lexicographically smallest completion guarantees that no intermediate valid partition can lie between the current and produced one in colex order. The link structure ensures that identifying $q$ and maintaining adjacency of nonzero coordinates requires time proportional to the number of affected indices.

This completes the construction of the required algorithm. ∎