docker_space/frontier_cs_8/intensive_search.cpp

// Intensive hill climbing / SA search for minimum d
// For each d from 20 to 26, run many restarts with SA
#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[]) {
    if (argc < 3) {
        cerr << "Usage: " << argv[0] << " <target_mod_P> <d>" << endl;
        return 1;
    }
    long long target = atoll(argv[1]);
    int d = atoi(argv[2]);

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

    int gy[35];
    long long bestDist = P;
    int bestGy[35];
    bool found = false;

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

    int restarts = 0;
    long long total_iters = 0;

    while (elapsed_ms() < 60000 && !found) {  // 60 seconds
        restarts++;
        // Random init
        memset(gy, 0, sizeof(int) * d);
        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; }

        // Simulated annealing
        double temp = 1e18;
        double coolRate = 0.99999;
        int noImprove = 0;

        for (int iter = 0; iter < 500000; iter++) {
            total_iters++;
            int j = 1 + rng() % (d - 1);
            int og = gy[j];
            int ng = rng() % (j + 1);
            if (ng == og) continue;
            gy[j] = ng;
            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);
            long long od = min((T - target + P) % P, (target - T + P) % P);

            if (nd < od) {
                T = nT;
                if (nd < bestDist) {
                    bestDist = nd;
                    memcpy(bestGy, gy, sizeof(int) * d);
                }
            } else {
                // SA acceptance
                double delta = (double)(nd - od);
                if (rng() % 1000000 < (int)(1000000.0 * exp(-delta / temp))) {
                    T = nT;
                } else {
                    gy[j] = og;
                }
            }
            temp *= coolRate;
        }
        if (found) break;
    }

    if (found) {
        cerr << "FOUND d=" << d << " after " << restarts << " restarts, " << total_iters << " iters" << endl;
        cerr << "gy[] =";
        for (int j = 0; j < d; j++) cerr << " " << bestGy[j];
        cerr << endl;
        // Verify
        long long verify = computeT(d, bestGy);
        cerr << "T=" << verify << " target=" << target << " match=" << (verify == target) << endl;
        // Output program
        int n = d + 1;
        cout << n << 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 " << n << endl;
    } else {
        cerr << "NOT FOUND d=" << d << " after " << restarts << " restarts, " << total_iters << " iters, best_dist=" << bestDist << endl;
    }

    return 0;
}