Redirecting to
NADOS

K Increasing Subsequence 2

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

For the given sequence A with n elements find the number of strictly increasing subsequences with k elements.

Note: This question is same as K Increasing Subsequence, but this time array can have numbers from 1 to 10^9 and can have duplicates.
Input Format 
First line contains two integer n and k
following n lines contains elements of sequence
A[1]
A[2]
....A[n]
Output Format 
Print one number the andwer to question
Question Video
Constraints 
1. 1 <= n <= 10^5
2. 1 <= k <= 11
3. 1 <= A[i] <= 10^9
5. A can contain duplicates
6. Output may not fit in 32 bit signed integer
Sample Input 
5 2
1
1
3
8
2
Sample Output 
7


  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name