algo/quickmaffs-permutation-puzzle

74 solves / 465 points

Writeup by Aryan

Once again, the problem statement is quite simple. We wish to compute the number of permutations p of the numbers 1 ... n (n < 10^4) that satisfy the following:

• For all i (2 <= i <= n), p[i - 1] < p[i] if i is odd, and p[i - 1] > p[i] if i is even (assume 1-indexing)

Since this number is quite large, we must return the result mod 10^9 + 7.

A simple python bruteforce for i in [1, 8] gives us the following interesting looking sequence: 1, 1, 2, 5, 16, 61, 272, 1385.

import itertools
MOD = 10**9 + 7

def ok(perm):
    for i in range(1, len(perm)):
        if i % 2 == 1:
            if perm[i-1] >= perm[i]:
                return False
        else:
            if perm[i-1] <= perm[i]:
                return False
    return True

def perms(n):
    all_permutations = itertools.permutations(range(1, n+1))
    valid_count = 0
    
    for perm in all_permutations:
        if ok(perm):
            valid_count += 1
    
    return valid_count % MOD

for i in range(1, 9):
    print(perms(i))

Turns out this is sequence A000111 on OEIS. Scrolling through the page, alternating permutations are mentioned a bunch. Googling alternating permutations leads to this GeeksForGeeks article that has most of the solution. All we need to do is implement some modular arithmetic to prevent overflow.

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

const ll MOD = 1e9 + 7;

ll binpow(ll base, ll exp, ll mod) {
    ll result = 1;
    while (exp > 0) {
        if (exp % 2 == 1)
            result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

void precompute_factorials(ll fact[], ll inv_fact[], int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    inv_fact[n] = binpow(fact[n], MOD - 2, MOD);
    for (int i = n - 1; i >= 0; i--) {
        inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
    }
}

ll binomial_coefficient(ll fact[], ll inv_fact[], int n, int k) {
    if (k > n || k < 0) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

ll zig_zag(int n) {
    ll fact[n + 1], inv_fact[n + 1], zig[n + 1] = {0};
    
    precompute_factorials(fact, inv_fact, n);
    
    zig[0] = 1;
    zig[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        ll sum = 0;
        for (int k = 0; k <= i - 1; k++) {
            ll binom = binomial_coefficient(fact, inv_fact, i - 1, k);
            sum = (sum + (binom * zig[k] % MOD) * zig[i - 1 - k] % MOD) % MOD;
        }
        zig[i] = sum * binpow(2, MOD - 2, MOD) % MOD;
    }
    
    return zig[n];
}

int main() {
    int n;
    cin >> n;
    cout << zig_zag(n) << endl;
    return 0;
}

Flag: vsctf{QuickMaffs_FMC_Huge_Degen_b4a1c2af876eeb9a}