1
$\begingroup$

I can solve the following problem by Jeff Erickson in $O(n^3)$(and maybe in $O(n^2logn)$) time but how is the $O(n^{3/2} log(n))$ time solution possible?

Let $D[1 .. n]$ be an array of digits, each an integer between $0$ and $9$. A digital subsequence of $D$ is a sequence of positive integers composed in the usual way from disjoint substrings of $D$. For example, $3, 4, 5, 6, 8, 9, 32, 38, 46, 64, 83, 279$ is a digital subsequence of the first several digits of $\pi$:$$ \underline 3 , 1, \underline 4 , 1, \underline 5 , 9, 2, \underline 6 , 5, 3, 5, \underline 8 , \underline 9 , 7, 9, \underline{3, 2} , 3, 8, \underline{4, 6} , 2, \underline{6, 4} , 3, 3, \underline{8, 3 }, \underline {2, 7, 9}$$ The length of a digital subsequence is the number of integers it contains, not the number of digits; the preceding example has length $12$. As usual, a digital subsequence is increasing if each number is larger than its predecessor.

Describe and analyze an efficient algorithm to compute the longest increasing digital subsequence of $D$. [Hint: Be careful about your computational assumptions. How long does it take to compare two k-digit numbers?]

For full credit, your algorithm should run in $O(n^4)$ time; faster algorithms are worth extra credit. The fastest algorithm I know for this problem runs in $O(n^{3/2}log n)$ time; achieving this bound requires several tricks, both in the design of the algorithm and in its analysis, but nothing outside the scope of this class.

$\endgroup$
3

1 Answer 1

1
$\begingroup$

I will assume you know how to solve the problem by keeping a table $T[i, j]$ which stores the length of the best solution whose last integer is $D[i\cdots j] = D[i]D[i+1] \cdots D[j]$. To compute $T[i, j]$ you need to find the best $T[a, b]$ such that $D[a \cdots b] <_{\text{lex}} D[i \cdots j]$ and $b < i$. The computation of $T[i, j]$ (provided the previous entries of $T$ have been filled) can take $O(n)$ if the $<_{\text{lex}}$ is implemented in $O(1)$ time with a good data structure like a suffix array + LCP; after all, you're always comparing substrings of $D$. Naively, this would yield a runtime of $O(n^3)$ which is the state at which you seem to be.

Now consider the following observations.

Observation 1: The $i$-th term of the optimal sequence should never be longer than the $i-1$-th term by more than 1 digit.

Observation 2: Taking $D[1]$, $D[2\cdots3]$, $D[4 \cdots 6], \ldots D[n-\sqrt{n} \cdots n]$ is always a solution, implying that the answer is always at least $\sqrt{n}$, and by Observation 1, we get that only the cells of $T$ with $j-i+1 \leq \sqrt{n}$ should be computed (one can even limit it to $j-i+1 \leq \sqrt{j}$, but it doesn't help asymptotically...). There are now $O(n^{3/2})$ cells.

Now let's try to speed-up the computation of \begin{equation} T[i, j] = 1 + \max_{a \leq b < i} \Big\{ T[a, b] \; \vert \; D[a\cdots b] <_{\text{lex}} D[i\cdots j] \Big\}.\tag{1} \end{equation}

As you were already doing in your $O(n^3)$ approach, we should only consider $b - a = j - i$ or $b-a = j - i -1$ (this is just Observation 1). If we keep, for each substring length $\ell \in \{1, \ldots, \sqrt{n}\}$ a matrix where $B[\ell][i] := \max_{b < i} \Big\{ T[b-\ell+1, b]\Big\}$, then $B[j-i-1][i]$ is one candidate for the $\max$ in Equation (1), while the other candidate will be

$$ \max_{b < i} \Big\{ T[b-j+i+1, b] \; \vert \; D[a\cdots b] <_{\text{lex}} D[i\cdots j] \Big\}. $$

How could we compute this last amount more efficiently? We can assume we're constructing $T[i, j]$ in increasing order of $i$, and let the length be denoted $\ell = j-i+1$. We can keep in memory a set of pairs $$S^{i}_\ell = \Big\{ (T[b-\ell+1, b], D[b-\ell+1 \cdots b]) \; \vert \; b < i\Big\}.$$

If we let $w = D[i\cdots j]$, then we're looking for $$ \max v \; \text{s.t. } \; (v, y) \in S^i_{\ell} \text{ and } y <_{\text{lex}} w. $$

We're now facing a data structures problem; how can we keep a set of pairs $(\text{integer}, \text{string of length } \leq \sqrt{n})$ in a way that quickly allows us to query with a word $w$ for the maximum first coordinate whose second coordinate is smaller than $w$? It is enough to maintain $S$ as a balanced binary search tree, where the ordering of the tree is based solely on the words $y$ inserted in it, but every node keeps track of the best value $v$ present in its subtree. Notice that because comparisons between strings take $O(1)$, searching on the tree will take $O(\log n)$. Therefore our entire algorithm runs in $O(n^{3/2} \log n)$.

$\endgroup$

Your Answer

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

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