Problem 866: Tidying Up B

Mathematical Analysis

Hexagonal Numbers

The $k$-th hexagonal number is:

The first few values are: $H_1 = 1, H_2 = 6, H_3 = 15, H_4 = 28, \ldots$

Segment Formation Process

When the father places piece $i$ in position $i$, one of three things happens:

1. Isolated: Neither position $i-1$ nor $i+1$ is filled. A new segment of length 1 is formed. He writes $H_1 = 1$.
2. Extension: Exactly one neighbor is filled, extending a segment of length $m$ to length $m+1$. He writes $H_{m+1}$.
3. Merge: Both neighbors are filled, merging segments of lengths $m_1$ and $m_2$ into one segment of length $m_1 + m_2 + 1$. He writes $H_{m_1 + m_2 + 1}$.

Dynamic Programming Approach

We track the state of the caterpillar as pieces are placed. For a permutation $\sigma$ of $\{1, 2, \ldots, N\}$, piece $\sigma(t)$ is placed at time $t$.

We use a dynamic programming approach where we process positions left to right and track segment structures. The expected value of the product over all $N!$ permutations can be computed using the recurrence on segment configurations.

Modular Arithmetic

Since the answer must be given modulo $987654319$ (which is prime), we work in $\mathbb{F}_{987654319}$ and use modular inverses where needed.

Editorial

Project Euler 866: Tidying Up B A caterpillar of N=100 pieces is assembled randomly. When a segment of length k is formed, H_k = k*(2k-1) is recorded. We want the expected value of the product of all recorded hexagonal numbers, mod 987654319. Key insight: Consider which piece is placed LAST in each interval [a,b]. If piece at position i is placed last in interval [a,b] of length L=b-a+1, then it contributes H_L to the product. The sub-intervals [a,i-1] and [i+1,b] are filled independently. E(L) = H_L / L * sum_{i=0}^{L-1} E(i) * E(L-1-i) E(0) = 1. We enumerate all permutations (or use DP on segment structures). We then iterate over each permutation, simulate the placement process. Finally, track segment lengths and compute the product of hexagonal numbers.

Pseudocode

Enumerate all permutations (or use DP on segment structures)
For each permutation, simulate the placement process
Track segment lengths and compute the product of hexagonal numbers
Average over all permutations
Return result modulo $987654319$

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity Analysis

• Time: $O(N^2 \cdot P(N))$ where $P(N)$ is the number of partitions involved in the DP states
• Space: $O(N \cdot P(N))$

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Project Euler 866: Tidying Up B
 *
 * A caterpillar of N=100 pieces is assembled randomly. When a segment of
 * length k is formed, H_k = k*(2k-1) is recorded. We want the expected
 * value of the product of all recorded hexagonal numbers, mod 987654319.
 *
 * Key insight: Consider which piece is placed LAST in each interval [a,b].
 * If piece at position i is placed last in interval [a,b] of length L=b-a+1,
 * then it contributes H_L to the product. The sub-intervals [a,i-1] and
 * [i+1,b] are filled independently.
 *
 * E(L) = H_L / L * sum_{i=0}^{L-1} E(i) * E(L-1-i)
 * E(0) = 1
 */

const long long MOD = 987654319;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

long long inv(long long a, long long mod) {
    return power(a, mod - 2, mod);
}

int main() {
    const int N = 100;

    // H_k = k * (2k - 1)
    auto H = [&](long long k) -> long long {
        return k % MOD * ((2 * k - 1) % MOD) % MOD;
    };

    // E[L] = expected product for interval of length L
    vector<long long> E(N + 1, 0);
    E[0] = 1;

    for (int L = 1; L <= N; L++) {
        long long s = 0;
        for (int i = 0; i < L; i++) {
            s = (s + E[i] % MOD * E[L - 1 - i]) % MOD;
        }
        E[L] = H(L) % MOD * s % MOD * inv(L, MOD) % MOD;
    }

    cout << E[N] << endl;

    return 0;
}

"""
Project Euler 866: Tidying Up B

A caterpillar of N=100 pieces is assembled randomly. When a segment of
length k is formed, H_k = k*(2k-1) is recorded. We want the expected
value of the product of all recorded hexagonal numbers, mod 987654319.

Key insight: Consider which piece is placed LAST in each interval [a,b].
If piece at position i is placed last in interval [a,b] of length L=b-a+1,
then it contributes H_L to the product. The sub-intervals [a,i-1] and
[i+1,b] are filled independently.

E(L) = H_L / L * sum_{i=0}^{L-1} E(i) * E(L-1-i)
E(0) = 1
"""

MOD = 987654319

def solve():
    N = 100

    def H(k):
        return k * (2 * k - 1) % MOD

    E = [0] * (N + 1)
    E[0] = 1

    for L in range(1, N + 1):
        s = 0
        for i in range(L):
            s = (s + E[i] * E[L - 1 - i]) % MOD
        E[L] = H(L) * s % MOD * pow(L, MOD - 2, MOD) % MOD

    print(E[N])

solve()