Hugging Face's logo

JustinTX
/
shinka-backup

Model card Files
xet
 Community
shinka-backup / docker_space /frontier_cs_8 /fast_search2.cpp
JustinTX's picture
JustinTX
Add files using upload-large-folder tool
1fd0050 verified
Raw History Blame Contribute Delete
7.91 kB
#include <bits/stdc++.h>
using namespace std;
static const long long P = 998244353;
// Fast evaluator for the generalized chain structure
// n instructions: POP[0]..POP[d-1], HALT[d] where d=n-1
// POP[i]: POP (i+1) GOTO (i+1) PUSH push_val[i] GOTO push_goto[i]
// HALT: HALT PUSH halt_push GOTO halt_goto
//
// Constraint for no cycles: push_goto[i] <= i (goes to same or earlier instruction)
// This ensures the recursion terminates because:
// - solve(i, v) for v != i+1 calls solve(push_goto[i], push_val[i]) where push_goto[i] <= i
// This resolves to some instruction j <= i with some value x
// Then calls solve(j, v)
// Since j <= i and the chain makes progress, this terminates
//
// Actually, we need to be more careful. Let me use the standard chain constraint
// and just vary push_val.
// With the standard chain (push_goto[i] goes to some j <= i, pop_goto=i+1):
// The recursion for solve(i, x) where x != i+1:
// First: solve(push_goto[i], push_val[i])
// This pushes push_val[i] at instruction push_goto[i]
// If push_val[i] == push_goto[i]+1, it matches immediately -> (push_goto[i]+1, 1)
// If push_val[i] != push_goto[i]+1, it recurses deeper
// Then: solve(result, x) processes x at the resulting instruction
//
// The key insight: if push_val[i] != i+1 (not the standard value),
// the behavior changes because the pushed value may or may not match at the target instruction.
// Let me compute the cost using iterative DP
// States: (instruction, value) where value in {0, 1, ..., maxVal}
// We process in topological order
struct State {
int instr;
int val;
};
int main() {
long long targets[2] = {150994941LL, 150994939LL};
for (int n = 8; n <= 27; n++) {
int d = n - 1;
// Allow push values 1..d (same as pop values)
// push_goto[i] in 0..i (goes to same or earlier)
// halt_push in 1..d, halt_goto in 0..d-1
cerr << "n=" << n << " d=" << d << endl;
mt19937 rng(42 + n * 7777);
bool found[2] = {false, false};
auto startTime = chrono::steady_clock::now();
int timeLimit = (n <= 15) ? 15000 : (n <= 20) ? 10000 : 5000;
long long total_attempts = 0;
while (!(found[0] && found[1])) {
auto now = chrono::steady_clock::now();
auto ms = chrono::duration_cast<chrono::milliseconds>(now - startTime).count();
if (ms > timeLimit) break;
// Random config
int push_val[30], push_goto[30];
int halt_push, halt_goto;
for (int i = 0; i < d; i++) {
push_val[i] = 1 + rng() % d; // 1..d
push_goto[i] = rng() % (i + 1); // 0..i
}
halt_push = 1 + rng() % d;
halt_goto = rng() % d;
// Evaluate using recursive DP with cycle detection
// States: (instr 0..d, val 0..d)
// val 0 = empty stack
int maxVal = d;
int nstates = (d + 1) * (maxVal + 1);
vector<int> dest(nstates, -2);
vector<long long> cost(nstates, 0);
vector<int8_t> st(nstates, 0); // 0=unvisited, 1=in-progress, 2=done
bool cycle = false;
function<pair<int,long long>(int,int)> solve = [&](int i, int x) -> pair<int,long long> {
int id = i * (maxVal + 1) + x;
if (st[id] == 2) return {dest[id], cost[id]};
if (st[id] == 1) { cycle = true; return {-2, 0}; }
st[id] = 1;
int dd; long long cc;
if (i < d) { // POP
int pv = i + 1; // pop_val
if (x == pv) {
dd = i + 1; cc = 1; // pop, goto next
} else {
auto [j, u] = solve(push_goto[i], push_val[i]);
if (cycle) return {-2, 0};
if (j < 0 || j > d) { cycle = true; return {-2, 0}; }
auto [k, v] = solve(j, x);
if (cycle) return {-2, 0};
dd = k; cc = (u + v + 1) % P;
}
} else { // HALT (i == d)
if (x == 0) {
dd = -1; cc = 1;
} else {
auto [j, u] = solve(halt_goto, halt_push);
if (cycle) return {-2, 0};
if (j < 0 || j > d) { cycle = true; return {-2, 0}; }
auto [k, v] = solve(j, x);
if (cycle) return {-2, 0};
dd = k; cc = (u + v + 1) % P;
}
}
st[id] = 2; dest[id] = dd; cost[id] = cc;
return {dd, cc};
};
auto [_, T] = solve(0, 0);
total_attempts++;
if (cycle) continue;
// Hill climbing
for (int iter = 0; iter < 30000; iter++) {
for (int ti = 0; ti < 2; ti++) {
if (!found[ti] && T == targets[ti]) {
found[ti] = true;
cerr << "FOUND n=" << n << " target" << (ti+1) << " T=" << T << endl;
cout << "TARGET" << (ti+1) << " n=" << n << endl;
cout << n << endl;
for (int i = 0; i < d; i++) {
cout << "POP " << (i+1) << " GOTO " << (i+2)
<< " PUSH " << push_val[i] << " GOTO " << (push_goto[i]+1) << endl;
}
cout << "HALT PUSH " << halt_push << " GOTO " << (halt_goto+1) << endl;
}
}
if (found[0] && found[1]) break;
// Mutate
int save_pv, save_pg, save_idx, save_hp, save_hg;
int mut = rng() % 3;
if (mut == 0 && d > 0) {
save_idx = rng() % d;
save_pv = push_val[save_idx];
push_val[save_idx] = 1 + rng() % d;
} else if (mut == 1 && d > 0) {
save_idx = rng() % d;
save_pg = push_goto[save_idx];
push_goto[save_idx] = rng() % (save_idx + 1);
} else {
save_hp = halt_push; save_hg = halt_goto;
halt_push = 1 + rng() % d;
halt_goto = rng() % d;
mut = 2;
}
// Re-evaluate
fill(st.begin(), st.end(), (int8_t)0);
cycle = false;
auto [_d, nT] = solve(0, 0);
total_attempts++;
bool accept = false;
if (!cycle) {
long long bestOld = P, bestNew = P;
for (int ti = 0; ti < 2; ti++) {
if (!found[ti]) {
bestOld = min(bestOld, min((T - targets[ti] + P) % P, (targets[ti] - T + P) % P));
bestNew = min(bestNew, min((nT - targets[ti] + P) % P, (targets[ti] - nT + P) % P));
}
}
accept = (bestNew <= bestOld);
}
if (accept) {
T = nT;
} else {
if (mut == 0) push_val[save_idx] = save_pv;
else if (mut == 1) push_goto[save_idx] = save_pg;
else { halt_push = save_hp; halt_goto = save_hg; }
}
}
}
auto ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - startTime).count();
cerr << " attempts=" << total_attempts << " time=" << ms << "ms found=" << found[0] << "," << found[1] << endl;
if (found[0] && found[1]) break;
}
return 0;
}