| Gen 0 | Score: 66.67 | Best: 66.67 | Status: baseline | Change: All-pairs for n<=1500, chain building for large n |
| Gen 1 | Score: 73.33 | Best: 73.33 | Status: improved | Change: IS-based approach with bit identification for large n |
| Gen 1 | Score: 73.33 | Best: 73.33 | Status: improved | Change: Individual IS + sum/sq identification + deg1 matching. Cases 1,2 perfect (1.0), Case 3 ratio 0.2 (150K rounds) |
| Gen 2 | Score: 73.33 | Best: 73.33 | Status: same | Change: Attempted batch IS building (buildIS function with add-prefix approach). TLE/WA due to high round+ops. Reverted to toggle1. |
| Gen 2 Analysis: The fundamental bottleneck is IS building requiring O(n) rounds with toggle1. Batch IS building reduces rounds to O(sqrt(n)) but increases ops, making total penalty worse. The toggle1 approach benefits from extremely low ops (14M << 15M) with max round penalty (f=8). Lambda=0.2 appears to be near-optimal for this problem structure. The sum+sq technique correctly handles 2-IS-neighbor nodes. Phase 4 handles remaining edges via second-level IS. Key insight: any approach that builds IS of n/3 requires O(sqrt(n)) batch iterations or O(n) individual toggles, giving lambda >= 0.2. |
| Gen 3 | Score: 66.67 | Best: 73.33 | Status: reverted | Change: Attempted batch IS with full probe (200K ops/round). TLE at 20s due to testlib readInt overhead. |
| Gen 4 | Score: 66.67 | Best: 73.33 | Status: reverted | Change: Attempted batch IS with moderate probe (30K ops/round). WA (wrong answer) + 18s. |
| Gen 5 | Score: 66.67 | Best: 73.33 | Status: reverted | Change: Attempted hybrid no-probe + probe batch IS. WA (IS not maximal) + 13-16s. |
| Gen 6 | Score: 73.33 | Best: 73.33 | Status: reverted to baseline | Change: Reverted to individual toggle IS approach. |
| Key findings: |
| - Batch IS construction is ~15-20x slower than individual toggles due to testlib interactor I/O overhead (~10ms per round for 200K ops) |
| - Individual toggle IS: 150K rounds (fast, ~2s total), lambda=0.2 (f(t)=8 maxed) |
| - Batch IS: 300-700 rounds (15-20s, TLE), lambda=0.3-0.4 if it could run in time |
| - The only way to improve score is to reduce rounds below 4608 (for f(t)<8), which requires batch IS |
| - Batch IS requires the interactor to be faster, which we can't control |
| - Score 73.33 appears to be the maximum achievable given the I/O constraints |
|
|
