File size: 8,959 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 | #include <bits/stdc++.h>
using namespace std;
static const long long P = 998244353;
// Generalized chain: n-1 POP instructions + 1 HALT
// POP instruction i: POP (i+1) GOTO pop_goto[i] PUSH push_val[i] GOTO push_goto[i]
// HALT instruction (n-1): HALT PUSH halt_push GOTO halt_goto
//
// The standard chain has pop_goto[i]=i+1, push_val[i]=i+1, push_goto[i] varies
// Let's generalize by allowing push_val and push_goto to vary more
// For the checker DP, we need to simulate it properly
// State: (instr, top_of_stack_value)
struct Evaluator {
int n;
// POP instructions 0..n-2
vector<int> pop_val; // = i+1 always
vector<int> pop_goto; // where to go when matched
vector<int> push_val; // what to push
vector<int> push_goto; // where to go when not matched
// HALT instruction n-1
int halt_push;
int halt_goto;
// DP
vector<array<int, 1025>> dp_dest;
vector<array<long long, 1025>> dp_cost;
vector<array<int8_t, 1025>> dp_state; // 0=unvisited, 1=in-progress, 2=done
bool has_cycle;
void init() {
dp_dest.assign(n, array<int, 1025>{});
dp_cost.assign(n, array<long long, 1025>{});
dp_state.assign(n, array<int8_t, 1025>{});
has_cycle = false;
}
pair<int, long long> solve(int i, int x) {
if (has_cycle) return {-2, 0};
if (dp_state[i][x] == 2) return {dp_dest[i][x], dp_cost[i][x]};
if (dp_state[i][x] == 1) { has_cycle = true; return {-2, 0}; }
dp_state[i][x] = 1;
int dest;
long long cost;
if (i < n - 1) { // POP
if (x == pop_val[i]) {
dest = pop_goto[i];
cost = 1;
} else {
auto [j, u] = solve(push_goto[i], push_val[i]);
if (has_cycle) return {-2, 0};
auto [k, v] = solve(j, x);
if (has_cycle) return {-2, 0};
dest = k;
cost = (u + v + 1) % P;
}
} else { // HALT
if (x == 0) {
dest = -1;
cost = 1;
} else {
auto [j, u] = solve(halt_goto, halt_push);
if (has_cycle) return {-2, 0};
auto [k, v] = solve(j, x);
if (has_cycle) return {-2, 0};
dest = k;
cost = (u + v + 1) % P;
}
}
dp_state[i][x] = 2;
dp_dest[i][x] = dest;
dp_cost[i][x] = cost;
return {dest, cost};
}
};
int main() {
long long targets[2] = {150994941LL, 150994939LL};
// For the chain structure, let's count distinct values with different push_val choices
// Standard: push_val[i] = i+1, pop_goto[i] = i+1, and push_goto[i] varies
// Generalized: also vary push_val[i] and pop_goto[i]
// First, let's see how many distinct values we get for n=12 (11 POP + 1 HALT)
// with the standard structure (just varying push_goto)
// We already know: ~2^d = 2^11 = 2048
// Let's try n=12 with varying BOTH push_goto[i] AND push_val[i]
// push_val[i] can be 1..maxV
// This might give us many more distinct values
// Actually, let me think about what push_val does.
// When instruction i doesn't match (x != i+1), it pushes push_val[i] and goes to push_goto[i].
// The cost includes solve(push_goto[i], push_val[i]).second
// Different push_val values lead to different sub-computations.
// With push_val values from 1..V, we have V*n choices for (push_val, push_goto) at each instruction.
// Let's test: for d=11 (n=12), with V=5, how many distinct T values?
// That's (5*12)^11 configs for the generalized version... way too many.
// But maybe even with 2 push values, we get much more diversity.
// Let me try a different approach: use the chain structure but with generalized push_vals
// and do hill climbing on both push_goto AND push_val.
for (int n = 10; n <= 28; n++) {
cerr << "n=" << n << endl;
int d = n - 1; // number of POP instructions
mt19937 rng(42 + n * 1000003);
bool found[2] = {false, false};
int foundConfig[2][35][2]; // [target][instr][push_val, push_goto]
auto startTime = chrono::steady_clock::now();
int timeLimit = (n <= 15) ? 15000 : (n <= 20) ? 8000 : 3000;
for (int restart = 0; !(found[0] && found[1]); restart++) {
auto now = chrono::steady_clock::now();
auto ms = chrono::duration_cast<chrono::milliseconds>(now - startTime).count();
if (ms > timeLimit) break;
// Random initial config
// pop_val[i] = i+1, pop_goto[i] = i+1 (always next)
// push_val[i] random from 1..min(i+3, 20)
// push_goto[i] random from 0..n-1
// halt_push = 1, halt_goto = n-1
Evaluator ev;
ev.n = n;
ev.pop_val.resize(d);
ev.pop_goto.resize(d);
ev.push_val.resize(d);
ev.push_goto.resize(d);
for (int i = 0; i < d; i++) {
ev.pop_val[i] = i + 1;
ev.pop_goto[i] = i + 1; // standard: next instruction
int maxPV = min(i + 2, 10); // push values up to 10
ev.push_val[i] = 1 + rng() % maxPV;
ev.push_goto[i] = rng() % n;
}
ev.halt_push = 1;
ev.halt_goto = d; // self-loop at HALT... this might cause cycles
// Actually, halt_goto pointing to itself with push causes cycle
// Let halt_goto point to a POP instruction instead
ev.halt_goto = rng() % d; // point to some POP instruction
ev.init();
auto [dest, cost] = ev.solve(0, 0);
if (ev.has_cycle) continue;
// Hill climbing
for (int iter = 0; iter < 50000; iter++) {
for (int ti = 0; ti < 2; ti++) {
if (!found[ti] && cost == targets[ti]) {
found[ti] = true;
cerr << "FOUND n=" << n << " target" << (ti+1) << " cost=" << cost << endl;
// Print program
cout << "FOUND n=" << n << " target" << (ti+1) << ":" << endl;
cout << n << endl;
for (int i = 0; i < d; i++) {
cout << "POP " << ev.pop_val[i] << " GOTO " << (ev.pop_goto[i]+1)
<< " PUSH " << ev.push_val[i] << " GOTO " << (ev.push_goto[i]+1) << endl;
}
cout << "HALT PUSH " << ev.halt_push << " GOTO " << (ev.halt_goto+1) << endl;
}
}
if (found[0] && found[1]) break;
// Mutate: change one push_val or push_goto
int choice = rng() % (2 * d + 2); // 2*d for POP params + 2 for HALT params
Evaluator ev2 = ev; // shallow copy the config (not DP)
// Apply mutation
if (choice < d) {
// Change push_val[choice]
int maxPV = min(choice + 2, 10);
ev2.push_val[choice] = 1 + rng() % maxPV;
} else if (choice < 2*d) {
// Change push_goto[choice - d]
ev2.push_goto[choice - d] = rng() % n;
} else if (choice == 2*d) {
// Change halt_push
ev2.halt_push = 1 + rng() % 10;
} else {
// Change halt_goto
ev2.halt_goto = rng() % d;
}
ev2.init();
auto [dest2, cost2] = ev2.solve(0, 0);
if (ev2.has_cycle) continue;
// Accept if closer to either target
long long bestDist = P;
for (int ti = 0; ti < 2; ti++) {
if (!found[ti]) {
long long dd = min((cost - targets[ti] + P) % P, (targets[ti] - cost + P) % P);
bestDist = min(bestDist, dd);
}
}
long long newBestDist = P;
for (int ti = 0; ti < 2; ti++) {
if (!found[ti]) {
long long dd = min((cost2 - targets[ti] + P) % P, (targets[ti] - cost2 + P) % P);
newBestDist = min(newBestDist, dd);
}
}
if (newBestDist <= bestDist) {
ev.push_val = ev2.push_val;
ev.push_goto = ev2.push_goto;
ev.halt_push = ev2.halt_push;
ev.halt_goto = ev2.halt_goto;
cost = cost2;
}
}
}
cerr << " found=" << found[0] << "," << found[1] << endl;
if (found[0] && found[1]) break;
}
return 0;
}
|