<p>The algorithm below runs in time <span class="math-container">$O(n\log n)$</span>, but not <span class="math-container">$O(n)$</span>. On the other hand, it permutes the columns in such a way that there are only <span class="math-container">$O(\log^2n \cdot\log\log n)$</span> short segments in the end. </p>

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

<p>We start by finding <span class="math-container">$x^{-1}$</span> for every <span class="math-container">$x\in(\mathbb{F}_{n + 1})^*$</span>. For each <span class="math-container">$x$</span> this takes <span class="math-container">$O(\log n)$</span> time by Euclidean algorithm, in total <span class="math-container">$O(n\log n)$</span>. </p>

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

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

<p>Then we define another array <span class="math-container">$W$</span> of size <span class="math-container">$n$</span>. Namely, <span class="math-container">$W[\gamma]$</span> is defined as follows
<span class="math-container">$$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].$$</span></p>

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

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

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

CC BY-SA 4.0
2018-12-28T11:53:28.227Z
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)$).
Alexander S. Kulikov
CC BY-SA 4.0
2018-12-28T10:15:54.660Z
2018-12-29T10:07:34.160Z
2018-12-29T10:07:34.160Z
Sasha Kozachinskiy
<p>Consider an <span class="math-container">$n \times n$</span> table with <span class="math-container">$n$</span> stars such that each row contains at most <span class="math-container">$\log n$</span> stars. The stars break each row into segments (continuous parts of a row without stars). Let's call a segment <em>short</em> if its length is at most <span class="math-container">$\log n$</span>. It is not difficult to show that under a random permutation of the columns, the number of short segments is at most <span class="math-container">$O(\log^4n)$</span>. Can you design a deterministic <span class="math-container">$O(n)$</span> time algorithm that takes the positions of <span class="math-container">$n$</span> stars as an input and outputs a permutation of the columns such that the number of short segments is at most <span class="math-container">$O(n/\log n)$</span>?</p>

<cc.complexity-theory><ds.algorithms><derandomization>
Permuting the columns of a 0/1-matrix to avoid short segments
Alexander S. Kulikov
# Permuting the columns of a 0/1-matrix to avoid short segments

(Asked by: username_0 on 2018-12-28)

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)$?

**Tags:** cc.complexity-theory, ds.algorithms, derandomization

---

## 1 answers

### Answer by username_1 on 2018-12-28. Score: 1

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).

> **Comments:**
> **username_0**: 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)$).  

---

