[Provincial Selection 2025] Seal

The question

Can the source-listed reference complexity O(T n^2) be substantially improved?

Algorithmic frontier

Reference frontier: $\mathcal{O}\!\left(T n^{2}\right)$
Latest reported AI result: $\mathcal{O}\!\left(T n \log n\right)$

Normalized growth proxy · not benchmark data

This compares source-reported bounds; it is not a correctness or novelty finding.

Results

2026-09-12

Claimed result: $\mathcal{O}\!\left(T n \log n\right)$

AI / model: ChatGPT

Reported method

The page fixes the last maximum, shows the legal retained sets are ancestor-closed sets of a monotone-stack forest, counts them with an upper-triangular 2x2 matrix, and uses a globally weight-balanced expression tree to make each update O(log n), claiming O(n log n) time and O(n) space per test case.

Verification

Source: Source reviewed
Theory: Theory not checked
Implementation: Code available
Prior art: Prior art not reviewed

The result page was opened and compared with the collection claim. Legacy audit state: audited_public.

The source frames its baseline as an O(n log^2 n) dynamic tree DP while the table's baseline cell is O(T n^2); these do not conflict, but the page does not corroborate the table's cell. The offered source-download link is a dead ChatGPT sandbox URI, though the program itself is inline.

Credits

Published by: Chris_Shi

Independent reproduction: Not yet performed

Prior-art review: Not yet performed