PROBLEM LINK:
Editorialist: Vivek Hamirvasia
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Dynamic Programming.
PROBLEM:
Given the first N natural numbers, we need to find the number of ways to arrange them such that only K of them are visible from left to right. A number is visible if there is no number greater than it, to the left of it.
EXPLANATION:
This can be solved with dynamic programming where
DP[i][j] = number of ways to place the first i numbers in position 1 to i such that j of them are visible.
At every position i, we can choose to place the largest number i, or any of the number from 1 to i-1. Thus DP[N][K] is the required answer.
DP[i][j] = DP[i-1][j-1] + (i-1) * DP[i-1][j]
Placing the largest number i at position i will always make it visible and the problem reduces to finding the number of ways to place the first i-1 numbers in position 1 to i-1 such that j-1 of them are visible.
While, placing any of the number from 1 to i-1 on position i, makes that element not visible, and hence the problem reduces to to finding the number of ways to place the first i-1 numbers in position 1 to i-1 such that j of them are visible.
Hence, at every step, we can either place the largest number there or place any of the (i-1) smaller numbers there. In the first case, the largest number will be visible for sure and in the second case, the chosen number will not be visible for sure since at some point, the largest number will overshadow it.
Base Condition is DP[1][1] = 1.
We can precompute the DP for 1<=i<=1000 and 1<=j<=i and then answer each test case in O(1)
Complexity : O(N2)