Whimsical_HITMAN's blog

[Help] LIS type of problem.
By Whimsical_HITMAN, history, 13 months ago, In English

https://www.spoj.com/problems/ONEXLIS/

i have been trying to solve the problem for a long time...but couldnt come up with a proper approach... My approach(ig wrong) : when we consider a sequence to be lis, the elements before the last element must have lds(longest strictly decreasing subsequence) > 1; however im unable to implement the idea; any help would be appreciated.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Firstly without loss of generality, we can assume that $$$0 \le a_i \le n - 1$$$, by coordinate compression.

Let's try fixing the one pair that is out of order in the subsequence. Define $$$l_x, r_x$$$ to be the longest increasing sequence ending at index $$$x$$$ and the longest increasing sequence starting from index $$$y$$$ respectively. These values can be computed for all $$$x$$$ using a segment tree in one pass. Then the answer to the problem is $$$\max_{i < j, a[i] > a[j]} l_i + r_j$$$. Iterating over $$$j$$$, this is also doable using a segment tree.

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    iterating over all j will give tle right?

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For every $$$j$$$ you do $$$O(\log n)$$$ work, so it should not.

      → Reply