docker_space/frontier_cs_8/chain_general.cpp

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

static const long long P = 998244353;

// Generalized chain: n-1 POP instructions + 1 HALT
// POP instruction i: POP (i+1) GOTO pop_goto[i] PUSH push_val[i] GOTO push_goto[i]
// HALT instruction (n-1): HALT PUSH halt_push GOTO halt_goto
//
// The standard chain has pop_goto[i]=i+1, push_val[i]=i+1, push_goto[i] varies
// Let's generalize by allowing push_val and push_goto to vary more

// For the checker DP, we need to simulate it properly
// State: (instr, top_of_stack_value)

struct Evaluator {
    int n;
    // POP instructions 0..n-2
    vector<int> pop_val;    // = i+1 always
    vector<int> pop_goto;   // where to go when matched
    vector<int> push_val;   // what to push
    vector<int> push_goto;  // where to go when not matched
    // HALT instruction n-1
    int halt_push;
    int halt_goto;

    // DP
    vector<array<int, 1025>> dp_dest;
    vector<array<long long, 1025>> dp_cost;
    vector<array<int8_t, 1025>> dp_state; // 0=unvisited, 1=in-progress, 2=done

    bool has_cycle;

    void init() {
        dp_dest.assign(n, array<int, 1025>{});
        dp_cost.assign(n, array<long long, 1025>{});
        dp_state.assign(n, array<int8_t, 1025>{});
        has_cycle = false;
    }

    pair<int, long long> solve(int i, int x) {
        if (has_cycle) return {-2, 0};
        if (dp_state[i][x] == 2) return {dp_dest[i][x], dp_cost[i][x]};
        if (dp_state[i][x] == 1) { has_cycle = true; return {-2, 0}; }
        dp_state[i][x] = 1;

        int dest;
        long long cost;

        if (i < n - 1) { // POP
            if (x == pop_val[i]) {
                dest = pop_goto[i];
                cost = 1;
            } else {
                auto [j, u] = solve(push_goto[i], push_val[i]);
                if (has_cycle) return {-2, 0};
                auto [k, v] = solve(j, x);
                if (has_cycle) return {-2, 0};
                dest = k;
                cost = (u + v + 1) % P;
            }
        } else { // HALT
            if (x == 0) {
                dest = -1;
                cost = 1;
            } else {
                auto [j, u] = solve(halt_goto, halt_push);
                if (has_cycle) return {-2, 0};
                auto [k, v] = solve(j, x);
                if (has_cycle) return {-2, 0};
                dest = k;
                cost = (u + v + 1) % P;
            }
        }

        dp_state[i][x] = 2;
        dp_dest[i][x] = dest;
        dp_cost[i][x] = cost;
        return {dest, cost};
    }
};

