# Tag Info

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

11

A note on methodology I thought a bit about this problem, and came to a solution. When I read Saeed Amiri's answer, I realized that what I came up with was a specialized version of the standard longest subsequence finding algorithm for a sequence of length 3. I'm posting the way I came up with the solution, because I think it is an interesting example of ...

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

8

There is an $O(n)$ time algorithm, which uses $O(n)$ space. First, traverse the array left to right maintaining a stack and an auxiliary array which tells you for each element, the index of an element greater than it and to the right of it. Initially the stack is empty and the aux array contains all $-1$s. Each time you consider a new element in the array,...

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

5

A dynamic programming solution would work here, if the vitamin contents come from a finite set (for instance, bounded integers). First, sort the fruits on price ascending and in the cases were two or more fruit have the same price, sort them on vitamin content (descending). Now, define $M[f, v]$ to be the maximal number of fruits in a sublist, containing ...

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 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 ... 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$, ...

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

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

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

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

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

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

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

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