docker_space/frontier_cs_7/bdd_approach.cpp

#include <bits/stdc++.h>
using namespace std;

// BDD approach: build a reduced ordered BDD for the predicate L <= x <= R
// where x is a 20-bit number.
// Each BDD node corresponds to a bit position and has two children (0 and 1).
// Terminal nodes: TRUE (accept) and FALSE (reject).
// We only need paths that reach TRUE, so FALSE branches are simply absent.

// Key difference from current approach: BDD sharing can happen across bit levels
// if two sub-functions are identical.

// Actually, this is EXACTLY what the current solution does with the recursive
// range decomposition and memoization. The map<tuple<int,int,int>,int> rc
// is essentially BDD node caching.

// But BDD has a crucial additional optimization: if two sub-functions at
// DIFFERENT bit positions are identical, they can share a node.
// In standard ROBDD, nodes are ordered by variable, so a variable-k node
// can only point to variable-(k-1) nodes. No cross-level sharing.

// In our problem, the DAG doesn't need to be a BDD. It just needs to be
// a DAG where paths spell out binary representations of numbers in [L,R].

// Can we build a "relaxed" BDD where a node at level k can point to
// a node at level k-2 (skipping a level)?
// If so, the skipped bit is ALWAYS a specific value (constrained path).
// But then some paths have 19 edges and others have 20. Wrong!

// Unless we ADD dummy "pass-through" nodes to equalize path lengths.
// But that would ADD nodes, not save them.

// OK here's another idea. What if some paths have FEWER edges but
// the first bit is still 1 and the number is valid?
// For example, a number like 577837 is 20 bits. But what about the
// number 999141? Also 20 bits.
// ALL numbers in [577837, 979141] are 20 bits. So all paths must be 20 edges.

// I think we're stuck at 55. Let me try one more thing: a SAT-based search
// for tiny cases to see if cross-depth sharing ever helps.

int L, R;

struct Edge { int to, w; };
vector<vector<Edge>> adj;
int n_nodes;
vector<int> indeg, outdeg;

bool verify(int L, int R) {
    int start = -1, end_node = -1;
    for (int i = 1; i <= n_nodes; i++) {
        if (indeg[i] == 0) start = i;
        if (outdeg[i] == 0) end_node = i;
    }
    if (start < 0 || end_node < 0) return false;

    // Check no leading zeros
    for (auto& e : adj[start]) if (e.w == 0) return false;

    int cnt = 0;
    vector<int> vis(R + 1, 0);
    bool error = false;

    function<void(int, int)> dfs = [&](int x, int val) {
        if (error) return;
        if (outdeg[x] == 0) {
            cnt++;
            if (cnt > 1000000 || val < L || val > R) { error = true; return; }
            vis[val]++;
            if (vis[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;
}

// For small ranges, try to find if the ADFA can be beaten
void solve_optimal(int L, int R) {
    // Build ADFA
    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;
    };

    int bits = 0;
    int tmp = R;
    while (tmp > 0) { bits++; tmp >>= 1; }

    int base = 1 << (bits - 1);
    get_state(bits - 1, max(0, L - base), min(base - 1, R - base));

    int adfa_nodes = next_id + 1; // +1 for START

    // Now try to build with fewer nodes using brute force
    // (only feasible for tiny ranges)
    // Skip this for large ranges

    cout << "L=" << L << " R=" << R << " bits=" << bits << " ADFA=" << adfa_nodes << endl;
}

int main() {
    // Test on small cases to see if ADFA is always optimal
    cout << "Testing small cases..." << endl;
    for (int l = 1; l <= 30; l++) {
        for (int r = l; r <= 30; r++) {
            int bits = 0;
            int tmp = r;
            while (tmp > 0) { bits++; tmp >>= 1; }

            int bitsL = 0;
            tmp = l;
            while (tmp > 0) { bitsL++; tmp >>= 1; }

            // Only test same-bit-length ranges
            if (bitsL == bits) {
                solve_optimal(l, r);
            }
        }
    }

    // Now for the actual problem
    cout << "\nActual problem:" << endl;
    solve_optimal(577837, 979141);

    return 0;
}