docker_space/frontier_cs_7/minimize.cpp

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