Beautiful Array

Posted: 18 Jun, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

You are given two integers ‘M’ and ‘N’. Your task is to find the number of a unique beautiful array of length ‘M’.

The array of length ‘M’ is said to be beautiful if -

The array consists of elements from 1 to ‘N’.

The array contains at least one ‘N’ length strictly increasing subsequence.

Note:

A subsequence of an array is an ordered subset of the array's elements having the same sequential ordering as the original array. For example, the subsequences of the array  [1, 2, 3] are [1], [2], [3], [1, 2], [1, 3], [2, 3] and [1, 2, 3] where  [2, 1], [3,2, 1] are not subsequence of array [1, 2, 3]

The longest increasing subsequence of an array of numbers is the longest possible subsequence that can be created from its elements such that all elements are in strictly increasing order.

For example:

For M = 3 and N = 2
array : [ 1, 1, 2 ] [ 1, 2, 1 ] [ 1, 2, 2 ] [ 2, 1, 2 ] are beautiful.

array:  [ 1, 1, 1 ] [ 2, 1, 1 ] [ 2, 2, 1 ] [ 2, 2, 2 ] are not beautiful. 
Input Format:
The first line of input contains an integer ‘Q’, denoting the number of queries. Then each query follows.

The first line and the only of each query contains a pair of integers ‘M’ and ‘N’ , where ‘M’ is the length of the array and ‘N’ is the range of elements.
Output Format:
For each query, print a single line containing ‘X’, denoting the number of beautiful arrays of length ‘M’.

As this number can be quite large, print your answer modulo 10 ^ 9 + 7.

The output of each test case will be printed on a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= Q <= 500
1 <= N <= M <= 5 * 10 ^ 3

Time Limit: 1 sec.
Approach 1

Since we have to use elements from [1, N] and make the longest increasing subsequence, we must use all elements of [1, N] and for ‘N’ position out of ‘M’, place them in increasing order.

Like for ‘N’ = 3, ‘M’ = 5, some possible placements of ‘N’ elements are

Array[ ]   :   _ 1  _  2  3

position :  1  2  3  4  5

Array[ ]   :   _ 1  2  _  3

position :  1  2  3  4  5

 

So, we have ( M C N) ways to select the ‘N’ position such that the selected position makes an increasing subsequence of length ‘N’. For example (N = 3 and M = 5 ) we have 10 ways (5 C 3) to select 3 positions out of 5, such that the selected position makes an increasing subsequence of length 3. Let the selected position be {p1, p2, p3 ...pn}.

After doing so our task is to fill the gaps.

Now to avoid repetition of the array, we don’t place 1 before p1, don’t place 2 before p2 and after p1, don’t place 3 before p3 and after p2, and so on.

We can say in the set {p1, p2, p3 ...pn} p1, p2, p3….pn are the first positions of 1, 2, 3..N respectively.

If we carefully observe, there are (‘N’ - 1) ways to fill not filled positions before ‘pn’ (the first position of N) and ‘N’ ways to fill each not filled position after ‘pn’.

 

Let x = ‘pn’  -  N, be the not filled position to the left of ‘pn’ and y = M - ‘pn’,  be the not filled position to the right of ‘pn’.

So, loop for each ‘pn’ position from N to M, and find the number of ways for each position of ‘pn’ and add to our answer.

Total number of ways for each pn  = ( (pn - 1) C (N -1) )( pow (x, N-1) ) * ( pow(y, N) )), where n C r denotes the total combination of ‘r’ elements among ‘n’.

 

We have done (('pn' - 1) C (N - 1)) not (pn C N) because we have to fix ‘N’-th element at ‘pn’ and arrange only ‘N’ - 1 element in ‘pn’ -1 positions such that it maintains the constraints of the question( increasing subsequence).

 

Note:

  • Take care of modulo operation where mod = 10^9 +7.
  • Since this question has a different number of queries, So pre-calculate factorial, and multiplicative modular inverse.

 

Algorithm :

 

  • Take ‘factorial’ and ‘inverse’ array that stores the factorial and modular multiplicative inverse.
  • Do precalculation by calling the function ‘preCalculate( factorial, inverse)’.
  • Take the vector ‘res’, which stores the answer of each query.
  • Do the following for each query from 0 to ‘N’.
    • Let ‘n’ = arr[i][0] and ‘m’ = arr[i][1],  be pairs of numbers given.
    • Let ‘ans’ be the variable to store the answer ( number of the beautiful arrays)
    • Let ‘n1powx’ be variable initialized to 1.
    • Let ‘npowx’ be the variable initialized to power( ‘n’, ‘m’ -’n’)
    • Let ‘inverseN’ be the modular multiplicative inverse  of ‘n’ under mod.
    • Take a counter ‘i’ and run a loop from ‘n’ to ‘m’
      • Calculate iCm by calling the function nCk(i-1, n-1) and store it in variable nck.
      • Update ‘ans’ i.e ans = ( ( (nck * npowx) % mod ) * n1powx ) % mod
      • Update ‘n1powx’ as n1powx = ( n1powx * (n -1)) % mod
      • Update ‘npowx’ as npowx = (npowx * inverseN) % mod
    • Push (ans%mod) in  ‘res’ vector
  • return ‘res’

 

Description of preCalculate ( factorial, inverse ) function:

 

  • Initialize, factorial[0] = 1
  • Initialize, inverse[0] = inverse[1] = 1
  • Run a loop from 1 to 5 * 10 ^ 3.
    • Store factorial[i] = (factorial [i - 1] * i) % 'mod'
    • Store inverse[i] = multiverse( factorial [i], mod.

 

Description of modInverse (num, mod) function:

 

    This function returns the modular multiplicative inverse of num under modulo ‘mod’ 

  • Let ‘x’ and ‘y’ be the variable that satisfies the extended euclidean equation on ‘num’ and ‘mod’
  • Just find the value of ‘x’ and ‘y’ using an extended Euclidean algorithm.
  • If ’x’ if negative then add ‘mod’ to it as ‘x’ = ‘x’ + ‘mod’
  • Return ‘x’
     

Description of nCk( ‘n’, ‘k’) function:

 

  • Return (((factorial [ n ] * inverse [k] ) % mod ) * inverse[n-k] ) % mod)
Try Problem