# Tag Info

## Hot answers tagged subsequences

15

The problem is surprisingly non-trivial. First, two brute force algorithms. A square ("repeated pattern") is given by its length $\ell$ and position $p$, and takes time $O(\ell)$ to verify. If we go over all $\ell$ and $p$, we obtain an $O(n^3)$ algorithm. We can improve on that by first looping over $\ell$, and then scanning the string with two running ...

9

Let's start with the following observation: Let $max$ denote the maximum of the sequence $a_1,...,a_n$, and let $min$ denote its minimum. If $a_1=max$, then choosing $b_1=b_2=...=b_n=\lfloor(max+min)/2\rfloor$ is optimal. Why is this the case? Well, since the sequence starts with the maximum, either we choose $b_1$ large, and suffer a large deviation ...

7

Here is a hint. Suppose the sequence contains $n-1$ Xs and $n+1$ Ys, so that you need to change some Y to X. You can compute for each position $k \in [1,\ldots,2n]$ the number of Xs minus the number of Ys; let's call that a "report". Changing a Y to an X affects the report in a certain, easy to describe, way. On the other hand, whether a sequence is good ...

7

Here is an algorithm to count distinct subsequences of length $3$ in time $O(n \log n)$, regardless of how many times any value $a$ occurs in $A[j]$. First, create a binary search tree $T$ containing all possible values $a = A[j]$, storing at each node how many times it occurs in $A$, and how many nodes there are which follow it in the tree (are further to ...

6

There's an algorithm named after Manacher's algorithm, which is really fast, a linear time algorithm. See Wikipedia's reference Postscript: If you're really familiar with Z Algorithm, you will find that they're alike. Edit I've just misunderstood the OP's meaning (but I don't want to delete the proceding information. It's somewhat useful). He means the ...

6

The answer to the OP's question is, no if $N\le 7$ and yes otherwise. For given any positive integer $r$ and $s$, the celebrated Erdős–Szekeres theorem shows that for any sequence of distinct real numbers with length at least $(r − 1)(s − 1) + 1$ contains an increasing subsequence of length $r$ or a decreasing subsequence of length $s$. It turns out that ...

5

The fastest algorithm I can think of is applying LCS in a creative way. It can solve this problem in O(N^2) time and O(N^2) space where N is the size of string. LCS (S, reverse (S)) will give you the largest palindromic subsequence, as the largest palindromic subsequence will be the largest common subsequence between the string S and its reverse. For ...

5

It's easier to change notation. Suppose the array is $A$, with the $i$-th element denoted $A[i]$ for $i=1,2,\dots,n$, and that element $i$ has attributes $A[i].x$ and $A[i].y$. Associate a directed graph $G$ with the array as follows. The vertices of $G$ are the indices $1\dots n$ of the array. Vertex $i$ is connected to vertex $j\$ if both conditions $... 5 I suggest you pick a random permutation on the range$[a,b]$, i.e., a bijective function$\pi:[a,b]\to [a,b]$. Then, maintain a counter$i$that starts at$i=a$; at each step, output$\pi(i)$and then increment$i$(wrapping around so that$b+1$becomes$a$). There are standard methods for generating such a random permutation in the cryptography literature: ... 4 Yes, this can be solved much more efficiently. You can solve this problem in$O(b 2^b)$time using a FFT, if each number is a$b$-bit number. In the comments, you said$b=16$, so this should be an efficient solution: something like$2^{21}$steps of computation. Consider the sequence$b_{-1},b_0,b_1,\dots,b_n$defined by$b_{-1}=0$and$b_i = a_0 \oplus ...

4

Let the original sequence be $a_1,\ldots,a_n$. After removing a contiguous subsequence $a_{i+1},\ldots,a_{j-1}$, we are left with $a_1,\ldots,a_i,a_j,\ldots,a_n$ (possibly $i = 0$ or $j = n+1$). In particular, if $a_1 \leq a_2 \leq \cdots \leq a_I > a_{I+1}$ then $i \leq I$, and if $a_{J-1} > a_J \leq a_{J+1} \leq \cdots \leq a_n$ then $j \geq J$. In ...

4

In the following answer, I show how to solve in $O(n\log n)$ the following similar question: Given an array $A$ and a number $k$, find the longest contiguous subsequence in which any two elements $x,y$ satisfy $|x-y| \leq k$. Using this, it is easy to solve in $O(n \log n)$ the following question, closer to yours: Given an array $A$ and a number $k$, ...

4

No, it is not possible to do better unless the Strong Exponential Time Hypothesis (SETH) fails. If we could solve this problem substantially faster than $O(n^2)$ we would immediately obtain a much faster algorithm for solving the NP-complete problem Satisfiability. This is true even for $m$ slightly more than $\log(n)$ and the case in which we want to decide ...

4

It's impossible (assuming you only use comparisons). First, we augment all elements with indices: $a[i] \to (a[i], i)$. We'll need this when we'll remove the sequence from the array in linear time. Consider the following sorting algorithm: def sort(a): subseq = get_sorted_subseq(a) # Your function. Assume takes O(n) time b = a.exclude(subseq) ...

3

Yes, they mean the same thing. A n-gram is a sequence of n consecutive things (words, letters, whatever). A k-mer is a sequence of k consecutive things (DNA basepairs). The phrase k-mer is more common in computational genomics. See https://en.wikipedia.org/wiki/N-gram and https://en.wikipedia.org/wiki/K-mer for definitions.

3

Let $S = \{a_1,\ldots,a_n\}$, and denote $S^t$ the set after deciding the fate of $a_t$. If you want to use induction, here is your induction hypothesis: If there is a subset of $S$ that sums to $k$, then there is a subset of $S^t$ that sums to $k$. Every subset of $S$ that sums to $k$ includes $S^t \cap \{a_1,\ldots,a_t\}$.

3

You recently clarified that you want to solve the following problem: Given an input sequence $L[0..N-1]$, check whether an arithmetic progression of length $\ge N/4$ appears as a subsequence of $L$. This is a significantly easier problem, and I can suggest a very efficient algorithm for you. Let me build up to it by first explaining a few key ideas ...

3

For each $i$, let $s(i)$ be a string of length $f(i)+1$ that is not a subsequence of $S[1\ldots i]$, then what you seek for is exactly $s(n)$. Also denote $g(i) = \min\left(\ell\left(i,\sigma_1\right),\ldots,\ell\left(i,\sigma_{|\Sigma|}\right)\right)$. $g(i)$'s can be computed in $O(n)$ time in advance. We have $$s(i)=s(g(i)-1)S[g(i)].$$ Firstly $s(g(i)-... 3 I'm assuming the input does not have duplicates, e.g. not [1, 2, 2, 5]. No, an efficient (polynomial time) algorithm does not exist to our best knowledge, as per "Covering a set with arithmetic progressions is NP-complete" by Lenwood S.Health. But we can make a recursive algorithm regardless, it will just be exponential time as our input grows. Note that ... 3 Here is a simple randomized$O(n)$time algorithm. We start by rephrasing your problem slightly. Suppose that the original array is$a_1,\ldots,a_n$. Form a new array$b_0,\ldots,b_n$containing the running sums of the previous array: $$b_0 = 0, \qquad b_i = a_1 + \cdots + a_i.$$ Notice that$a_i + \cdots + a_j = b_j - b_{i-1}$. Therefore we can rephrase ... 3 Hint, scan the array from left to right, keeping track of the smallest number so far and using that number to compute the largest interval whose right endpoint is the number just scanned. Here is the Python code for the simple linear algorithm hinted. Hit the "run" button to see a couple of test result. 3 Here is an algorithm that computes the minimum cost that is about as simple as possible and as fast as possible. Count the total number of each character in$m$and$n$. Let them be$c(a), c(b), \cdots$respectively. Let$x$be one of$a,b,\cdots$such that$c(x)$is the maximum. Let$\sigma$be the sum of all$c(i)$where$i$goes through$a, b, \cdots$... 3 Here is a heuristic that won't always work, but should work with high probability if the integers in the arrays are chosen randomly from a large enough space. Initialize a hashtable of counts$C$to all zeros. Then, repeat$t$times: randomly pick$i,j$, compute$b_j-a_i$, and increment$C[b_j-a_i]$. Finally, sort$C$by counts, from largest count to ... 2 Problem of finding LPS of a string can be converted into finding Longest Common Subsequence of two strings. In this, one string will be original one and the second will be reverse of the original string. The Longest Common Subsequence problem is like the pattern matching problem, except that you are allowed to skip characters in the text. Also, the goal is ... 2 Here is the professor's solution, which he calls "reduction": For each$i$from$0$to$l$, try to construct a solution if we know that the deviation is less than or equal to$i$. The first$i$for which a solution can be found is the minimum deviation. We can find a solution given the deviation in$O(n)$time. So the running time is$O(nl)$. Then, instead ... 2 I'm going to think out loud here just working through the hints you've given. Let's go to the original hint of saying that$O(nl)$is what you should try first. I can think of a greedy algorithm that has that time. The$l$part of the time complexity means you can keep a list of the count of each occurence of each value$0..l$. That, is just create a set$\...

2

You can adapt the algorithm described in Wikipedia so that it runs in time $O(N\log (N-M))$ if you're only interested in increasing sequences of length at most $N-M$. Judging by the existence of an $N\log N$ lower bound for the general case, $O(N\log(N-M))$ might be optimal. (Your problem is equivalent to the decision problem of whether there exists a non-...

2

No, $\Omega(n\log n)$ comparisons are required. Let $k = \Theta(n)$ be an integer parameter and consider the following family of inputs. $$k+1,\:k+2,\:k,\:k+2,\:k-1,\:k+2,\:\ldots,\:2,\:k+2,\:1,\:k+2,\:x_1,\:x_2,\:\ldots,\:x_k$$ Note that, for $a\in\{1,\:2,\:\ldots,\:k+1\}$, the maximum bounded subsequence beginning with $a$ consists of $a$, then $a$ ...

2

Let's call the length of the array $t \cdot n$, so in your task $t=3$. Since in every fragment $[1, n], [n+1, 2n] \ldots [(t-1)n+1, tn]$ we can't take more than $k$ elements, so the number of taken elements won't be larger than $t\cdot k$. Let's call the indices of taken elements in the given array $x_1, x_2 \ldots x_{tn}$. It's easy to notice that $x_i + n \... 2 It's possible to count the number of such strings in something like$O(2^{n})$time. This is faster than generating all permutations (as$n! \sim 2^{n \log n + O(n)}\$), but it's still not polynomial time. I don't know if the number of such strings can be counted in polynomial time. Here's how to do it. You can build a NFA that accepts all such strings of ...

Only top voted, non community-wiki answers of a minimum length are eligible