Add files using upload-large-folder tool

1fd0050 verified 6 months ago

7.77 kB

// Ladder construction: try to get T > 2^(d+1)-1 with d POPs
// by using non-standard push chars that create cross-references.
//
// Consider d=26 (n=27). Standard chain max T = 2^27-1 = 134M.
// We need T = 150M.
//
// What if POP j pushes char (j+1) [standard] but goes to a deeper goto?
// In the standard chain, solve(j, x) for x != j+1:
//   cost = 1 + solve(gy[j], j+1).steps + solve(j+1, x).steps
//   where solve(gy[j], j+1) traverses from gy[j] to j (cost depends on gy[j])
//   and solve(j+1, x) continues the chain.
//
// With gy[j]=0 for all j: solve(j, x) = 2^(j+1) * solve_x_factor + stuff
// Each level doubles.
//
// What if some instruction pushes a char that causes the resolve step
// to call MULTIPLE pops? E.g., if POP 5 pushes char 3 instead of char 6,
// then solve(gy[5], 3) goes to gy[5], and char 3 gets popped by POP 2
// (which pops char 3). But to reach POP 2 from gy[5], we might traverse
// through POPs 0-2, each adding their own costs.
//
// Wait, that's the same as setting gy[5] to a different value.
// Actually no - the push_char determines WHICH POP consumes the push.
// In standard chain: push_char = j+1, consumed by POP j itself.
// If push_char = 3 (for POP 5), consumed by POP 2.
// Then solve(gy[5], 3) returns at POP 2's goto = 3.
// Then solve(3, x) continues from POP 3.
// But we skipped POPs 3, 4! The resolve step only went to POP 2.
//
// Actually this makes the resolve step SHORTER, not longer.
// To make it LONGER, we want push_char to NOT match any POP's pop_char.
// If push_char = d+1 (a char no POP pops), then the char propagates all the way
// to HALT. HALT processes it by pushing something else and recursing.
// This could create much deeper recursion!
//
// Let me try: d POP instructions that all pop chars 1..d.
// Some POPs push char d+1 (which NO POP pops).
// HALT pushes char 1 and goes to some instruction.
// When char d+1 reaches HALT, HALT pushes char 1 and continues.
// Char 1 gets popped by POP 0, which goes to POP 1.
// So the "resolve" for char d+1 goes through the entire chain AND the HALT.

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

constexpr long long P = 998244353;

// General program: n instructions
// Each instruction is POP or HALT with given params
// Solve by checker's recursive method

struct Program {
    int n;
    int type[30];     // 0=POP, 1=HALT
    int pop_c[30];    // POP char (for POP)
    int goto1[30];    // goto on pop match (for POP)
    int push_c[30];   // push char
    int goto2[30];    // goto on push

    optional<pair<int, long long>> dp[30][40];
    bool vis[30][40];
    bool inf;
    int maxC;

    void clear_dp() {
        for (int i = 0; i < n; i++)
            for (int j = 0; j <= maxC; j++) {
                dp[i][j].reset();
                vis[i][j] = false;
            }
        inf = false;
    }

    pair<int, long long> solve(int i, int x) {
        if (dp[i][x]) return dp[i][x].value();
        if (vis[i][x]) { inf = true; return {-1, 0}; }
        vis[i][x] = true;

        if (type[i] == 0) {
            if (x == pop_c[i]) {
                dp[i][x] = {goto1[i], 1LL};
            } else {
                auto [j, u] = solve(goto2[i], push_c[i]);
                if (inf) return {-1, 0};
                auto [k, v] = solve(j, x);
                if (inf) return {-1, 0};
                dp[i][x] = {k, (u + v + 1) % P};
            }
        } else {
            if (x == 0) {
                dp[i][x] = {-1, 1LL};
            } else {
                auto [j, u] = solve(goto2[i], push_c[i]);
                if (inf) return {-1, 0};
                auto [k, v] = solve(j, x);
                if (inf) return {-1, 0};
                dp[i][x] = {k, (u + v + 1) % P};
            }
        }
        return dp[i][x].value();
    }

    long long eval() {
        clear_dp();
        auto [fi, steps] = solve(0, 0);
        if (inf) return -1;
        return steps;
    }
};

