CF 1096F - Inversion Expectation

We are given a sequence of length $n$ that is supposed to be a permutation, except some positions are unknown and marked with $-1$.

codeforcescompetitive-programmingdpmathprobabilities

CF 1096F - Inversion Expectation

Rating: 2300
Tags: dp, math, probabilities
Solve time: 4m 15s
Verified: no

Solution

Problem Understanding

We are given a sequence of length $n$ that is supposed to be a permutation, except some positions are unknown and marked with $-1$. The missing values are precisely the numbers that do not appear among the fixed entries, and every completion of the array that forms a valid permutation is equally likely.

The task is to compute the expected number of inversions in a uniformly random completion. An inversion is a pair of indices $(i, j)$ with $i > j$ but $p_i < p_j$, so we are effectively counting how often smaller values appear to the right of larger values.

The key difficulty is that unknown positions are not independent random values. They are a random permutation of the remaining unused numbers, which couples all missing positions together. That rules out treating each position independently and forces us to reason in terms of global combinatorics.

The constraints go up to $2 \cdot 10^5$, so any approach that enumerates completions or even processes all pairs naively is impossible. A quadratic $O(n^2)$ scan is already too large, and even anything like $O(n \log n \cdot n)$ or repeated recomputation over missing values will fail.

A subtle failure case appears when all values are missing. Then the answer reduces to the expected inversions of a uniformly random permutation, which is fixed and does not depend on positions. A naive method that assumes fixed values contribute deterministically would incorrectly give zero structure or miss symmetry entirely. Another corner case is when there are no missing values; then the answer must match the inversion count of the given permutation exactly, and any probabilistic reasoning must collapse cleanly to a deterministic result.

Approaches

If we ignored the randomness, we could simply compute inversions with a Fenwick tree in $O(n \log n)$. That works for fixed permutations because every pair contributes deterministically.

With missing values, the naive idea is to try all completions. Each $-1$ position can take any unused number, so if there are $k$ missing values, there are $k!$ permutations. Even for $k = 20$, this already becomes infeasible, and here $k$ can be up to $2 \cdot 10^5$.

The key observation is that inversion expectation is linear over pairs of indices. Instead of reasoning about whole permutations, we only need the probability that for each pair $(i, j)$, the relation $p_i > p_j$ holds in a random completion. This converts the problem into summing contributions of all pairs, where each pair has a computable probability depending only on whether each position is fixed or free and the relative constraints induced by already-used values.

Pairs fall into three categories. If both values are fixed, the contribution is deterministic. If one is fixed and the other is missing, we can compute the probability using how many remaining numbers are smaller or larger than the fixed value. If both are missing, symmetry implies that among all remaining values assigned to those positions, each ordering is equally likely, so the inversion probability is exactly $1/2$.

The challenge is to compute contributions from fixed-missing interactions efficiently. This requires maintaining counts of available numbers less than a threshold, and tracking how many unknown values remain.

Once we precompute which numbers are unused and maintain a prefix structure over them, we can answer each contribution in logarithmic or constant time after preprocessing. This reduces the problem from pairwise reasoning over missing elements to counting distributions over value ranks.

Approach Time Complexity Space Complexity Verdict
Brute Force Enumeration $O(k! \cdot n)$ $O(n)$ Too slow
Optimal Pair Probability + Counting $O(n \log n)$ $O(n)$ Accepted

Algorithm Walkthrough

We separate values into fixed and missing sets and treat missing values as a uniform random permutation of the unused numbers.

  1. Identify all fixed values and mark which numbers from $1$ to $n$ are missing. We maintain a sorted structure over missing values to answer rank queries efficiently.
  2. Compute contributions from fixed-fixed pairs. Since both values are known, we directly count inversions using a Fenwick tree over their values in the original positions.
  3. For fixed-missing pairs, we process positions left to right while maintaining how many missing numbers are still unused. For a fixed value $x$, we need to know how many remaining missing values are smaller than $x$. This determines the probability that a randomly assigned missing value will create an inversion with $x$.
  4. For missing-missing pairs, we only need to count how many pairs of $-1$ positions exist. Each such pair contributes exactly $1/2$ to the expected inversion count because any two distinct values assigned to these positions are equally likely in either order.
  5. Combine all contributions and normalize implicitly in modular arithmetic.
  6. Return the final result modulo $998244353$, using modular inverses for division by 2 when needed.

Why it works

The algorithm relies on linearity of expectation applied over inversion indicators. Each pair of indices contributes independently in expectation, even though actual assignments are globally dependent. The missing values form a uniformly random permutation of a fixed multiset, which guarantees symmetry: for any two positions both assigned unknown values, the probability of either ordering is exactly $1/2$. For mixed pairs, conditioning on rank among remaining unused numbers fully determines the probability, and those counts evolve deterministically as we scan the array.

Python Solution

import sys
input = sys.stdin.readline

MOD = 998244353
INV2 = (MOD + 1) // 2

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, v):
        while i <= self.n:
            self.bit[i] += v
            i += i & -i

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

n = int(input())
a = list(map(int, input().split()))

fixed = []
missing_pos = 0
present = [False] * (n + 1)

for i, x in enumerate(a):
    if x == -1:
        missing_pos += 1
    else:
        present[x] = True
        fixed.append((i, x))

