File size: 3,871 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 | #include <bits/stdc++.h>
using namespace std;
// Test on small cases: for range [5, 7] (example), verify the optimal solution
// and check if our ADFA approach matches
int L_g, R_g;
struct Edge { int to, w; };
bool verify(int n, vector<vector<Edge>>& adj, int L, int R) {
vector<int> indeg(n + 1, 0), outdeg(n + 1, 0);
for (int i = 1; i <= n; i++) {
outdeg[i] = adj[i].size();
for (auto& e : adj[i]) indeg[e.to]++;
}
int start = -1, end_node = -1;
int cnt1 = 0, cnt2 = 0;
for (int i = 1; i <= n; i++) {
if (indeg[i] == 0) { cnt1++; start = i; }
if (outdeg[i] == 0) { cnt2++; end_node = i; }
}
if (cnt1 != 1 || cnt2 != 1) return false;
for (auto& e : adj[start]) if (e.w == 0) return false;
// DAG check
vector<int> deg(n + 1, 0);
for (int i = 1; i <= n; i++) deg[i] = indeg[i];
queue<int> q;
for (int i = 1; i <= n; i++) if (deg[i] == 0) q.push(i);
int topo_cnt = 0;
while (!q.empty()) { int u = q.front(); q.pop(); topo_cnt++; for (auto& e : adj[u]) if (--deg[e.to] == 0) q.push(e.to); }
if (topo_cnt != n) return false;
int cnt = 0;
vector<int> vis(R + 1, 0);
bool error = false;
function<void(int, long long)> dfs = [&](int x, long long val) {
if (error) return;
if (val > R) { error = true; return; }
if (adj[x].empty()) {
cnt++;
if (cnt > 500000 || val < L || val > R) { error = true; return; }
vis[(int)val]++;
if (vis[(int)val] > 1) { error = true; return; }
return;
}
for (auto& e : adj[x]) dfs(e.to, val * 2 + e.w);
};
dfs(start, 0);
if (error) return false;
for (int i = L; i <= R; i++) if (vis[i] == 0) return false;
return true;
}
// Build ADFA for [L,R]
int build_adfa(int L, int R) {
int bits = 0;
for (int t = R; t > 0; t >>= 1) bits++;
map<tuple<int,int,int>, int> state_id;
int next_id = 0;
vector<array<int,2>> trans;
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) return id;
int mid = 1 << (k - 1);
trans[id][0] = get_state(k - 1, lo, min(hi, mid - 1));
trans[id][1] = get_state(k - 1, max(lo, mid) - mid, hi - mid);
return id;
};
// Handle multiple bit lengths
int bitsL = 0;
for (int t = L; t > 0; t >>= 1) bitsL++;
int start_children = 0;
for (int len = bitsL; len <= bits; len++) {
int rs = 1 << (len - 1), re = (1 << len) - 1;
int cL = max(L, rs), cR = min(R, re);
if (cL > cR) continue;
if (len == 1) {
// Special: END state
} else {
get_state(len - 1, cL - rs, cR - rs);
}
start_children++;
}
return next_id + 1; // +1 for START
}
int main() {
// Test ADFA node count vs brute-force optimal for small cases
cout << "L\tR\tADFA\tBF_opt" << endl;
// For each range where all numbers have the same bit length
for (int bits = 1; bits <= 8; bits++) {
int lo = 1 << (bits - 1);
int hi = (1 << bits) - 1;
for (int L = lo; L <= hi; L++) {
for (int R = L; R <= hi; R++) {
int adfa = build_adfa(L, R);
// For small ranges, we can verify this is optimal
// by trying all possible DAGs (too expensive for large n)
// Just print for now
if (adfa <= 10 && R - L >= 2) {
cout << L << "\t" << R << "\t" << adfa << endl;
}
}
}
}
return 0;
}
|