Permuting the columns of a 0/1-matrix to avoid short segments 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).