docker_space/frontier_cs_8/fast_search2.cpp

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

static const long long P = 998244353;

// Fast evaluator for the generalized chain structure
// n instructions: POP[0]..POP[d-1], HALT[d] where d=n-1
// POP[i]: POP (i+1) GOTO (i+1) PUSH push_val[i] GOTO push_goto[i]
// HALT: HALT PUSH halt_push GOTO halt_goto
//
// Constraint for no cycles: push_goto[i] <= i (goes to same or earlier instruction)
// This ensures the recursion terminates because:
// - solve(i, v) for v != i+1 calls solve(push_goto[i], push_val[i]) where push_goto[i] <= i
//   This resolves to some instruction j <= i with some value x
//   Then calls solve(j, v)
//   Since j <= i and the chain makes progress, this terminates
//
// Actually, we need to be more careful. Let me use the standard chain constraint
// and just vary push_val.

// With the standard chain (push_goto[i] goes to some j <= i, pop_goto=i+1):
// The recursion for solve(i, x) where x != i+1:
//   First: solve(push_goto[i], push_val[i])
//     This pushes push_val[i] at instruction push_goto[i]
//     If push_val[i] == push_goto[i]+1, it matches immediately -> (push_goto[i]+1, 1)
//     If push_val[i] != push_goto[i]+1, it recurses deeper
//   Then: solve(result, x) processes x at the resulting instruction
//
// The key insight: if push_val[i] != i+1 (not the standard value),
// the behavior changes because the pushed value may or may not match at the target instruction.

// Let me compute the cost using iterative DP
// States: (instruction, value) where value in {0, 1, ..., maxVal}
// We process in topological order

struct State {
    int instr;
    int val;
};

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

    for (int n = 8; n <= 27; n++) {
        int d = n - 1;
        // Allow push values 1..d (same as pop values)
        // push_goto[i] in 0..i (goes to same or earlier)
        // halt_push in 1..d, halt_goto in 0..d-1

        cerr << "n=" << n << " d=" << d << endl;

        mt19937 rng(42 + n * 7777);
        bool found[2] = {false, false};

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

        long long total_attempts = 0;

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

            // Random config
            int push_val[30], push_goto[30];
            int halt_push, halt_goto;
            for (int i = 0; i < d; i++) {
                push_val[i] = 1 + rng() % d; // 1..d
                push_goto[i] = rng() % (i + 1); // 0..i
            }
            halt_push = 1 + rng() % d;
            halt_goto = rng() % d;

            // Evaluate using recursive DP with cycle detection
            // States: (instr 0..d, val 0..d)
            // val 0 = empty stack
            int maxVal = d;
            int nstates = (d + 1) * (maxVal + 1);
            vector<int> dest(nstates, -2);
            vector<long long> cost(nstates, 0);
            vector<int8_t> st(nstates, 0); // 0=unvisited, 1=in-progress, 2=done
            bool cycle = false;

            function<pair<int,long long>(int,int)> solve = [&](int i, int x) -> pair<int,long long> {
                int id = i * (maxVal + 1) + x;
                if (st[id] == 2) return {dest[id], cost[id]};
                if (st[id] == 1) { cycle = true; return {-2, 0}; }
                st[id] = 1;

                int dd; long long cc;
                if (i < d) { // POP
                    int pv = i + 1; // pop_val
                    if (x == pv) {
                        dd = i + 1; cc = 1; // pop, goto next
                    } else {
                        auto [j, u] = solve(push_goto[i], push_val[i]);
                        if (cycle) return {-2, 0};
                        if (j < 0 || j > d) { cycle = true; return {-2, 0}; }
                        auto [k, v] = solve(j, x);
                        if (cycle) return {-2, 0};
                        dd = k; cc = (u + v + 1) % P;
                    }
                } else { // HALT (i == d)
                    if (x == 0) {
                        dd = -1; cc = 1;
                    } else {
                        auto [j, u] = solve(halt_goto, halt_push);
                        if (cycle) return {-2, 0};
                        if (j < 0 || j > d) { cycle = true; return {-2, 0}; }
                        auto [k, v] = solve(j, x);
                        if (cycle) return {-2, 0};
                        dd = k; cc = (u + v + 1) % P;
                    }
                }

                st[id] = 2; dest[id] = dd; cost[id] = cc;
                return {dd, cc};
            };

            auto [_, T] = solve(0, 0);
            total_attempts++;
            if (cycle) continue;

            // Hill climbing
            for (int iter = 0; iter < 30000; iter++) {
                for (int ti = 0; ti < 2; ti++) {
                    if (!found[ti] && T == targets[ti]) {
                        found[ti] = true;
                        cerr << "FOUND n=" << n << " target" << (ti+1) << " T=" << T << endl;
                        cout << "TARGET" << (ti+1) << " n=" << n << endl;
                        cout << n << endl;
                        for (int i = 0; i < d; i++) {
                            cout << "POP " << (i+1) << " GOTO " << (i+2)
                                 << " PUSH " << push_val[i] << " GOTO " << (push_goto[i]+1) << endl;
                        }
                        cout << "HALT PUSH " << halt_push << " GOTO " << (halt_goto+1) << endl;
                    }
                }
                if (found[0] && found[1]) break;

                // Mutate
                int save_pv, save_pg, save_idx, save_hp, save_hg;
                int mut = rng() % 3;
                if (mut == 0 && d > 0) {
                    save_idx = rng() % d;
                    save_pv = push_val[save_idx];
                    push_val[save_idx] = 1 + rng() % d;
                } else if (mut == 1 && d > 0) {
                    save_idx = rng() % d;
                    save_pg = push_goto[save_idx];
                    push_goto[save_idx] = rng() % (save_idx + 1);
                } else {
                    save_hp = halt_push; save_hg = halt_goto;
                    halt_push = 1 + rng() % d;
                    halt_goto = rng() % d;
                    mut = 2;
                }

                // Re-evaluate
                fill(st.begin(), st.end(), (int8_t)0);
                cycle = false;
                auto [_d, nT] = solve(0, 0);
                total_attempts++;

                bool accept = false;
                if (!cycle) {
                    long long bestOld = P, bestNew = P;
                    for (int ti = 0; ti < 2; ti++) {
                        if (!found[ti]) {
                            bestOld = min(bestOld, min((T - targets[ti] + P) % P, (targets[ti] - T + P) % P));
                            bestNew = min(bestNew, min((nT - targets[ti] + P) % P, (targets[ti] - nT + P) % P));
                        }
                    }
                    accept = (bestNew <= bestOld);
                }

                if (accept) {
                    T = nT;
                } else {
                    if (mut == 0) push_val[save_idx] = save_pv;
                    else if (mut == 1) push_goto[save_idx] = save_pg;
                    else { halt_push = save_hp; halt_goto = save_hg; }
                }
            }
        }

        auto ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - startTime).count();
        cerr << "  attempts=" << total_attempts << " time=" << ms << "ms found=" << found[0] << "," << found[1] << endl;
        if (found[0] && found[1]) break;
    }

    return 0;
}