Add files using upload-large-folder tool

1fd0050 verified 6 months ago

6.77 kB

// Chain program with larger alphabet to enable modular arithmetic
//
// Key idea: Use a chain of d POP instructions where:
// - POP j pops char (j+1), pushes char p[j], goto g[j]
// - HALT at d: push char 1, goto d
//
// In the standard chain, p[j] = j+1 (same as pop char).
// But if p[j] is a DIFFERENT char that doesn't get popped until later,
// it creates longer recursion chains.
//
// Actually, the chain formula computeT already captures ALL chain-structured programs.
// The push_char doesn't matter in the chain formula because:
// - POP j pushes char (j+1) [in the standard construction]
// - What matters is where the pushed char gets popped (the goto target)
// - The push_char just determines which POP pops it
//
// Wait, actually the push char DOES matter! If POP j pushes char c and c != (j+1),
// then char c might be popped by a DIFFERENT instruction than j.
// This changes which states are visited!
//
// Let me reconsider. In the general case:
// POP j: pop_char = a[j], goto1 = g1[j], push_char = b[j], goto2 = g2[j]
//
// solve(j, x): if x == a[j]: goto g1[j], steps = 1
//   else: solve(g2[j], b[j]) -> (ret_j, cost_j). Then solve(ret_j, x) -> (ret_k, cost_k).
//     Result: (ret_k, cost_j + cost_k + 1)
//
// The chain formula assumes: a[j] = j+1, b[j] = j+1, g1[j] = j+1
// Only g2[j] varies (= gy[j]).
// Under these assumptions, solve(g2[j], j+1) traverses from g2[j] to j+1
// because POP j is the unique instruction that pops char j+1.
//
// But if we allow a[j] and b[j] to vary:
// - a[j] = j+1 (each POP pops a unique char)
// - b[j] can be any char in {1..maxChar}
// - If b[j] = k+1 for some k != j, then solve(g2[j], k+1) will eventually
//   reach POP k which pops char k+1.
//
// This creates CROSS-LINKS in the recursion, which can increase step counts!
//
// Let me implement this generalized chain and search over it.

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

constexpr long long P = 998244353;

// Generalized chain with d POP instructions + 1 HALT
// POP j: pop char (j+1), goto (j+1), push char push_c[j], goto push_g[j]
// HALT d: push char 1, goto d

int d_val;
int push_c[35]; // push_c[j] in {1..d}
int push_g[35]; // push_g[j] in {0..d-1}

// We use the checker's recursive solve
optional<pair<int, long long>> dp[35][35]; // dp[instr][char], char 0=empty, 1..d
bool vis[35][35];
bool inf_flag;

