Input: a sequence <A_1, A_2, ..., A_n> of integers and an integer X.
Output: true if there is a strictly increasing subsequence of length X in sequence A, false otherwise.
Is there an O(n) algorithm for this problem ?
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | awoo | 154 |
8 | Dominater069 | 154 |
10 | luogu_official | 150 |
Input: a sequence <A_1, A_2, ..., A_n> of integers and an integer X.
Output: true if there is a strictly increasing subsequence of length X in sequence A, false otherwise.
Is there an O(n) algorithm for this problem ?
Name |
---|
Calculate all $$$a_{i+1}-a_i\ (1\leq i\leq n-1)$$$ and find out if there are $$$x-1$$$ or more continuous positive numbers.
subsequence not subarray.
counterexample:
a = [1, 2, 1, 3, 1, 4, 1, 5], x = 5
ans = true, but your condition is false.
I only have an $$$O(n\cdot log_2(n))$$$ solution using segment tree with coordinate compression + DP. I don't think there is a $$$O(n)$$$ solution. Not sure.
Calculating LIS in O(nlog(n)) is not an option here ?
You can just get the LIS of the sequence. If it is bigger than or equal to X, then the answer is YES. Otherwise, NO.
So why did you suggested a complex O(nlog(n)) solution ?
Why complex? Most two popular ways to get LIS either by binary search, or DP + segment trees. In fact, DP+ segment tree solution is easier to get to than the binary search, which requires more casework.
What does coordinate compression means? Google search hasn't got me anywhere.
My solution for the LIS:
let $$$a[i]$$$ be the length of LIS wich the last element is $$$i$$$
then $$$a[i]$$$ = maximum of $$$a[0...i-1]+1$$$
finding the maximum can be done using a fenwik tree or a segment tree. Is this different from your solution? If so can you explain me yours
Edit: Oh it just occurred to me. we can't do this if maximum element is too large. I guess coordinate compression is to solve that issue?
Yes, if element is too large, I just renumber it to smaller one. I renumber all elements from $$$0$$$ to $$$N-1$$$ in ascending order.
I think if finding
LIS
of a sequence is lower-bounded by O(nlog(n)), we can prove that we can do no better than O(nlog(n)) in the worst case.Assume X >= LIS of the sequence. So to check if this length is possible we have to do >= O(nlog(n)) work.
So in worst case O(nlog(n)) is the best we can do.
Good thought, but this isn't a valid proof. There's plenty of problems where answering "is the answer bigger than or equal to X?" is faster than answering "what is the answer?". Since the latter can be obtained from the former using binary search, a correct lower bound, only knowing the fact that answering "what is the answer?" has a lower bound of $$$O(n \log n)$$$, is $$$O(\frac{n \log n}{\log n}) = O(n)$$$, but this ends up being useless here.
Well technically checking whether the LIS is of length at least X could be faster than calculating the LIS. For example, the problem of checking whether a palindrome of length X exists in a string can be carried out in linear time with hashes, while a binary search + hashes solution takes $$$O(n \; log \; n)$$$ time to compute the longest palindrome. However, the longest palindrome can be computed in linear time with other methods (such as Manacher's algorithm or eertree).
If $$$X \geq | LIS(A) | $$$ means there is such algorithm that find Longest Increasing Subsequence length in Linear. But currently there isnt and continue being researched by some researchers, the best I know is that some papers that prove such $$$O(n\ log(log(n)))$$$ algorithm exists but it is either/both complex or/and having big hidden constant to use in practical