PROBLEM LINK:
Author: Diwakar Bhardwaj
Tester: Aditya Kumar
Editorialist: Shubham Kabra
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Dynamic Programming, Permutation & Combination, Inverse Modulo
PROBLEM:
For given numbers N, I and K, we have to find the number of sorted subsets where I comes at position K that can be formed by set{1,2,…N}.
EXPLANATION:
Let’s fix the position of I_{th} number at K_{th} position as given in the problem.
Now, we have to find total number of possible subsets that can be formed with given conditions.
Firstly, choose the numbers for the first K-1 positions as they are blank right now. We have to fill these positions with first I-1 numbers as we have to keep the subset in sorted form.
So, total number of ways for choosing the number from I-1 numbers for K-1 positions is ^{(I-1)}C_{(K-1)}.
Now, for the remaining numbers from I+1 to N, it is not necessary that they appear in the subset or not. So, for every number greater than I, either the number appears in subset or not. So, permutation for either choosing each number or not is 2 and for total N-I numbers it will be 2^{(N-I)}.
Hence, total number of required subsets are ^{(I-1)}C_{(K-1)} * 2^{(N-I)}.
We have to give output as (^{(I-1)}C_{(K-1)} * 2^{(N-I)})\%(10^9+7).
Now, we just have to calculate ^{I-1}C_{K-1} for each query (keeping the number of queries 10^6 into consideration); the best solution is to pre compute each and every case of ^{I-1}C_{K-1}.
For, pre computation we can use the formula for computing ^nc_r:
.
OPTIMAL COMPLEXITY:
\mathcal{O}(N*K + Q)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.