docker_space/frontier_cs_8/modified_chain.cpp

// Modified chain: d POP instructions + 1 HALT, but with more complex structure
// Instead of each POP using a unique char, we can have some POPs share chars
// or use multiple chars per level.
//
// Key idea: In a standard chain with d=26, max T = 2^27-1 = 134217727
// We need T = 150994941 (target 1) or 150994939 (target 2)
// That's about 12.5% more than the chain max.
//
// What if we use one of the 26 POP slots more effectively?
// E.g., one POP instruction that, instead of doubling, triples the count?
//
// For a standard chain POP at level j with gy[j]=0:
//   solve(j, x) for x != (j+1): push (j+1), go to 0, solve(0, j+1) = chain_steps(j), then solve(chain_ret(j), x)
//   This gives: steps(j, x) = 1 + chain_steps(0 to j-1) + steps(next, x)
//   And chain_ret(j) = j+1 (the next instruction after clearing the push)
//
// What if instead of pushing a char that gets popped by this same instruction,
// we push a char that needs to traverse MULTIPLE instructions before being popped?
//
// Actually, the issue is different. In the checker, the recursion is:
//   solve(i, x): for POP i, if x != pop_char:
//     (j, u) = solve(push_goto, push_char)  -- "evaluate the push"
//     (k, v) = solve(j, x)                  -- "then handle x at the return point"
//     result = (k, u + v + 1)
//
// For a standard chain with gy[j]=0: solve(0, push_char) traverses the entire subchain from 0.
// The push_char is (j+1), which doesn't match any pop_char of instructions 0..j-1 (they pop 1..j).
// So solve(0, j+1) pushes at every level, creating a tree of depth j.
//
// What if we use 2 different chars at one level? E.g., have POP j pop char j+1,
// but push TWO different chars (at two different instructions). But each POP can only push one char.
//
// Alternative: use a non-chain goto. E.g., POP j pushes char c and goes to some instruction k != 0.
// If k goes to an instruction that pushes more, we get more steps.
//
// Actually, the fundamental issue: for d=26 chain, the computation is exact (< P).
// So the step count is literally bounded by 2^27-1. No modular tricks.
//
// For the step count to exceed 2^27-1 with 27 instructions, we NEED non-chain structure
// that creates more than 2^27-1 steps. This requires the dp DAG to have more paths.
//
// With n=27 instructions and alphabet up to 1024, we have 27*1025 = 27675 states.
// The step count grows like Fibonacci/exponential over the DAG.
// A DAG on 27675 nodes can have step counts up to... 2^27675? No, it depends on the structure.
//
// Actually, the computation does: step[state] = 1 + step[child1] + step[child2]
// where child1 and child2 are other states. If the DAG is a binary tree of depth D,
// step count = 2^D. The maximum depth is bounded by the number of states = 27675.
// So max step count could be astronomical (2^27675). But we need it mod P.
//
// The key: with enough states (via larger alphabet), we can create deep recursion trees
// that wrap around mod P to hit any target!
//
// So the question becomes: what's the minimum n such that n * (max_char + 1) provides
// enough states to hit our target?
//
// For a chain with d instructions and alphabet A, the "effective depth" is d * A
// (each instruction can be visited with A different stack tops).
// We need enough depth to wrap around mod P.
//
// With n instructions and alphabet A:
// - Number of states: n * (A+1)
// - If we can create a linear chain of these states, step count = 2^(n*(A+1))
// - We need 2^(n*(A+1)) >= P ≈ 10^9, so n*(A+1) >= 30
//
// With n=4, A=7: 4*8=32 states >= 30. So theoretically n=4 can achieve any target mod P!
// But we need to find the right program structure.

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

constexpr long long P = 998244353;

int n_instr;
int maxChar;
int type_arr[30];
int pop_char_arr[30], goto1_arr[30], push_char_arr[30], goto2_arr[30];

// dp indexed by [instr][char], where char 0=empty, 1..maxChar
optional<pair<int, long long>> dp[30][1030];
bool vis[30][1030];
bool infinite_flag;