int main() {
    long long targets[2] = {150994941LL, 150994939LL};

    // For the chain structure, let's count distinct values with different push_val choices
    // Standard: push_val[i] = i+1, pop_goto[i] = i+1, and push_goto[i] varies
    // Generalized: also vary push_val[i] and pop_goto[i]

    // First, let's see how many distinct values we get for n=12 (11 POP + 1 HALT)
    // with the standard structure (just varying push_goto)
    // We already know: ~2^d = 2^11 = 2048

    // Let's try n=12 with varying BOTH push_goto[i] AND push_val[i]
    // push_val[i] can be 1..maxV
    // This might give us many more distinct values

    // Actually, let me think about what push_val does.
    // When instruction i doesn't match (x != i+1), it pushes push_val[i] and goes to push_goto[i].
    // The cost includes solve(push_goto[i], push_val[i]).second
    // Different push_val values lead to different sub-computations.
    // With push_val values from 1..V, we have V*n choices for (push_val, push_goto) at each instruction.

    // Let's test: for d=11 (n=12), with V=5, how many distinct T values?
    // That's (5*12)^11 configs for the generalized version... way too many.
    // But maybe even with 2 push values, we get much more diversity.

    // Let me try a different approach: use the chain structure but with generalized push_vals
    // and do hill climbing on both push_goto AND push_val.

    for (int n = 10; n <= 28; n++) {
        cerr << "n=" << n << endl;
        int d = n - 1; // number of POP instructions

        mt19937 rng(42 + n * 1000003);
        bool found[2] = {false, false};
        int foundConfig[2][35][2]; // [target][instr][push_val, push_goto]

        auto startTime = chrono::steady_clock::now();
        int timeLimit = (n <= 15) ? 15000 : (n <= 20) ? 8000 : 3000;

        for (int restart = 0; !(found[0] && found[1]); restart++) {
            auto now = chrono::steady_clock::now();
            auto ms = chrono::duration_cast<chrono::milliseconds>(now - startTime).count();
            if (ms > timeLimit) break;

            // Random initial config
            // pop_val[i] = i+1, pop_goto[i] = i+1 (always next)
            // push_val[i] random from 1..min(i+3, 20)
            // push_goto[i] random from 0..n-1
            // halt_push = 1, halt_goto = n-1

            Evaluator ev;
            ev.n = n;
            ev.pop_val.resize(d);
            ev.pop_goto.resize(d);
            ev.push_val.resize(d);
            ev.push_goto.resize(d);
            for (int i = 0; i < d; i++) {
                ev.pop_val[i] = i + 1;
                ev.pop_goto[i] = i + 1; // standard: next instruction
                int maxPV = min(i + 2, 10); // push values up to 10
                ev.push_val[i] = 1 + rng() % maxPV;
                ev.push_goto[i] = rng() % n;
            }
            ev.halt_push = 1;
            ev.halt_goto = d; // self-loop at HALT... this might cause cycles

            // Actually, halt_goto pointing to itself with push causes cycle
            // Let halt_goto point to a POP instruction instead
            ev.halt_goto = rng() % d; // point to some POP instruction

            ev.init();
            auto [dest, cost] = ev.solve(0, 0);
            if (ev.has_cycle) continue;

            // Hill climbing
            for (int iter = 0; iter < 50000; iter++) {
                for (int ti = 0; ti < 2; ti++) {
                    if (!found[ti] && cost == targets[ti]) {
                        found[ti] = true;
                        cerr << "FOUND n=" << n << " target" << (ti+1) << " cost=" << cost << endl;
                        // Print program
                        cout << "FOUND n=" << n << " target" << (ti+1) << ":" << endl;
                        cout << n << endl;
                        for (int i = 0; i < d; i++) {
                            cout << "POP " << ev.pop_val[i] << " GOTO " << (ev.pop_goto[i]+1)
                                 << " PUSH " << ev.push_val[i] << " GOTO " << (ev.push_goto[i]+1) << endl;
                        }
                        cout << "HALT PUSH " << ev.halt_push << " GOTO " << (ev.halt_goto+1) << endl;
                    }
                }
                if (found[0] && found[1]) break;

                // Mutate: change one push_val or push_goto
                int choice = rng() % (2 * d + 2); // 2*d for POP params + 2 for HALT params
                Evaluator ev2 = ev; // shallow copy the config (not DP)
                // Apply mutation
                if (choice < d) {
                    // Change push_val[choice]
                    int maxPV = min(choice + 2, 10);
                    ev2.push_val[choice] = 1 + rng() % maxPV;
                } else if (choice < 2*d) {
                    // Change push_goto[choice - d]
                    ev2.push_goto[choice - d] = rng() % n;
                } else if (choice == 2*d) {
                    // Change halt_push
                    ev2.halt_push = 1 + rng() % 10;
                } else {
                    // Change halt_goto
                    ev2.halt_goto = rng() % d;
                }

                ev2.init();
                auto [dest2, cost2] = ev2.solve(0, 0);
                if (ev2.has_cycle) continue;

                // Accept if closer to either target
                long long bestDist = P;
                for (int ti = 0; ti < 2; ti++) {
                    if (!found[ti]) {
                        long long dd = min((cost - targets[ti] + P) % P, (targets[ti] - cost + P) % P);
                        bestDist = min(bestDist, dd);
                    }
                }
                long long newBestDist = P;
                for (int ti = 0; ti < 2; ti++) {
                    if (!found[ti]) {
                        long long dd = min((cost2 - targets[ti] + P) % P, (targets[ti] - cost2 + P) % P);
                        newBestDist = min(newBestDist, dd);
                    }
                }

                if (newBestDist <= bestDist) {
                    ev.push_val = ev2.push_val;
                    ev.push_goto = ev2.push_goto;
                    ev.halt_push = ev2.halt_push;
                    ev.halt_goto = ev2.halt_goto;
                    cost = cost2;
                }
            }
        }

        cerr << "  found=" << found[0] << "," << found[1] << endl;
        if (found[0] && found[1]) break;
    }

    return 0;
}