I have a straightforward task that can be done in $O(n^2)$ time. I'm now wondering if the task can be done in time $O(n^{2-\epsilon})$ if we are allowed to do some pre-processing.

The problem exists of two steps. In the first (preprocessing) step, we are given an $n \times n$ array $A_{i,j}$: $n$ permutations of the numbers $1\ldots n$. We are given unbounded time to do some preprocessing and build a datastructure of polynomial size that we can use in step 2. In step 2 (the task), we are given an array of length $n$ named $b$, containing (possibly duplicate) indices between $0$ and $n-1$. Intuitively, the $i$'th element of $b$ determines from which array we are going to take the first element and write that number to the output, unless that number was already written to the output (even if it was from another array), in which case we try the next element of the array. More formally, the output must be an array of length $n$ named $c$, that's a permutation of the numbers $1\ldots n$. The first element of $c$ is $A_{b_0,0}$. Next, $c_i (i=1\ldots n-1)$ is determined as follows:

  1. Set $j = 0$.
  2. If $A_{b_i,j}$ does not already appear in $c$, then $c_i = A_{b_i,j}$
  3. Else, increment $j$ and goto 2.

So these 3 steps are contained in an outer loop that's executed $n-1$ times: 1 time for each $c_i$.

It's easy to see that this implementation of step 2 runs in $O(n^2)$ and does not use any datastructure that could be constructed in step 1. Can we do better in step 2 by creating a clever datastructure of polynomial size in step 1?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.