docker_space/frontier_cs_7/small_test.cpp

#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;
}