File size: 2,669 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 | #!/usr/bin/env python3
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
d = 27
target1 = 150994941
target2 = 150994939
# Search ALL two-change combinations (not just first find)
print("All two-change solutions for d=27:")
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"TARGET1: gy[{j1}]={g1}, gy[{j2}]={g2}")
if T == target2:
print(f"TARGET2: gy[{j1}]={g1}, gy[{j2}]={g2}")
# Now try with SMALLER d values!
print("\nSearching smaller d values with multi-change:")
for d in range(20, 27):
print(f"\n=== d={d} (n={d+1}) ===")
# For smaller d, we need more changes.
# Let's try exhaustive search with up to 4 changes using hill climbing
import random
random.seed(42 + d)
best_gy = None
for trial in range(100000):
gy = [0] * d
# Random: set 1-6 positions to non-zero
num_changes = random.randint(1, min(6, d))
positions = random.sample(range(1, d), min(num_changes, d-1))
for j in positions:
gy[j] = random.randint(0, j)
T = computeT(d, gy)
if T == target1:
print(f"FOUND TARGET1 d={d}: gy = {gy}")
best_gy = gy[:]
break
if T == target2:
print(f"FOUND TARGET2 d={d}: gy = {gy}")
best_gy = gy[:]
break
if best_gy is None:
# Hill climbing
for restart in range(200):
gy = [0] * d
for j in range(1, d):
gy[j] = random.randint(0, j)
T = computeT(d, gy)
for iteration in range(50000):
j = random.randint(1, d-1)
old_g = gy[j]
gy[j] = random.randint(0, j)
nT = computeT(d, gy)
if nT == target1 or nT == target2:
print(f"FOUND d={d}: T={nT}, gy = {gy}")
best_gy = gy[:]
break
nd = min((nT - target1) % P, (target1 - nT) % P, (nT - target2) % P, (target2 - nT) % P)
od = min((T - target1) % P, (target1 - T) % P, (T - target2) % P, (target2 - T) % P)
if nd <= od:
T = nT
else:
gy[j] = old_g
if best_gy: break
|