[Provincial Selection 2026] Seeker

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 \sqrt{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 \sqrt{n} \log n\right)$

AI / model: ChatGPT

Reported method

The page blocks a fixed long-path decomposition, expresses a whole block's effect on the incoming probability distribution as a low-degree rational function, and answers in-block queries from O(B) precomputed moments instead of scanning the long distribution per vertex, giving O(nB + (n^2/B + n) log^2 n) and, with B = Theta(sqrt(n) log n), O(n^{3/2} log n). Derivation only — no code.

Verification

Source: Source reviewed
Theory: Theory not checked
Implementation: Theory only · code pending
Prior art: Prior art not reviewed

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

The share page was read in full. It contains no code block of any kind and explicitly states that the full fast version was never submitted to Luogu and is not claimed to have passed judging, so the record is theory-only with code pending.