Hugging Face's logo

JustinTX
/
shinka-backup

Model card Files
xet
 Community
shinka-backup
File size: 4,837 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
#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;
}