Exact guarantees and faster algorithms for $k$-rollercoasters
Sungmin Kim, Florin Manea
原文摘要
For $k\ge3$, a $k$-rollercoaster is a sequence of distinct values whose maximal increasing and decreasing runs all have length at least $k$. We discover the maximum guaranteed length $f_k(n)$ of $k$-rollercoasters appearing as subsequences of $n$-point permutations. In particular, letting $q=k-1$, we prove that $f_k(n)= \lceil n/q\rceil$ for $n\ge2q^2$, $f_k(n)= 2q-\lfloor \sqrt{2q^2-n}\rfloor$ for $q^2<n<2q^2$ and $f_k(n)= 0$ otherwise. We prove that the guarantees are tight by constructing an $n$-point permutation whose longest $k$-rollercoaster has exactly $f_k(n)$ points. Our proof extends Seidenberg's argument [Journal of the London Mathematical Society, 1959] for proving the Erdős--Szekeres theorem by representing points in a subsequence with respect to the lengths of longest monotonic (increasing and decreasing) subsequences that reach each point. The combinatorial proof yields a deterministic comparison-based algorithm that finds a rollercoaster of length at least $f_k(n)$ in $O(n\log f_k(n))$ time and $O(n)$ space for $n>q^2$. Independently, we give an $O(nk\log k)$-time, $O(nk)$-space algorithm for a longest $k$-rollercoaster, improving the previous $O(nk^2)$ bound. We use the dynamic program of Gawrychowski et al. [STACS 2019, Algorithmica 2022], and process its weighted predecessor queries through monotone subsequences with finger-search trees. Both algorithms return such subsequences.
cs.DM · cs.DS