pair<int, long long> solve(int i, int x) {
    if (dp[i][x]) return dp[i][x].value();
    if (vis[i][x]) { infinite_flag = true; return {-1, 0}; }
    vis[i][x] = true;

    if (type_arr[i] == 0) {
        if (x == pop_char_arr[i]) {
            dp[i][x] = {goto1_arr[i], 1LL};
        } else {
            auto [j, u] = solve(goto2_arr[i], push_char_arr[i]);
            if (infinite_flag) return {-1, 0};
            auto [k, v] = solve(j, x);
            if (infinite_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(goto2_arr[i], push_char_arr[i]);
            if (infinite_flag) return {-1, 0};
            auto [k, v] = solve(j, x);
            if (infinite_flag) return {-1, 0};
            dp[i][x] = {k, (u + v + 1) % P};
        }
    }
    return dp[i][x].value();
}

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

int main(int argc, char* argv[]) {
    if (argc < 4) {
        fprintf(stderr, "Usage: %s <target> <n> <alpha>\n", argv[0]);
        return 1;
    }
    long long target = atoll(argv[1]);
    n_instr = atoi(argv[2]);
    maxChar = atoi(argv[3]);

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    auto startTime = chrono::steady_clock::now();
    auto elapsed_ms = [&]() {
        return chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - startTime).count();
    };

    // Save best
    int best_type[30], best_pop[30], best_g1[30], best_push[30], best_g2[30];
    bool found = false;
    int restarts = 0;

    while (elapsed_ms() < 120000 && !found) {
        restarts++;
        // Random init: ensure at least one HALT, prefer mostly POP
        for (int i = 0; i < n_instr; i++) {
            if (i == n_instr - 1) type_arr[i] = 1; // last is HALT
            else type_arr[i] = 0; // POP

            if (type_arr[i] == 0) {
                pop_char_arr[i] = 1 + rng() % maxChar;
                goto1_arr[i] = rng() % n_instr;
                push_char_arr[i] = 1 + rng() % maxChar;
                goto2_arr[i] = rng() % n_instr;
            } else {
                push_char_arr[i] = 1 + rng() % maxChar;
                goto2_arr[i] = rng() % n_instr;
            }
        }

        long long T = evaluate();
        if (T < 0) continue;
        if (T == target) {
            found = true;
            memcpy(best_type, type_arr, sizeof(best_type));
            memcpy(best_pop, pop_char_arr, sizeof(best_pop));
            memcpy(best_g1, goto1_arr, sizeof(best_g1));
            memcpy(best_push, push_char_arr, sizeof(best_push));
            memcpy(best_g2, goto2_arr, sizeof(best_g2));
            break;
        }

        // Hill climbing
        for (int iter = 0; iter < 200000 && !found; iter++) {
            // Save
            int sv_type[30], sv_pop[30], sv_g1[30], sv_push[30], sv_g2[30];
            memcpy(sv_type, type_arr, sizeof(sv_type));
            memcpy(sv_pop, pop_char_arr, sizeof(sv_pop));
            memcpy(sv_g1, goto1_arr, sizeof(sv_g1));
            memcpy(sv_push, push_char_arr, sizeof(sv_push));
            memcpy(sv_g2, goto2_arr, sizeof(sv_g2));

            // Mutate one instruction
            int i = rng() % n_instr;
            int what = rng() % 6;
            if (what == 0 && i < n_instr - 1) {
                // Change type (rarely)
                // skip for now, keep structure stable
            }
            if (what == 1 && type_arr[i] == 0) push_char_arr[i] = 1 + rng() % maxChar;
            else if (what == 2) goto2_arr[i] = rng() % n_instr;
            else if (what == 3 && type_arr[i] == 0) goto1_arr[i] = rng() % n_instr;
            else if (what == 4 && type_arr[i] == 0) pop_char_arr[i] = 1 + rng() % maxChar;
            else if (what == 5) {
                if (type_arr[i] == 0) push_char_arr[i] = 1 + rng() % maxChar;
                else push_char_arr[i] = 1 + rng() % maxChar;
            }

            long long nT = evaluate();
            if (nT < 0) {
                memcpy(type_arr, sv_type, sizeof(sv_type));
                memcpy(pop_char_arr, sv_pop, sizeof(sv_pop));
                memcpy(goto1_arr, sv_g1, sizeof(sv_g1));
                memcpy(push_char_arr, sv_push, sizeof(sv_push));
                memcpy(goto2_arr, sv_g2, sizeof(sv_g2));
                continue;
            }

            if (nT == target) {
                found = true;
                memcpy(best_type, type_arr, sizeof(best_type));
                memcpy(best_pop, pop_char_arr, sizeof(best_pop));
                memcpy(best_g1, goto1_arr, sizeof(best_g1));
                memcpy(best_push, push_char_arr, sizeof(best_push));
                memcpy(best_g2, goto2_arr, sizeof(best_g2));
                break;
            }

            long long nd = min((nT - target + P) % P, (target - nT + P) % P);
            long long od = min((T - target + P) % P, (target - T + P) % P);

            if (nd <= od) {
                T = nT;
            } else {
                memcpy(type_arr, sv_type, sizeof(sv_type));
                memcpy(pop_char_arr, sv_pop, sizeof(sv_pop));
                memcpy(goto1_arr, sv_g1, sizeof(sv_g1));
                memcpy(push_char_arr, sv_push, sizeof(sv_push));
                memcpy(goto2_arr, sv_g2, sizeof(sv_g2));
            }
        }

        if (restarts % 50 == 0) {
            fprintf(stderr, "restart=%d elapsed=%ldms\n", restarts, elapsed_ms());
        }
    }

    if (found) {
        fprintf(stderr, "FOUND n=%d alpha=%d after %d restarts\n", n_instr, maxChar, restarts);
        printf("%d\n", n_instr);
        for (int i = 0; i < n_instr; i++) {
            if (best_type[i] == 0) {
                printf("POP %d GOTO %d PUSH %d GOTO %d\n",
                    best_pop[i], best_g1[i]+1, best_push[i], best_g2[i]+1);
            } else {
                printf("HALT PUSH %d GOTO %d\n", best_push[i], best_g2[i]+1);
            }
        }
    } else {
        fprintf(stderr, "NOT FOUND n=%d alpha=%d after %d restarts\n", n_instr, maxChar, restarts);
    }

    return 0;
}