int main() {
    long long target1 = 150994941;
    long long target2 = 150994939;

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

    // Try specific construction: d POP + 1 HALT
    // POP j: pop char (j+1), goto (j+2) [next POP or HALT]
    //        push char push_c[j], goto push_g[j]
    // HALT d: push char halt_c, goto halt_g
    //
    // Chars used: 1..d for pop_chars, plus additional chars for push.
    // If push_c[j] > d: no POP pops this char, so it propagates to HALT.
    // HALT then pushes halt_c and continues.
    //
    // This creates a more complex recursion than a simple chain.

    for (int d = 15; d <= 26; d++) {
        int n = d + 1;
        Program prog;
        prog.n = n;
        int maxPushChar = d + 3; // allow a few extra chars
        prog.maxC = maxPushChar;

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

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

        bool found = false;

        for (int restart = 0; dElapsed() < 8000 && !found; restart++) {
            // Setup structure
            for (int j = 0; j < d; j++) {
                prog.type[j] = 0;
                prog.pop_c[j] = j + 1;
                prog.goto1[j] = j + 1; // standard: next instruction
                prog.push_c[j] = 1 + rng() % maxPushChar;
                prog.goto2[j] = rng() % n;
            }
            prog.type[d] = 1;
            prog.push_c[d] = 1 + rng() % maxPushChar;
            prog.goto2[d] = rng() % n;

            long long T = prog.eval();
            if (T < 0) continue;

            for (int iter = 0; iter < 300000 && !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",
                            prog.pop_c[j], prog.goto1[j]+1, prog.push_c[j], prog.goto2[j]+1);
                    }
                    printf("HALT PUSH %d GOTO %d\n", prog.push_c[d], prog.goto2[d]+1);
                    break;
                }

                // Mutate
                int j = rng() % n;
                int what = rng() % 3;
                int sv_push = prog.push_c[j], sv_g2 = prog.goto2[j], sv_g1 = prog.goto1[j];

                if (what == 0) prog.push_c[j] = 1 + rng() % maxPushChar;
                else if (what == 1) prog.goto2[j] = rng() % n;
                else if (j < d) prog.goto1[j] = rng() % n; // vary pop goto too

                long long nT = prog.eval();
                if (nT < 0) {
                    prog.push_c[j] = sv_push; prog.goto2[j] = sv_g2; prog.goto1[j] = sv_g1;
                    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 {
                    prog.push_c[j] = sv_push; prog.goto2[j] = sv_g2; prog.goto1[j] = sv_g1;
                }
            }

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

        if (found) return 0;
    }

    return 0;
}

	// Ladder construction: try to get T > 2^(d+1)-1 with d POPs
	// by using non-standard push chars that create cross-references.
	//
	// Consider d=26 (n=27). Standard chain max T = 2^27-1 = 134M.
	// We need T = 150M.
	//
	// What if POP j pushes char (j+1) [standard] but goes to a deeper goto?
	// In the standard chain, solve(j, x) for x != j+1:
	// cost = 1 + solve(gy[j], j+1).steps + solve(j+1, x).steps
	// where solve(gy[j], j+1) traverses from gy[j] to j (cost depends on gy[j])
	// and solve(j+1, x) continues the chain.
	//
	// With gy[j]=0 for all j: solve(j, x) = 2^(j+1) * solve_x_factor + stuff
	// Each level doubles.
	//
	// What if some instruction pushes a char that causes the resolve step
	// to call MULTIPLE pops? E.g., if POP 5 pushes char 3 instead of char 6,
	// then solve(gy[5], 3) goes to gy[5], and char 3 gets popped by POP 2
	// (which pops char 3). But to reach POP 2 from gy[5], we might traverse
	// through POPs 0-2, each adding their own costs.
	//
	// Wait, that's the same as setting gy[5] to a different value.
	// Actually no - the push_char determines WHICH POP consumes the push.
	// In standard chain: push_char = j+1, consumed by POP j itself.
	// If push_char = 3 (for POP 5), consumed by POP 2.
	// Then solve(gy[5], 3) returns at POP 2's goto = 3.
	// Then solve(3, x) continues from POP 3.
	// But we skipped POPs 3, 4! The resolve step only went to POP 2.
	//
	// Actually this makes the resolve step SHORTER, not longer.
	// To make it LONGER, we want push_char to NOT match any POP's pop_char.
	// If push_char = d+1 (a char no POP pops), then the char propagates all the way
	// to HALT. HALT processes it by pushing something else and recursing.
	// This could create much deeper recursion!
	//
	// Let me try: d POP instructions that all pop chars 1..d.
	// Some POPs push char d+1 (which NO POP pops).
	// HALT pushes char 1 and goes to some instruction.
	// When char d+1 reaches HALT, HALT pushes char 1 and continues.
	// Char 1 gets popped by POP 0, which goes to POP 1.
	// So the "resolve" for char d+1 goes through the entire chain AND the HALT.

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

	constexpr long long P = 998244353;

	// General program: n instructions
	// Each instruction is POP or HALT with given params
	// Solve by checker's recursive method

	struct Program {
	int n;
	int type[30]; // 0=POP, 1=HALT
	int pop_c[30]; // POP char (for POP)
	int goto1[30]; // goto on pop match (for POP)
	int push_c[30]; // push char
	int goto2[30]; // goto on push

	optional<pair<int, long long>> dp[30][40];
	bool vis[30][40];
	bool inf;
	int maxC;

	void clear_dp() {
	for (int i = 0; i < n; i++)
	for (int j = 0; j <= maxC; j++) {
	dp[i][j].reset();
	vis[i][j] = false;
	}
	inf = false;
	}

	pair<int, long long> solve(int i, int x) {
	if (dp[i][x]) return dp[i][x].value();
	if (vis[i][x]) { inf = true; return {-1, 0}; }
	vis[i][x] = true;

	if (type[i] == 0) {
	if (x == pop_c[i]) {
	dp[i][x] = {goto1[i], 1LL};
	} else {
	auto [j, u] = solve(goto2[i], push_c[i]);
	if (inf) return {-1, 0};
	auto [k, v] = solve(j, x);
	if (inf) return {-1, 0};
	dp[i][x] = {k, (u + v + 1) % P};
	}
	} else {
	if (x == 0) {
	dp[i][x] = {-1, 1LL};
	} else {
	auto [j, u] = solve(goto2[i], push_c[i]);
	if (inf) return {-1, 0};
	auto [k, v] = solve(j, x);
	if (inf) return {-1, 0};
	dp[i][x] = {k, (u + v + 1) % P};
	}
	}
	return dp[i][x].value();
	}

	long long eval() {
	clear_dp();
	auto [fi, steps] = solve(0, 0);
	if (inf) return -1;
	return steps;
	}
	};

	int main() {
	long long target1 = 150994941;
	long long target2 = 150994939;

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

	// Try specific construction: d POP + 1 HALT
	// POP j: pop char (j+1), goto (j+2) [next POP or HALT]
	// push char push_c[j], goto push_g[j]
	// HALT d: push char halt_c, goto halt_g
	//
	// Chars used: 1..d for pop_chars, plus additional chars for push.
	// If push_c[j] > d: no POP pops this char, so it propagates to HALT.
	// HALT then pushes halt_c and continues.
	//
	// This creates a more complex recursion than a simple chain.

	for (int d = 15; d <= 26; d++) {
	int n = d + 1;
	Program prog;
	prog.n = n;
	int maxPushChar = d + 3; // allow a few extra chars
	prog.maxC = maxPushChar;

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

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

	bool found = false;

	for (int restart = 0; dElapsed() < 8000 && !found; restart++) {
	// Setup structure
	for (int j = 0; j < d; j++) {
	prog.type[j] = 0;
	prog.pop_c[j] = j + 1;
	prog.goto1[j] = j + 1; // standard: next instruction
	prog.push_c[j] = 1 + rng() % maxPushChar;
	prog.goto2[j] = rng() % n;
	}
	prog.type[d] = 1;
	prog.push_c[d] = 1 + rng() % maxPushChar;
	prog.goto2[d] = rng() % n;

	long long T = prog.eval();
	if (T < 0) continue;

	for (int iter = 0; iter < 300000 && !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",
	prog.pop_c[j], prog.goto1[j]+1, prog.push_c[j], prog.goto2[j]+1);
	}
	printf("HALT PUSH %d GOTO %d\n", prog.push_c[d], prog.goto2[d]+1);
	break;
	}

	// Mutate
	int j = rng() % n;
	int what = rng() % 3;
	int sv_push = prog.push_c[j], sv_g2 = prog.goto2[j], sv_g1 = prog.goto1[j];

	if (what == 0) prog.push_c[j] = 1 + rng() % maxPushChar;
	else if (what == 1) prog.goto2[j] = rng() % n;
	else if (j < d) prog.goto1[j] = rng() % n; // vary pop goto too

	long long nT = prog.eval();
	if (nT < 0) {
	prog.push_c[j] = sv_push; prog.goto2[j] = sv_g2; prog.goto1[j] = sv_g1;
	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 {
	prog.push_c[j] = sv_push; prog.goto2[j] = sv_g2; prog.goto1[j] = sv_g1;
	}
	}

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

	if (found) return 0;
	}

	return 0;
	}