You are not logged in. Please login at www.codechef.com to post your questions!

×

SLIS - Editorial

4
1

PROBLEM LINK:

Practice
Contest

Author: Jingbo Shang
Tester: Xiaoxu Guo
Editorialist: Pushkar Mishra

DIFFICULTY:

Medium

PREREQUISITES:

Segment trees

PROBLEM:

There are many ways to solve the Longest Increasing Subsequence (LIS) problem. There is a DP approach, a Patience sorting approach, and a Segment tree approach. We will use the last one to formulate our algorithm.

Since, $A[i] \leq 10^9$, we will have to compress the numbers into a smaller range. Since, the length of the array is $\leq 10^5$, we can compress the numbers into the range $1..10^5$. Now, we need to find the number of second-longest LIS in this compressed array.

Let us look at how we find the LIS in the compressed array $B[1..N]$ using segment trees. We process the elements of the array from left to right. We keep a segment tree whose nodes store the maximum of all the lengths of increasing subsequences ending on an element in their respective ranges. When we are processing $B[i]$, we first find the maximum in the range $1..B[i]-1$ using the segment tree. Let's say this maximum is equal to $L$. We then update the leaf associated with the $i^{th}$ index to $L+1$. We update its parents as well to reflect the new maximum in the range $1..B[i]$. Once we have processed all the $N$ elements, the length of the longest increasing subsequence lies in the root of the segment tree.

How can we get the number of LISes? For this, we store two variables per node, $max$ and $nmax$. The variable $max$ stores the maximum of the lengths of increasing subsequences ending on an element in the range that the node covers. The variable $nmax$ stores the number of increasing subsequences which have the length $max$. Now, when we are processing $B[i]$, we update the leaf associated with it by putting $max = L+1$ and $nmax = prevnmax$, where $prevnmax$ is the number of increasing subsequences of length $L$ (which is maximal) in the range $1..B[i]-1$.

This gives us a way to calculate the number of LISes in an array. How do we find the number of second-LISes? Our previous algorithm gives us an idea. This time, we will store 2 more variables per node: $smax$ and $nsmax$. The variable $smax$ stores second-maximum of all the lengths of increasing subsequences ending on an element in their respective ranges. The variable $snmax$ stores the number of increasing subsequences which have the length $smax$.

Now, during update and query operations on the segment tree, when we our combining two nodes $x$ and $y$, we can have three cases.

  • Case 1: $x.max > y.max$
    In this case, we will check whether $y.max$ is equal to $x.smax$ or not. If it is, we add $y.nmax$ to $x.nsmax$. We then return $x$ as the result of this combining operation.

  • Case 2: $x.max < y.max$
    This case is analogous to Case 1. We will check whether $x.max$ is equal to $y.smax$ or not. If it is, we add $x.nmax$ to $y.nsmax$. We then return $y$ as the result of this combining operation.

  • Case 3: $x.max = y.max$
    In this case, we add $y.nmax$ to $x.nmax$ and $y.nsmax$ to $x.nsmax$. We then return $x$ as the result of this combining operation.

Once all the elements have been processed, our final answer lies in the $nsmax$ variable of the root.

COMPLEXITY:

$\mathcal{O}(N\log N)$ per test case.

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

This question is marked "community wiki".

asked 18 Oct '15, 13:09

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156581
accept rate: 4%

edited 09 Feb '16, 16:55

admin's gravatar image

0★admin ♦♦
19.8k350498541

In Case 3, x should be returned instead of y as mentioned in the editorial.

(19 Oct '15, 06:22) anuj954★

yes, thank you :)

(19 Oct '15, 12:12) pushkarmishra4★

Can the tester please explain his solution?

link

answered 19 Oct '15, 08:54

wittyceaser's gravatar image

2★wittyceaser
3.4k194377
accept rate: 16%

Which part of it is unclear to you ?

(19 Oct '15, 15:33) anuj954★

I used BITs only, no segment trees.

I started by compressing the input and with counting the LIS ending at each $A[i]$ ($L[i]$). Then, while we could count the number of increasing sequences of each length $k$ ending at each $A[i]$ using a BIT for each $k$ and the same approach as for $L[i]$ (with counting instead of max-ing), we only need $k\ge L[i]-1$, which gives only $O(N)$ queries on BITs.

The next problem is space: one BIT costs $O(N)$ space, which is too much. But we already know on which numbers we'll have updates/queries for each $k$ - they're given just by $L[i]$ and $A[i]$ - so we'll compress them for each $k$ (using map<>s) and then build the BITs of optimal size for each $k$. The sum of those sizes is the same as the number of updates/queries, $O(N)$.

Each time before an operation on those BITs, we use one $O(\log{N})$ operation on a map<>, so the time complexity is still $O(N\log{N})$. See my code for more details.

link

answered 22 Oct '15, 23:04

xellos0's gravatar image

7★xellos0
5.9k54393
accept rate: 10%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×2,657
×1,768
×53
×2

question asked: 18 Oct '15, 13:09

question was seen: 3,488 times

last updated: 09 Feb '16, 16:55