docker_space/frontier_cs_8/max_steps.cpp

// Find the maximum step count achievable with n instructions and alphabet A
// Use random sampling + hill climbing to maximize T
#include <bits/stdc++.h>
using namespace std;

constexpr long long P = 998244353;

int n_instr, maxChar;
int type_arr[30];
int pop_c[30], g1[30], push_c[30], g2[30];

optional<pair<int, long long>> dp[30][1030];
bool vis[30][1030];
bool inf_flag;

pair<int, long long> solve(int i, int x) {
    if (dp[i][x]) return dp[i][x].value();
    if (vis[i][x]) { inf_flag = true; return {-1, 0}; }
    vis[i][x] = true;
    if (type_arr[i] == 0) {
        if (x == pop_c[i]) { dp[i][x] = {g1[i], 1LL}; }
        else {
            auto [j, u] = solve(g2[i], push_c[i]);
            if (inf_flag) return {-1, 0};
            auto [k, v] = solve(j, x);
            if (inf_flag) return {-1, 0};
            dp[i][x] = {k, (u + v + 1) % P};
        }
    } else {
        if (x == 0) { dp[i][x] = {-1, 1LL}; }
        else {
            auto [j, u] = solve(g2[i], push_c[i]);
            if (inf_flag) return {-1, 0};
            auto [k, v] = solve(j, x);
            if (inf_flag) return {-1, 0};
            dp[i][x] = {k, (u + v + 1) % P};
        }
    }
    return dp[i][x].value();
}

long long eval_prog() {
    for (int i = 0; i < n_instr; i++)
        for (int j = 0; j <= maxChar; j++) {
            dp[i][j].reset();
            vis[i][j] = false;
        }
    inf_flag = false;
    auto [fi, steps] = solve(0, 0);
    if (inf_flag) return -1;
    return steps;
}

int main() {
    mt19937 rng(42);

    // For each (n, A), find max T achievable
    for (int n = 2; n <= 10; n++) {
        for (int A : {n, n+2, 2*n, 3*n, min(30, 5*n)}) {
            n_instr = n;
            maxChar = A;
            long long global_max = 0;

            for (int restart = 0; restart < 10000; restart++) {
                // Random program
                for (int i = 0; i < n; i++) {
                    type_arr[i] = (i == n-1) ? 1 : 0;
                    if (type_arr[i] == 0) {
                        pop_c[i] = 1 + rng() % A;
                        g1[i] = rng() % n;
                        push_c[i] = 1 + rng() % A;
                        g2[i] = rng() % n;
                    } else {
                        push_c[i] = 1 + rng() % A;
                        g2[i] = rng() % n;
                    }
                }

                long long T = eval_prog();
                if (T < 0) continue;

                // Hill climb to maximize T
                for (int iter = 0; iter < 5000; iter++) {
                    int i = rng() % n;
                    int sv_pop = pop_c[i], sv_g1 = g1[i], sv_push = push_c[i], sv_g2 = g2[i];
                    int what = rng() % 4;
                    if (what == 0 && type_arr[i] == 0) pop_c[i] = 1 + rng() % A;
                    else if (what == 1) push_c[i] = 1 + rng() % A;
                    else if (what == 2) g2[i] = rng() % n;
                    else if (type_arr[i] == 0) g1[i] = rng() % n;

                    long long nT = eval_prog();
                    if (nT > T) T = nT;
                    else { pop_c[i] = sv_pop; g1[i] = sv_g1; push_c[i] = sv_push; g2[i] = sv_g2; }
                }

                if (T > global_max) global_max = T;
            }

            printf("n=%d A=%d: maxT=%lld (chain max=%lld, P=%d)\n",
                n, A, global_max, min((1LL<<(n))-1, (long long)P), P);
        }
    }

    return 0;
}