[Provincial Selection 2024] Reshaping Time

The question

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

Algorithmic frontier

Reference frontier: $\mathcal{O}\!\left(n \times 3^{n}\right)$
Latest reported AI result: $\mathcal{O}\!\left(n^{3} \times 2^{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(n^{3} \times 2^{n}\right)$

AI / model: Not identified

Reported method

The page converts the probability into a count, uses inclusion-exclusion over source segments and up-closed sets to avoid double-counting topological orders, computes Q_S(x) by grouping connected components by size, and finishes with layered fast subset convolution plus polynomial interpolation, claiming O(n^3 2^n) time and O(n 2^n) space.

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 reports passing three samples and 924 brute-force stress cases locally, but shows no judge record; it also never restates the table's O(n × 3^n) baseline.

Credits

Published by: Chris_Shi

Independent reproduction: Not yet performed

Prior-art review: Not yet performed