// Instructions:
// 0..d-1: POP (i+1) GOTO (i+1) PUSH push_c[i] GOTO push_g[i]
// d: HALT PUSH 1 GOTO d
pair<int, long long> solve(int i, int x) {
    if (dp[i][x]) return dp[i][x].value();
    if (vis[i][x]) { inf_flag = true; return {-1, 0}; }
    vis[i][x] = true;

    if (i < d_val) {
        // POP instruction: pops char (i+1)
        if (x == i + 1) {
            dp[i][x] = {i + 1, 1LL}; // goto i+1
        } else {
            auto [j, u] = solve(push_g[i], push_c[i]);
            if (inf_flag) return {-1, 0};
            auto [k, v] = solve(j, x);
            if (inf_flag) return {-1, 0};
            dp[i][x] = {k, (u + v + 1) % P};
        }
    } else {
        // HALT instruction
        if (x == 0) {
            dp[i][x] = {-1, 1LL};
        } else {
            auto [j, u] = solve(d_val, 1); // push 1, goto d
            if (inf_flag) return {-1, 0};
            auto [k, v] = solve(j, x);
            if (inf_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 <= d_val; i++)
        for (int j = 0; j <= d_val; j++) {
            dp[i][j].reset();
            vis[i][j] = false;
        }
    inf_flag = false;
    auto [fi, steps] = solve(0, 0);
    if (inf_flag) return -1;
    return steps;
}

int main(int argc, char* argv[]) {
    long long target1 = 150994941;
    long long target2 = 150994939;

    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();
    };

    // Try d from small to large
    for (int d = 20; d <= 26; d++) {
        d_val = d;
        int n = d + 1;

        fprintf(stderr, "=== d=%d (n=%d) ===\n", d, n);

        int timeLimit = 10000; // 10s per d value
        auto dStart = chrono::steady_clock::now();
        auto dElapsed = [&]() {
            return chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - dStart).count();
        };

        bool found = false;
        int restarts = 0;

        while (dElapsed() < timeLimit && !found) {
            restarts++;

            // Random init
            for (int j = 0; j < d; j++) {
                push_c[j] = 1 + rng() % d; // char in {1..d}
                push_g[j] = rng() % d;      // goto in {0..d-1}
            }

            long long T = evaluate();
            if (T < 0) continue;

            for (int iter = 0; iter < 200000 && !found; iter++) {
                if (T == target1 || T == target2) {
                    found = true;
                    fprintf(stderr, "FOUND! d=%d n=%d T=%lld\n", d, n, T);
                    printf("%d\n", n);
                    for (int j = 0; j < d; j++) {
                        printf("POP %d GOTO %d PUSH %d GOTO %d\n",
                            j+1, j+2, push_c[j], push_g[j]+1);
                    }
                    printf("HALT PUSH 1 GOTO %d\n", n);
                    break;
                }

                // Mutate one parameter
                int j = rng() % d;
                int what = rng() % 2;
                int sv_c = push_c[j], sv_g = push_g[j];
                if (what == 0) push_c[j] = 1 + rng() % d;
                else push_g[j] = rng() % d;

                long long nT = evaluate();
                if (nT < 0) {
                    push_c[j] = sv_c; push_g[j] = sv_g;
                    continue;
                }

                long long nd1 = min((nT - target1 + P) % P, (target1 - nT + P) % P);
                long long od1 = min((T - target1 + P) % P, (target1 - T + P) % P);
                long long nd2 = min((nT - target2 + P) % P, (target2 - nT + P) % P);
                long long od2 = min((T - target2 + P) % P, (target2 - T + P) % P);
                long long best_nd = min(nd1, nd2);
                long long best_od = min(od1, od2);

                if (best_nd <= best_od) T = nT;
                else { push_c[j] = sv_c; push_g[j] = sv_g; }
            }

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

        if (found) return 0;
        fprintf(stderr, "d=%d: not found after %d restarts\n", d, restarts);
    }

    return 0;
}

	// Chain program with larger alphabet to enable modular arithmetic
	//
	// Key idea: Use a chain of d POP instructions where:
	// - POP j pops char (j+1), pushes char p[j], goto g[j]
	// - HALT at d: push char 1, goto d
	//
	// In the standard chain, p[j] = j+1 (same as pop char).
	// But if p[j] is a DIFFERENT char that doesn't get popped until later,
	// it creates longer recursion chains.
	//
	// Actually, the chain formula computeT already captures ALL chain-structured programs.
	// The push_char doesn't matter in the chain formula because:
	// - POP j pushes char (j+1) [in the standard construction]
	// - What matters is where the pushed char gets popped (the goto target)
	// - The push_char just determines which POP pops it
	//
	// Wait, actually the push char DOES matter! If POP j pushes char c and c != (j+1),
	// then char c might be popped by a DIFFERENT instruction than j.
	// This changes which states are visited!
	//
	// Let me reconsider. In the general case:
	// POP j: pop_char = a[j], goto1 = g1[j], push_char = b[j], goto2 = g2[j]
	//
	// solve(j, x): if x == a[j]: goto g1[j], steps = 1
	// else: solve(g2[j], b[j]) -> (ret_j, cost_j). Then solve(ret_j, x) -> (ret_k, cost_k).
	// Result: (ret_k, cost_j + cost_k + 1)
	//
	// The chain formula assumes: a[j] = j+1, b[j] = j+1, g1[j] = j+1
	// Only g2[j] varies (= gy[j]).
	// Under these assumptions, solve(g2[j], j+1) traverses from g2[j] to j+1
	// because POP j is the unique instruction that pops char j+1.
	//
	// But if we allow a[j] and b[j] to vary:
	// - a[j] = j+1 (each POP pops a unique char)
	// - b[j] can be any char in {1..maxChar}
	// - If b[j] = k+1 for some k != j, then solve(g2[j], k+1) will eventually
	// reach POP k which pops char k+1.
	//
	// This creates CROSS-LINKS in the recursion, which can increase step counts!
	//
	// Let me implement this generalized chain and search over it.

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

	constexpr long long P = 998244353;

	// Generalized chain with d POP instructions + 1 HALT
	// POP j: pop char (j+1), goto (j+1), push char push_c[j], goto push_g[j]
	// HALT d: push char 1, goto d

	int d_val;
	int push_c[35]; // push_c[j] in {1..d}
	int push_g[35]; // push_g[j] in {0..d-1}

	// We use the checker's recursive solve
	optional<pair<int, long long>> dp[35][35]; // dp[instr][char], char 0=empty, 1..d
	bool vis[35][35];
	bool inf_flag;

	// Instructions:
	// 0..d-1: POP (i+1) GOTO (i+1) PUSH push_c[i] GOTO push_g[i]
	// d: HALT PUSH 1 GOTO d
	pair<int, long long> solve(int i, int x) {
	if (dp[i][x]) return dp[i][x].value();
	if (vis[i][x]) { inf_flag = true; return {-1, 0}; }
	vis[i][x] = true;

	if (i < d_val) {
	// POP instruction: pops char (i+1)
	if (x == i + 1) {
	dp[i][x] = {i + 1, 1LL}; // goto i+1
	} else {
	auto [j, u] = solve(push_g[i], push_c[i]);
	if (inf_flag) return {-1, 0};
	auto [k, v] = solve(j, x);
	if (inf_flag) return {-1, 0};
	dp[i][x] = {k, (u + v + 1) % P};
	}
	} else {
	// HALT instruction
	if (x == 0) {
	dp[i][x] = {-1, 1LL};
	} else {
	auto [j, u] = solve(d_val, 1); // push 1, goto d
	if (inf_flag) return {-1, 0};
	auto [k, v] = solve(j, x);
	if (inf_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 <= d_val; i++)
	for (int j = 0; j <= d_val; j++) {
	dp[i][j].reset();
	vis[i][j] = false;
	}
	inf_flag = false;
	auto [fi, steps] = solve(0, 0);
	if (inf_flag) return -1;
	return steps;
	}

	int main(int argc, char* argv[]) {
	long long target1 = 150994941;
	long long target2 = 150994939;

	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();
	};

	// Try d from small to large
	for (int d = 20; d <= 26; d++) {
	d_val = d;
	int n = d + 1;

	fprintf(stderr, "=== d=%d (n=%d) ===\n", d, n);

	int timeLimit = 10000; // 10s per d value
	auto dStart = chrono::steady_clock::now();
	auto dElapsed = [&]() {
	return chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - dStart).count();
	};

	bool found = false;
	int restarts = 0;

	while (dElapsed() < timeLimit && !found) {
	restarts++;

	// Random init
	for (int j = 0; j < d; j++) {
	push_c[j] = 1 + rng() % d; // char in {1..d}
	push_g[j] = rng() % d; // goto in {0..d-1}
	}

	long long T = evaluate();
	if (T < 0) continue;

	for (int iter = 0; iter < 200000 && !found; iter++) {
	if (T == target1 \|\| T == target2) {
	found = true;
	fprintf(stderr, "FOUND! d=%d n=%d T=%lld\n", d, n, T);
	printf("%d\n", n);
	for (int j = 0; j < d; j++) {
	printf("POP %d GOTO %d PUSH %d GOTO %d\n",
	j+1, j+2, push_c[j], push_g[j]+1);
	}
	printf("HALT PUSH 1 GOTO %d\n", n);
	break;
	}

	// Mutate one parameter
	int j = rng() % d;
	int what = rng() % 2;
	int sv_c = push_c[j], sv_g = push_g[j];
	if (what == 0) push_c[j] = 1 + rng() % d;
	else push_g[j] = rng() % d;

	long long nT = evaluate();
	if (nT < 0) {
	push_c[j] = sv_c; push_g[j] = sv_g;
	continue;
	}

	long long nd1 = min((nT - target1 + P) % P, (target1 - nT + P) % P);
	long long od1 = min((T - target1 + P) % P, (target1 - T + P) % P);
	long long nd2 = min((nT - target2 + P) % P, (target2 - nT + P) % P);
	long long od2 = min((T - target2 + P) % P, (target2 - T + P) % P);
	long long best_nd = min(nd1, nd2);
	long long best_od = min(od1, od2);

	if (best_nd <= best_od) T = nT;
	else { push_c[j] = sv_c; push_g[j] = sv_g; }
	}

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

	if (found) return 0;
	fprintf(stderr, "d=%d: not found after %d restarts\n", d, restarts);
	}

	return 0;
	}