docker_space/frontier_cs_8/check_range.cpp

// Check: what range of T values do generalized chains with d=26 produce?
// Specifically, can T exceed 134217727 (the standard chain max)?
#include <bits/stdc++.h>
using namespace std;
constexpr long long P = 998244353;
constexpr int MAXSTATES = 31 * 31;

int d;
int g1_arr[30], gy_arr[30];
int ret_instr[MAXSTATES];
long long cost_arr[MAXSTATES];
int8_t status_arr[MAXSTATES];
struct Frame { int state; int8_t phase; int dep1, dep2; };
Frame stk[MAXSTATES * 2];
int stk_top;
inline int encode(int i, int x) { return i * (d + 1) + x; }

long long eval_fast() {
    int ns = (d + 1) * (d + 1);
    memset(status_arr, 0, ns);
    stk_top = 0;
    stk[stk_top++] = {encode(0, 0), 0, -1, -1};
    while (stk_top > 0) {
        Frame& f = stk[stk_top - 1];
        int s = f.state, i = s / (d + 1), x = s % (d + 1);
        if (f.phase == 0) {
            if (status_arr[s] == 2) { stk_top--; continue; }
            if (status_arr[s] == 1) return -1;
            status_arr[s] = 1;
            if (i < d) {
                if (x == i + 1) { ret_instr[s] = g1_arr[i]; cost_arr[s] = 1; status_arr[s] = 2; stk_top--; continue; }
                f.dep1 = encode(gy_arr[i], i + 1); f.phase = 1; stk[stk_top++] = {f.dep1, 0, -1, -1}; continue;
            } else {
                if (x == 0) { ret_instr[s] = -1; cost_arr[s] = 1; status_arr[s] = 2; stk_top--; continue; }
                f.dep1 = encode(d, 1); f.phase = 1; stk[stk_top++] = {f.dep1, 0, -1, -1}; continue;
            }
        } else if (f.phase == 1) {
            if (status_arr[f.dep1] != 2) return -1;
            int j = ret_instr[f.dep1]; if (j < 0 || j > d) return -1;
            f.dep2 = encode(j, x); f.phase = 2; stk[stk_top++] = {f.dep2, 0, -1, -1}; continue;
        } else {
            if (status_arr[f.dep2] != 2) return -1;
            ret_instr[s] = ret_instr[f.dep2]; cost_arr[s] = (cost_arr[f.dep1] + cost_arr[f.dep2] + 1) % P;
            status_arr[s] = 2; stk_top--;
        }
    }
    return status_arr[encode(0, 0)] == 2 ? cost_arr[encode(0, 0)] : -1;
}

int main() {
    d = 26;
    mt19937 rng(42);

    long long max_T = 0;
    long long min_T = P;
    int above_134M = 0;
    int total_valid = 0;
    set<long long> unique_T;

    auto t0 = chrono::steady_clock::now();

    for (int trial = 0; trial < 1000000; trial++) {
        for (int j = 0; j < d; j++) {
            g1_arr[j] = j + 1;
            gy_arr[j] = rng() % (j + 1);
        }
        // Modify some g1
        int nc = 1 + rng() % 5;
        for (int c = 0; c < nc; c++) {
            g1_arr[rng() % d] = rng() % (d + 1);
        }

        long long T = eval_fast();
        if (T < 0) continue;
        total_valid++;
        if (T > max_T) {
            max_T = T;
            fprintf(stderr, "New max T: %lld at trial %d\n", T, trial);
        }
        if (T < min_T) min_T = T;
        if (T > 134217727) above_134M++;
        if (unique_T.size() < 100000) unique_T.insert(T);

        if (trial % 100000 == 0) {
            auto t1 = chrono::steady_clock::now();
            double ms = chrono::duration_cast<chrono::milliseconds>(t1 - t0).count();
            fprintf(stderr, "trial=%d valid=%d max=%lld min=%lld above_134M=%d unique=%zu time=%.0fms\n",
                trial, total_valid, max_T, min_T, above_134M, unique_T.size(), ms);
        }
    }

    printf("Total valid: %d\n", total_valid);
    printf("Max T: %lld\n", max_T);
    printf("Min T: %lld\n", min_T);
    printf("Above 134217727: %d (%.2f%%)\n", above_134M, 100.0*above_134M/total_valid);
    printf("Unique T values: %zu\n", unique_T.size());

    return 0;
}