Permutation Cuts

Cut a permutation anywhere, take the larger element on each side, keep the smaller of the two. Do that at every cut and you get an array. The question is how many permutations produce a given one — and the answer falls out of noticing that the array can only have one shape.

The problem#

Given n$𝑛$ and an array a$𝑎$ of length n−1$𝑛-1$, count the permutations p$𝑝$ of (1...n)$\left(1\dots 𝑛\right)$ with

for every 1≤i≤n−1$1\le 𝑖\le 𝑛-1$, modulo 998244353$998244353$. Both n$𝑛$ and the sum of n$𝑛$ over all tests go to 10^6${10}^6$, so the budget is linear and the constant matters.

One of the two maxima is always n$𝑛$#

Write L_i=max_(j≤i)p_j${𝐿}_{𝑖}={max}_{𝑗\le 𝑖}{𝑝}_{𝑗}$ and R_i=max_(j>i)p_j${𝑅}_{𝑖}={max}_{𝑗>𝑖}{𝑝}_{𝑗}$. As the cut moves right, L$𝐿$ can only grow and R$𝑅$ can only shrink. That much is immediate. The useful observation is sharper: let k$𝑘$ be the position holding the value n$𝑛$. Then n$𝑛$ is on the right of every cut before k$𝑘$ and on the left of every cut from k$𝑘$ onwards, so

In words:

a_i${𝑎}_{𝑖}$ is the maximum of whichever side does not contain n$𝑛$.

So a$𝑎$ is a prefix-maximum sequence glued to a suffix-maximum sequence — non-decreasing, then non-increasing. It is bitonic, and it has no choice about it.

The peak is n−1$𝑛-1$#

The two halves either side of position k$𝑘$ partition {1,...,n}∖{n}$\{1,\dots ,𝑛\}\setminus \{𝑛\}$ between them. One of them therefore contains n−1$𝑛-1$, and

Exactly one of the two, never both, since n−1$𝑛-1$ sits in exactly one half. That single fact does a lot of work below: it says the peak of the bitonic array is pinned to a known value, so an array whose peak is anything else is unachievable and the answer is zero.

Reading p$𝑝$ back off a$𝑎$#

Walk the left half outward from index 1$1$. Since a_i=max(p_1,...,p_i)${𝑎}_{𝑖}=max\left({𝑝}_1,\dots ,{𝑝}_{𝑖}\right)$ there,

• if a_i>a_(i−1)${𝑎}_{𝑖}>{𝑎}_{𝑖-1}$, position i$𝑖$ holds a new left-to-right maximum, and its value is forced to be exactly a_i${𝑎}_{𝑖}$;
• if a_i=a_(i−1)${𝑎}_{𝑖}={𝑎}_{𝑖-1}$, position i$𝑖$ holds something that did not break the record — any unused value below a_i${𝑎}_{𝑖}$, and we get to choose.

The right half is the mirror image. From a_j=max(p_(j+1),...,p_n)${𝑎}_{𝑗}=max\left({𝑝}_{𝑗+1},\dots ,{𝑝}_{𝑛}\right)$, a step a_j>a_(j+1)${𝑎}_{𝑗}>{𝑎}_{𝑗+1}$ forces p_(j+1)=a_j${𝑝}_{𝑗+1}={𝑎}_{𝑗}$, and a_j=a_(j+1)${𝑎}_{𝑗}={𝑎}_{𝑗+1}$ leaves a free choice below a_j${𝑎}_{𝑗}$.11Index j$𝑗$ on the right names position j+1$𝑗+1$, not j$𝑗$. Off-by-one here is the easiest way to write a solution that is right on palindromic inputs and wrong on everything else.

Each of the n−1$𝑛-1$ entries of a$𝑎$ names exactly one position of p$𝑝$, and the one position left over is k$𝑘$, which holds n$𝑛$.

Counting#

Process the entries in increasing order of value. Because Equation 2 makes a$𝑎$ rise and then fall, the two smallest unprocessed entries are always the two ends, so a pair of pointers walking inward visits the values in sorted order without ever sorting anything.

Keep a counter t$𝑡$ of positions already assigned. When the value v$𝑣$ at the current end is strictly larger than the previous one, that position is a record and its value is forced: one way. When v$𝑣$ repeats the previous value, the position takes any unused value strictly below v$𝑣$. Of the v−1$𝑣-1$ candidates, t−1$𝑡-1$ are already spent — every assigned position so far holds a value ≤v$\le 𝑣$, and exactly one of them holds v$𝑣$ itself — leaving

choices — Equation 4. If that count reaches zero the array is unachievable. Multiply, and finish with a factor of 2$2$: when the pointers meet, one entry and two positions remain, and the last freedom is which side of the final cut takes n$𝑛$.

The whole thing is a single inward walk: O(n)$𝑂\left(𝑛\right)$ time and no allocation beyond the input.

The code#

Three of the four early exits are the conditions above — the peak must be n−1$𝑛-1$ by Equation 3, values must not decrease along the walk, and a repeat must leave something to choose.

const PRIME_MOD: u64 = 998_244_353;

fn count(n: usize, xs: &[u32]) -> u64 {
    let (mut i, mut j, mut prev) = (0, n - 2, 0);
    let mut res = 1;
    let mut taken = 0;

    loop {
        // Equal ends can only be the peak, and the peak is pinned to n-1:
        // two different halves cannot both have maximum v.
        if xs[i] == xs[j] && xs[i] as usize != n - 1 {
            return 0
        };
        if i == j { return res * 2 % PRIME_MOD };

        let left = xs[i] < xs[j];
        let v = if left { xs[i] } else { xs[j] };

        if v < prev { return 0 };          // not bitonic
        if taken >= v { return 0 };        // nothing left below v to choose

        if v == prev {
            res *= (v - taken) as u64;     // a non-record position
            res %= PRIME_MOD;
        }

        prev = v;
        if left { i += 1 } else { j -= 1 };
        taken += 1;
    }
}

The equality test at the top of the loop is doing double duty, which is worth pausing on. While the pointers are apart it rejects an array claiming two halves with the same maximum. When they meet it is trivially true, and so becomes the check that the peak really is n−1$𝑛-1$ before the answer is returned.