Consider an $n \times n$ table with $n$ stars such that each row contains at most $\log n$ stars. The stars break each row into segments (continuous parts of a row without stars). Let's call a segment short if its length is at most $\log n$. It is not difficult to show that under a random permutation of the columns, the number of short segments is at most $O(\log^4n)$. Can you design a deterministic $O(n)$ time algorithm that takes the positions of $n$ stars as an input and outputs a permutation of the columns such that the number of short segments is at most $O(n/\log n)$?


The algorithm below runs in time $O(n\log n)$, but not $O(n)$. On the other hand, it permutes the columns in such a way that there are only $O(\log^2n \cdot\log\log n)$ short segments in the end.

Let us at first describe $O(n\log n)$-time algorithm for the case when $n + 1$ is prime. Then we may identify columns $\{1, 2, \ldots, n\}$ with elements of $(\mathbb{F}_{n + 1})^*$. The idea is to consider permutations of the form $x\mapsto \gamma x$ for $\gamma\in(\mathbb{F}_{n + 1})^*$. We will show that at least one $\gamma$ is good for us and how to find such $\gamma$ in $O(n\log n)$ time.

We start by finding $x^{-1}$ for every $x\in(\mathbb{F}_{n + 1})^*$. For each $x$ this takes $O(\log n)$ time by Euclidean algorithm, in total $O(n\log n)$.

Then assume that positions of stars are $$(a_1, b_1), \ldots, (a_n, b_n).$$ Let $L$ be the list of all $(i, j)$ such that $i\neq j$ and $a_i = a_j$ (pairs of stars which are from the same row). The size of $L$ is $O(t_1^2 + \ldots + t_n^2)$, where $t_i$ is the number of stars from the $i^{th}$ row. Since $t_i\le\log n$, we have $$|L| = O(t_1^2 + \ldots + t_n^2) = O((t_1 + \ldots + t_n)\cdot \log n) = O(n\log n).$$

We then create an array $M$ of size $n$, where $M[\rho]$ is equal to the number of $(i, j)\in L$ s.t. $\rho = b_i - b_j \pmod{n + 1}$. Clearly, computing $M$ takes $O(|L|) =O(n\log n)$ time.

Then we define another array $W$ of size $n$. Namely, $W[\gamma]$ is defined as follows $$W[\gamma] = \sum\limits_{\substack{k = -\log n \\ k\neq 0}}^{\log n} \sum\limits_{\substack{\rho:\, \gamma\rho = k\\\pmod{n + 1}}} M[\rho].$$

Now let us prove that $W[\gamma]$ is an upper bound on the number of short segments after permuting columns according to $x\mapsto \gamma x$. Indeed, the number of short segments is at most the number of $(i, j)\in L$ such that for some $u, v\in\{1, 2, \ldots, n\}, u\neq v, |u - v| \le \log n$ it holds that $\gamma b_i = u\pmod{n + 1}, \gamma b_j = v\pmod{n + 1}$. In turn, this is at most the number of $(i, j) \in L$ s.t. for some $k\in [-\log n, \log n], k\neq 0$ it holds that $\gamma(b_i - b_j) = k \pmod{n + 1}$. This is exactly $\sum\limits_{\substack{k = -\log n \\ k\neq 0}}^{\log n} \sum\limits_{\substack{\rho:\, \gamma\rho = k\\\pmod{n + 1}}} M[\rho]$.

Now it only remains to note that $$W[\gamma] = \sum\limits_{\substack{k = -\log n \\ k\neq 0}}^{\log n} M[\gamma^{-1} k]$$ Here we use the fact that $n + 1$ is prime. Since we have all $\gamma^{-1}$ precomputed, it takes only $O(n\log n)$ time to compute $W$. On the other hand for fixed $k$ all $\gamma^{-1} k$ are different, i.e. $\sum\limits_{\gamma} W[\gamma] \le 2\log n \sum\limits_{\rho} M[\rho] = 2\log n \cdot |L| = O(n\log^2 n)$. Hence there exists $\gamma$ such that $W[\gamma] = O(n\log^2 n/n) = O(\log^2 n)$. We find any such $\gamma$ and permute columns according to $x\mapsto \gamma x$.

The problem in general case is that now not all $\gamma$'s from $\mathbb{Z}_{n + 1}\setminus \{0\}$ are reversible. However, there are $\Omega(n/\log\log n)$ of them, so we start our algorithm by finding all reversible $\gamma\in\mathbb{Z}_{n + 1}\setminus \{0\}$ in $O(n\log n)$ time (once again, Euclidean algorithm helps). We then do exactly the same thing but only for reversible $\gamma$'s. In the end we will have a slightly worse upper bound on the smallest $W[\gamma]$, namely $O(\log^2(n)\log\log n)$ (because we take into account only $\Omega(n/\log\log n)$ of $\gamma$'s).

| cite | improve this answer | |
  • $\begingroup$ Sasha, the bit-size of the input is $n\log n$, yes, but we assume implicitly a RAM model (roughly, basic arithmetic operations with $O(\log n)$-length numbers cost $O(1)$). $\endgroup$ – Alexander S. Kulikov Dec 28 '18 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.