PROBLEM LINK:
Author: Ritesh Gupta
Tester: Romit Kumar
Editorialist: Romit Kumar
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
DP, Math
PROBLEM:
You are given an integer N. You are required to find the count of increasing subsequences in all permutations of 1, 2, …, N such that the highest element in the increasing subsequence lies at an even index(1-based indexing).
EXPLANATION:
This can be solved using dp approach. Consider we have two dp arrays, dp[] and dp1[], where dp1[i] stores count of all increasing subsequence for permutation of length i and dp[i] stores count of increasing subsequence whose highest element lies at even position for permutation of length i. It can be seen that our answer will be dp[N]. We will first try to construct dp1[] array.
Constructing dp1[] array
Consider we want to construct dp1[i]. It can be thought of as adding 1 extra element at the end of permutation of length i-1. We will put j(=1, 2, …, i) as the last element in permutation of length i and find the count of increasing subsequence for each j. The answer for dp1[i] will be summation of all values that we got after putting j as last element.
Now for any j, it can be seen that dp1[i] will at least be equal to dp1[i-1]. This is to account for all the increasing subsequence already formed upto length i-1. Now all that’s left is to consider those increasing subsequence whose last element is j. Of course, this will at least be equal to (i-1)! to account for subsequence of length 1 consisting of element j itself.
Now we have to take into account remaining increasing subsequences. For this we can consider permutation of length j-1(whose value is stored in dp1[j-1]). All the increasing subsequence in permutation of j-1 can have j as its last element and it will still be an increasing subsequence. We also have to consider ways of distributing these j-1 elements
over i-1 places. It will be equal to ways of choosing j-1 places from i-1 places times ways of shuffling remaining n-i places. So this will be equal to dp[j-1] \times {i-1\choose j-1} \times (n-i)! = \frac{dp[j-1] \times (i-1)!}{(j-1)!} . This term need to be calculated over all j from 1 to i-1.
Construction dp[] array
Constructing dp[] array is very similar to constructing dp1[] array. We will construct this as we did for dp1[]. To find dp[i], we need to consider all j(=1, 2, …, i-1). For any j, dp[i] will at least be equal to dp[i-1] to account for increasing subsequence with highest element is at even position already formed upto length i-1. Now we need to consider all increasing subsequence ending in j such that j is at even position. We will consider these combinations only if j lies at even position i.e. i is even since j is the last element. To construct this, we will follow the same idea as we did for dp1[].