Paper Tiger Sequence¶
Algorithms and attribution¶
The preferred algorithm is the problem setter's shared-suffix storage; see std.cpp. Codex (GPT-6) sizes the length table from the input, allocates the exact final character range, and specifies the cyclic-copy boundaries.
Interval backtracking with a bounded cache, implemented in alternative.cpp, is a parallel option with less character storage. Shared suffixes give linear construction time; backtracking trades interval decomposition for a small cache.
Every version shares one suffix¶
An operation only adds a prefix. Thus \(S_i\) is a suffix of \(S_{i+1}\) and of the final string \(S_N\) . Write \(L_i=|S_i|\) and precompute
Allocate \(L_N\) characters and place the initial string in \([L_N-L_0,L_N)\) . Version \(i\) will always occupy \([L_N-L_i,L_N)\) , so no historical copies are needed.
Copying an added prefix¶
Suppose the current version starts at \(b\) and has length \(L\) , and the new prefix has length \(D\) . Write
Every destination is left of \(b\) , while every source is inside the current version. The ranges do not overlap, so copying cannot read newly added characters. The new start is \(b-D\) .
Correctness¶
The initial suffix is correct. Assuming the current suffix is correct, the formula writes the complete new prefix in the required cyclic order and preserves the existing suffix. The resulting suffix is therefore the next version. Induction proves every version. For query \(q\) , output exactly \(L_q\) characters starting at \(L_N-L_q\) .
Complexity and boundaries¶
Let \(Z\) count all output characters, including newlines. Initial characters plus all additions total exactly \(L_N\) . Time is \(O(N+L_N+Z+1)\) and space is \(O(N+L_N)\) . Existing characters never need to be shifted.
The length table needs \(N+1\) entries, including version \(0\) . Starting with the maximum length \(10\) and applying the recurrence \(70\) times gives maximum final length \(4055267\) . This follows from the length recurrence and avoids an oversized fixed allocation. Distinct queries produce at most \(24331433\) string characters, plus newlines.
For \(N=0\) , queries refer to the initial version. For \(M=0\) , there is no output. Reduce \(p_i\) modulo the pre-growth length, and wrap within that same version.
Verification and Use¶
Ten fixed-seed formal recipes are in tests/plan.json . Compile the program, then run:
python tests/generate.py --out-dir <output-directory> --std <compiled-program>
Omit --std to generate inputs only; --case 01 selects one case. See independent small checks, input validation, the five-round timing, memory and hash record, and the environment and calibration method.
Measured Results¶
Intel Core Ultra 9 275HX, Windows 11, GCC 16.2.0 and C++17 -O2. Both programs ran for five alternating rounds on the same ten formal inputs. Time is the largest per-input median, including startup and I/O. Peak working sets were measured separately and include runtime overhead.
| Program and algorithm | Largest median (seconds) | Peak (MiB) | 0.5-second reference limit |
|---|---|---|---|
| Shared suffixes | 0.070396 | 9.04 | Measured inputs pass |
| Interval backtracking with bounded cache | 0.069889 | 5.36 | Measured inputs pass |
The limit is twice the reference program's largest median, rounded up to a multiple of 0.5 seconds. See the measurement record for all runs and input/source/binary hashes. Recalibrate on other judges. These measurements describe the supplied implementations and measured inputs.