File size: 9,426 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 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 | #include <bits/stdc++.h>
using namespace std;
// Build the ADFA for [L,R] and perform proper minimization
// Then try cross-depth merging and other optimizations
int L = 577837, R = 979141;
int main() {
// Both L and R are 20-bit numbers
int bits = 20;
assert(L >= (1 << 19) && R < (1 << 20));
// The ADFA has 21 layers (depth 0 = START, depth 20 = END)
// At each depth d, after reading d bits, we have a "state" that represents
// the set of suffixes that can follow to complete a valid number in [L,R]
// State at depth d after reading prefix p (a d-bit number, first bit is 1):
// The set of (20-d)-bit suffixes s such that p*2^(20-d) + s is in [L,R]
// i.e., L <= p*2^(20-d) + s <= R
// i.e., max(0, L - p*2^(20-d)) <= s <= min(2^(20-d)-1, R - p*2^(20-d))
// So the state is characterized by (lo, hi) where lo and hi are the bounds on the suffix
// lo = max(0, L - p*2^(20-d))
// hi = min(2^(20-d)-1, R - p*2^(20-d))
// Two prefixes at the same depth have the same state iff they have the same (lo, hi)
// Let's enumerate all distinct (lo, hi) pairs at each depth
// At depth d, valid prefixes p satisfy: 2^(d-1) <= p < 2^d (first bit is 1)
// And the range of complete numbers is [L, R]
// So: p*2^(20-d) + s in [L,R], s in [0, 2^(20-d)-1]
// We need: p*2^(20-d) <= R and (p+1)*2^(20-d) - 1 >= L
// i.e., p <= R >> (20-d) and p >= ceil(L / 2^(20-d)) ... roughly
cout << "Analyzing ADFA states for L=" << L << " R=" << R << " bits=" << bits << endl;
// For each depth, collect all distinct (lo, hi) suffix range pairs
// Also record transition structure
struct State {
int lo, hi; // suffix range [lo, hi] at remaining bits k
int k; // remaining bits
};
// Map from (k, lo, hi) to state id
map<tuple<int,int,int>, int> state_id;
int next_id = 0;
// Transitions: state_id -> (child_on_0, child_on_1) where -1 means no edge
vector<array<int,2>> trans;
// BFS/DFS from START
function<int(int, int, int)> get_state = [&](int k, int lo, int hi) -> int {
if (lo > hi) return -1;
auto key = make_tuple(k, lo, hi);
auto it = state_id.find(key);
if (it != state_id.end()) return it->second;
int id = next_id++;
state_id[key] = id;
trans.push_back({-1, -1});
if (k == 0) {
// END state, no transitions
return id;
}
int mid = 1 << (k - 1);
// On bit 0: suffix starts with 0, so s = 0*2^(k-1) + s'
// New range: lo <= s' <= min(hi, mid-1)
int lo0 = lo, hi0 = min(hi, mid - 1);
trans[id][0] = get_state(k - 1, lo0, hi0);
// On bit 1: suffix starts with 1, so s = mid + s'
// New range: max(lo, mid) - mid <= s' <= hi - mid
int lo1 = max(lo, mid) - mid, hi1 = hi - mid;
trans[id][1] = get_state(k - 1, lo1, hi1);
return id;
};
// START: depth 0, first bit must be 1
// After reading bit 1, we're at depth 1 with prefix = 1
// Remaining bits: 19
// suffix range: max(0, L - 1*2^19) <= s <= min(2^19-1, R - 1*2^19)
int base = 1 << 19; // 524288
int lo_start = max(0, L - base);
int hi_start = min((1 << 19) - 1, R - base);
cout << "Start suffix range: [" << lo_start << ", " << hi_start << "]" << endl;
int start_child = get_state(19, lo_start, hi_start);
// +1 for START, +1 for END (already counted)
// START is separate (connects to start_child via edge weight 1)
// Actually START is a special node not counted in get_state
cout << "\nTotal distinct states (excluding START): " << next_id << endl;
cout << "Total nodes (including START): " << next_id + 1 << endl;
// Print states by depth (remaining bits k)
map<int, vector<pair<int,int>>> by_k;
for (auto& [key, id] : state_id) {
auto [k, lo, hi] = key;
by_k[k].push_back({lo, hi});
}
cout << "\nStates by depth (remaining bits k -> number of states):" << endl;
int total = 1; // START
for (int k = 19; k >= 0; k--) {
auto& states = by_k[k];
sort(states.begin(), states.end());
cout << "k=" << k << " (depth " << (20-k) << "): " << states.size() << " states" << endl;
for (auto& [lo, hi] : states) {
auto it = state_id.find({k, lo, hi});
int id = it->second;
cout << " id=" << id << " [" << lo << "," << hi << "]";
if (k > 0) {
cout << " -> 0:" << trans[id][0] << " 1:" << trans[id][1];
}
cout << endl;
}
total += states.size();
}
cout << "\nTotal: " << total << endl;
// Now check: are there any states at different depths that have identical
// transition structures (same children)?
cout << "\n=== Cross-depth analysis ===" << endl;
// Compute the "signature" of each state bottom-up
// Signature = the set of numbers reachable from this state
// Two states can be merged if they have the same signature AND
// can be made consistent in the DAG
// Actually, for merging, we need states with identical sub-DAGs
// Compute hash of sub-DAG rooted at each state
map<int, long long> state_hash;
function<long long(int)> compute_hash = [&](int id) -> long long {
if (state_hash.count(id)) return state_hash[id];
if (id == -1) return -1;
long long h0 = compute_hash(trans[id][0]);
long long h1 = compute_hash(trans[id][1]);
// Simple hash
long long h = h0 * 1000000007LL + h1 * 998244353LL + 12345;
return state_hash[id] = h;
};
for (auto& [key, id] : state_id) {
compute_hash(id);
}
// Group states by hash
map<long long, vector<int>> by_hash;
for (auto& [key, id] : state_id) {
by_hash[state_hash[id]].push_back(id);
}
cout << "\nStates grouped by sub-DAG hash:" << endl;
int mergeable = 0;
for (auto& [h, ids] : by_hash) {
if (ids.size() > 1) {
cout << "Hash " << h << ": states";
for (int id : ids) {
// Find the key for this id
for (auto& [key, sid] : state_id) {
if (sid == id) {
auto [k, lo, hi] = key;
cout << " (k=" << k << ",[" << lo << "," << hi << "])";
break;
}
}
}
cout << endl;
mergeable += ids.size() - 1;
}
}
cout << "Potentially mergeable: " << mergeable << " states" << endl;
// Now let's try to actually build a minimized DAG with cross-depth merging
// using structural equivalence
// Two nodes are structurally equivalent if:
// - Both are END (k=0, lo=0, hi=0), or
// - They have the same transition structure after merging:
// trans[a][0] is equivalent to trans[b][0] AND trans[a][1] is equivalent to trans[b][1]
// This is exactly what the hash captures (assuming no collisions)
// Let's verify with exact comparison
// Build equivalence classes bottom-up
map<int, int> eq_class; // state_id -> equivalence class id
int n_classes = 0;
// First, assign classes to END state(s)
// Then go up level by level
// Process by k (remaining bits), starting from k=0
for (int k = 0; k <= 19; k++) {
// Get all states at this level
map<pair<int,int>, int> sig_to_class; // (class_of_child0, class_of_child1) -> class
for (auto& [key, id] : state_id) {
auto [kk, lo, hi] = key;
if (kk != k) continue;
if (k == 0) {
// END state - all END states are equivalent
if (!sig_to_class.count({-1, -1})) {
sig_to_class[{-1, -1}] = n_classes++;
}
eq_class[id] = sig_to_class[{-1, -1}];
} else {
int c0 = (trans[id][0] == -1) ? -1 : eq_class[trans[id][0]];
int c1 = (trans[id][1] == -1) ? -1 : eq_class[trans[id][1]];
auto sig = make_pair(c0, c1);
if (!sig_to_class.count(sig)) {
sig_to_class[sig] = n_classes++;
}
eq_class[id] = sig_to_class[sig];
}
}
}
cout << "\n=== After cross-depth minimization ===" << endl;
cout << "Number of equivalence classes: " << n_classes << endl;
cout << "Total nodes (with START): " << n_classes + 1 << endl;
// Print which states got merged
map<int, vector<int>> class_members;
for (auto& [id, cls] : eq_class) {
class_members[cls].push_back(id);
}
int merged_count = 0;
for (auto& [cls, members] : class_members) {
if (members.size() > 1) {
cout << "Class " << cls << " merges:";
for (int id : members) {
for (auto& [key, sid] : state_id) {
if (sid == id) {
auto [k, lo, hi] = key;
cout << " (k=" << k << ",[" << lo << "," << hi << "])";
break;
}
}
}
cout << endl;
merged_count += members.size() - 1;
}
}
cout << "Total nodes saved by cross-depth merging: " << merged_count << endl;
return 0;
}
|