File size: 5,109 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 | #!/usr/bin/env python3
"""
Analyze the chain step count formula mathematically.
computeT(d, gy):
Sv[0] = 0
for j in 0..d-1:
c[j] = (Sv[j] - Sv[gy[j]] + (j - gy[j]) + 1) mod P
Sv[j+1] = (Sv[j] + c[j]) mod P
T = (Sv[d] + d + 1) mod P
Where gy[j] in {0, ..., j} for each j.
For the standard chain (all gy[j]=0):
c[j] = Sv[j] + j + 1
Sv[j+1] = 2*Sv[j] + j + 1
Let's compute Sv[j] for gy[j]=0:
Sv[0] = 0
Sv[1] = 0 + 1 = 1
Sv[2] = 2 + 2 = 4
Sv[3] = 8 + 3 = 11
Sv[j] = 2^(j+1) - j - 2
T = 2^(d+1) - d - 2 + d + 1 = 2^(d+1) - 1
Now let's think about what happens when we change ONE gy value.
Say gy[k] = g instead of 0. Then:
For j < k: everything is the same.
At j = k: c[k] = Sv[k] - Sv[g] + (k - g) + 1 instead of Sv[k] + k + 1
Difference: delta_c[k] = -(Sv[g] + g)
Wait, let me be more precise.
With gy[k]=g: c[k] = Sv[k] - Sv[g] + k - g + 1
With gy[k]=0: c[k] = Sv[k] - Sv[0] + k - 0 + 1 = Sv[k] + k + 1
Difference: c[k]_new - c[k]_old = -Sv[g] - g
For the standard chain (all gy[j]=0 for j != k):
Sv[g] = 2^(g+1) - g - 2
So delta = -(2^(g+1) - g - 2) - g = -2^(g+1) + 2
But this only works if all OTHER gy values are 0. In general it's more complex.
Let me think about the formula differently.
Define T(d, gy[]) mod P.
For d=27, we need T = 150994941 or 150994939.
Standard T(27, all zeros) = 2^28 - 1 = 268435455.
Can we reduce T by choosing some gy[j] != 0?
From the analysis above, setting gy[k]=g reduces T by roughly 2^(g+1) - 2 at level k,
but this also propagates to levels k+1, k+2, etc. (since Sv changes).
Actually the formula is more subtle. Let me think recursively.
T(d) = Sv[d] + d + 1
Sv[d] = sum of c[j] for j=0..d-1
c[j] = Sv[j] - Sv[gy[j]] + j - gy[j] + 1
This is a recurrence where each c[j] depends on all previous Sv values.
Key insight: c[j] represents the cost of "resolving the push at level j".
When gy[j] = g, the pushed char starts at level g and traverses to level j.
The cost of this traversal is: sum of c[i] for i = g..j-1, plus j-g contributions of 1.
Actually: c[j] = Sv[j] - Sv[g] + j - g + 1 = (sum of c[i] for i=g..j-1) + (j-g) + 1
Wait, Sv[j] - Sv[g] = sum of c[i] for i=g..j-1.
So c[j] = (sum c[i], i=g..j-1) + (j-g) + 1 = (sum c[i], i=g..j-1) + (j-g+1)
The (j-g+1) is the number of instructions traversed (including the push itself).
And sum c[i] for i=g..j-1 is the cost of all the sub-pushes encountered while traversing.
So the total T is like a tree of sub-pushes.
"""
P = 998244353
def computeT(d, gy):
Sv = [0] * (d + 1)
for j in range(d):
c = (Sv[j] - Sv[gy[j]] + (j - gy[j]) + 1) % P
Sv[j + 1] = (Sv[j] + c) % P
return (Sv[d] + d + 1) % P
# For d=27, find what T values are achievable
d = 27
target1 = 150994941
target2 = 150994939
# Standard chain
T_all_zero = computeT(d, [0]*d)
print(f"d={d}, T(all zeros) = {T_all_zero}")
print(f"Target 1: {target1}, diff = {T_all_zero - target1}")
print(f"Target 2: {target2}, diff = {T_all_zero - target2}")
# The diff is what we need to subtract.
diff1 = (T_all_zero - target1) % P
diff2 = (T_all_zero - target2) % P
print(f"Need to reduce by {diff1} for target1")
print(f"Need to reduce by {diff2} for target2")
# Let's compute what happens when we set gy[j] = g for one j.
# With all other gy = 0.
print("\nEffect of single gy[j]=g changes:")
for j in range(d):
for g in range(1, j+1): # g=0 is baseline
gy = [0]*d
gy[j] = g
T = computeT(d, gy)
reduction = (T_all_zero - T) % P
if reduction == diff1:
print(f" *** MATCH TARGET1: gy[{j}]={g}, T={T}, reduction={reduction}")
if reduction == diff2:
print(f" *** MATCH TARGET2: gy[{j}]={g}, T={T}, reduction={reduction}")
print("\nSearching two-change combinations...")
# Two changes: gy[j1]=g1, gy[j2]=g2
# This is O(d^4) ≈ 27^4 ≈ 500K, feasible
import itertools
# First, compute reduction for each single change
single_reductions = {}
for j in range(d):
for g in range(1, j+1):
gy = [0]*d
gy[j] = g
T = computeT(d, gy)
single_reductions[(j, g)] = T
# The problem: changes are NOT independent. Setting gy[j1] and gy[j2] together
# gives a different result than the sum of individual reductions.
# So we can't just combine single changes.
# But we can try all pairs.
found = False
for j1 in range(d):
for g1 in range(1, j1+1):
for j2 in range(j1+1, d):
for g2 in range(1, j2+1):
gy = [0]*d
gy[j1] = g1
gy[j2] = g2
T = computeT(d, gy)
if T == target1:
print(f"FOUND TARGET1: gy[{j1}]={g1}, gy[{j2}]={g2}, T={T}")
found = True
break
if T == target2:
print(f"FOUND TARGET2: gy[{j1}]={g1}, gy[{j2}]={g2}, T={T}")
found = True
break
if found: break
if found: break
if found: break
if not found:
print("No two-change solution found. This confirms the current solution likely uses more changes.")
|