docker_space/frontier_cs_8/aggressive_search.cpp

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

static const long long P = 998244353;

long long Sv[35];

inline long long computeT(int d, const int* gy) {
    Sv[0] = 0;
    for (int j = 0; j < d; j++) {
        long long c = ((Sv[j] - Sv[gy[j]] + (j - gy[j]) + 1) % P + P) % P;
        Sv[j + 1] = (Sv[j] + c) % P;
    }
    return (Sv[d] + d + 1) % P;
}

int main(int argc, char** argv) {
    long long target;
    int minD = 20, maxD = 27;

    if (argc >= 2) target = atoll(argv[1]);
    else target = 150994941LL; // default: target1

    if (argc >= 3) minD = atoi(argv[2]);
    if (argc >= 4) maxD = atoi(argv[3]);

    cerr << "Target: " << target << " searching d=" << minD << ".." << maxD << endl;

    mt19937 rng(target * 1000003ULL + 42);

    for (int d = minD; d <= maxD; d++) {
        cerr << "Trying d=" << d << " (n=" << (d+1) << ")" << endl;

        auto startTime = chrono::steady_clock::now();
        int timeLimit = 30000; // 30s per d

        int gy[35];
        int bestGy[35];
        bool found = false;
        long long attempts = 0;

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

            // Random restart
            gy[0] = 0;
            for (int j = 1; j < d; j++) gy[j] = rng() % (j + 1);
            long long T = computeT(d, gy);

            if (T == target) { found = true; memcpy(bestGy, gy, sizeof(int)*d); break; }

            // Aggressive hill climbing with restarts
            long long bestDist = min((T - target + P) % P, (target - T + P) % P);

            int noImprove = 0;
            for (int iter = 0; iter < 200000 && !found; iter++) {
                // Try modifying 1 or 2 positions
                int nmod = (rng() % 4 == 0) ? 2 : 1;
                int saved_j[2], saved_g[2];

                for (int m = 0; m < nmod; m++) {
                    int j = 1 + rng() % (d - 1);
                    saved_j[m] = j;
                    saved_g[m] = gy[j];
                    gy[j] = rng() % (j + 1);
                }

                long long nT = computeT(d, gy);
                if (nT == target) {
                    found = true;
                    memcpy(bestGy, gy, sizeof(int)*d);
                    break;
                }

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

                if (nd < bestDist) {
                    T = nT;
                    bestDist = nd;
                    noImprove = 0;
                } else if (nd == bestDist && (rng() % 2 == 0)) {
                    // Accept sideways move with 50% probability
                    T = nT;
                    noImprove++;
                } else {
                    // Revert
                    for (int m = nmod - 1; m >= 0; m--) {
                        gy[saved_j[m]] = saved_g[m];
                    }
                    noImprove++;
                }

                // If stuck, do a bigger perturbation
                if (noImprove > 500) {
                    int nflip = 2 + rng() % (d / 3);
                    for (int f = 0; f < nflip; f++) {
                        int j = 1 + rng() % (d - 1);
                        gy[j] = rng() % (j + 1);
                    }
                    T = computeT(d, gy);
                    bestDist = min((T - target + P) % P, (target - T + P) % P);
                    if (T == target) { found = true; memcpy(bestGy, gy, sizeof(int)*d); }
                    noImprove = 0;
                }

                attempts++;
            }
        }

        auto ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - startTime).count();
        cerr << "  attempts=" << attempts << " time=" << ms << "ms found=" << found << endl;

        if (found) {
            cout << "FOUND d=" << d << " gy:";
            for (int j = 0; j < d; j++) cout << " " << bestGy[j];
            cout << endl;

            // Verify
            long long T = computeT(d, bestGy);
            cout << "T=" << T << " target=" << target << " match=" << (T == target) << endl;

            // Output program
            cout << (d+1) << endl;
            for (int j = 0; j < d; j++) {
                cout << "POP " << (j+1) << " GOTO " << (j+2)
                     << " PUSH " << (j+1) << " GOTO " << (bestGy[j]+1) << endl;
            }
            cout << "HALT PUSH 1 GOTO " << (d+1) << endl;
            break;
        }
    }

    return 0;
}