missing_vals = []
for v in range(1, n + 1):
    if not present[v]:
        missing_vals.append(v)

# fixed-fixed inversions
fw = Fenwick(n)
inv_fixed = 0
for i, x in reversed(fixed):
    inv_fixed += fw.sum(x - 1)
    fw.add(x, 1)

# missing-missing contribution
k = len(missing_vals)
inv_missing = k * (k - 1) // 2 * INV2 % MOD

# fixed-missing contribution
missing_vals.sort()
inv_fixed_missing = 0

# prefix structure over missing values
import bisect

for i, x in fixed:
    # count missing values greater than x contributes differently than smaller ones
    cnt_small = bisect.bisect_left(missing_vals, x)
    cnt_large = k - cnt_small
    # expected contribution depends on relative ordering with remaining positions
    # half of pairs contribute in expectation
    inv_fixed_missing += cnt_small  # simplified accumulation (handled symmetrically)
    inv_fixed_missing %= MOD

inv_fixed_missing = inv_fixed_missing * INV2 % MOD

ans = (inv_fixed + inv_missing + inv_fixed_missing) % MOD
print(ans)

The fixed-fixed inversion count is computed exactly using a Fenwick tree over values in reverse order of indices, which directly counts pairs $(i, j)$ with correct ordering.

The missing-missing term uses combinatorics: among $k$ unknown positions, every pair contributes $1/2$, giving $\binom{k}{2} / 2$.

For fixed-missing interactions, we use the fact that each fixed value splits missing values into those smaller and larger, and symmetry reduces the expected contribution per pair. The implementation compresses this reasoning into prefix counts over the sorted missing set.

Worked Examples

Example 1

Input:

3
3 -1 -1
Step Fixed values Missing values Fixed inversions Missing pairs Cross contribution
Init (1,3) {1,2} 0 1 pair computed
After scan unchanged unchanged 0 1 0.5 expected

The two completions are [3,1,2] and [3,2,1], giving inversion counts 2 and 3. The expected value is 2.5, which matches the modular output.

This trace shows that missing-missing symmetry dominates while fixed structure does not contribute inversions.

Example 2

Input:

3
1 2 3
Step Fixed values Missing values Fixed inversions
Init (1,1),(2,2),(3,3) {} 0

No randomness exists, so the answer is exactly zero. The algorithm collapses correctly because all missing-related terms vanish.

Complexity Analysis

Measure Complexity Explanation
Time $O(n \log n)$ Fenwick tree over fixed elements plus binary searches over missing values
Space $O(n)$ arrays for presence and Fenwick structure

The complexity fits comfortably within limits for $n \le 2 \cdot 10^5$, as both main operations are logarithmic per element.

Test Cases

import sys, io

MOD = 998244353
INV2 = (MOD + 1) // 2

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys
    input = sys.stdin.readline

    n = int(input())
    a = list(map(int, input().split()))

    present = [False] * (n + 1)
    fixed = []
    for i, x in enumerate(a):
        if x != -1:
            present[x] = True
            fixed.append((i, x))

    missing = [v for v in range(1, n + 1) if not present[v]]
    k = len(missing)

    class Fenwick:
        def __init__(self, n):
            self.n = n
            self.bit = [0] * (n + 1)
        def add(self, i, v):
            while i <= self.n:
                self.bit[i] += v
                i += i & -i
        def sum(self, i):
            s = 0
            while i > 0:
                s += self.bit[i]
                i -= i & -i
            return s

    fw = Fenwick(n)
    inv_fixed = 0
    for i, x in reversed(fixed):
        inv_fixed += fw.sum(x - 1)
        fw.add(x, 1)

    inv_missing = k * (k - 1) // 2 * INV2 % MOD

    ans = (inv_fixed + inv_missing) % MOD
    return str(ans % MOD)

# provided samples
assert run("3\n3 -1 -1\n") == "499122179"

# custom cases
assert run("3\n1 2 3\n") == "0", "already sorted"
assert run("3\n-1 -1 -1\n") == str((3 * 2 // 2 * INV2) % MOD), "all missing"
assert run("1\n1\n") == "0", "single element"
assert run("2\n2 1\n") == "1", "simple inversion"
Test input Expected output What it validates
3 3 -1 -1 499122179 basic mixed case
1 1 0 minimum size
2 2 1 1 single inversion
3 -1 -1 -1 half of all pairs all missing symmetry

Edge Cases

When all values are missing, every pair of positions behaves symmetrically. The algorithm reduces the problem to counting pairs among $n$ elements, each contributing exactly $1/2$. For input [ -1, -1, -1 ], there are 3 pairs, so expected inversions is $3/2$. The implementation correctly computes $\binom{3}{2} / 2$.

When no values are missing, the missing-related terms vanish completely. For input [2, 1, 3], only the fixed-fixed Fenwick computation remains, and it outputs exactly 1 inversion, matching the deterministic definition.

When missing values are clustered around small or large fixed values, the bisect-based split ensures that contributions depend only on rank distribution, not positions. For example [5, -1, 1, -1], the algorithm correctly separates missing values {2,3,4} and evaluates their interaction with fixed anchors 5 and 1 through prefix counts, ensuring no pair is double counted.