This work extends the argument to positive but unbounded values, obtaining the same linear lower bound without zeros or ties, and establishes the asymptotic optimality of the standard $O(n)$-time, $O(1)$-space solution in several increasingly restrictive variants.
Abstract
Stone Game III admits a standard backward dynamic program using $O(n)$ time and $O(1)$ auxiliary space. The upper bound is immediate, but its optimality raises a deceptively simple question: must a correct algorithm really inspect a linear number of input values? For the original problem, an all-zero instance gives a short indistinguishability proof that every position must be inspected. This argument appears to depend strongly on the possibility of a tie. We show that it does not. Even under the promise that every input has a winner, an adversary can force any deterministic algorithm to make $\Omega(n)$ inspections by combining modular move control with indistinguishable input completions. We also extend the argument to positive but unbounded values, obtaining the same linear lower bound without zeros or ties. Together these results establish the asymptotic optimality of the standard $O(n)$-time, $O(1)$-space solution in several increasingly restrictive variants.
LeetCode Problem 856, Score of Parentheses, admits a one-pass algorithm using $O(n)$ time and $O(1)$ auxiliary registers. Its correctness follows from a local interpretation: every occurrence of () contributes a power of two determined by its nesting depth. The space bound is immediately optimal in the usual programmin...
Step recursion is a form of bounded recursion in which each recursive call moves from an input y to a prescribed predecessor $\rho_g(y)$. Its depth $D_g(y)$ is the exact number of such moves needed to reach zero. A natural question is whether knowing this depth for every input determines the expressive power of the res...
We study proportional cake cutting under an equal-length constraint, where each of $n$ agents must receive a bundle of length exactly $1/n$ that is worth at least $1/n$ to that agent. Our main result determines the exact worst-case number of cuts needed to guarantee such an allocation, namely $2n-2$ for every $n$. This...
Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui· International Symposium on M...· 0 citations
We prove that a random 3-SAT formula with $n$ variables and $\lfloor 4.268n\rfloor$ clauses is unsatisfiable with high probability. The satisfiability threshold has attracted considerable attention: successive upper bounds reached 4.4898 in the work of D\'iaz, Kirousis, Mitsche, and P\'erez-Gim\'enez, while the cavity...
Worst-case analysis, the setting of the $P \stackrel{?}{=} NP$ question, measures the cost of a problem as a function of input size alone. Yet problems that are exponential in general often become polynomial, even linear, once a checkable property of the input is known: Partition, for instance, is decidable in linear t...
Does randomization improve the worst-case first-order complexity of nonconvex optimization when the objective is very smooth? We prove that, for every fixed finite integer $p\ge3$, finding an $\eps$-stationary point requires $\Omega_p(\eps^{-5/3})$ exact value-and-gradient queries, even for $C^\infty$ objectives with i...
Hai-Han Zhang, Wen-Dao Wu, Fang-Qing Zhang et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
