PROBLEM LINK:
Author: Puneet Kumar
Editorialist: Pawan Mishra
DIFFICULTY:
EASY
PREREQUISITES:
Modulo Exponentiation, Binary search
PROBLEM:
There are N candies. Each has a label Ai showing its sweetness level. You have to put exactly K candies in a box such that the box has balanced sweetness i.e. the sweetest candy in the box should not be sweeter than P times the least sweetest candy in the box. Tell the total number of ways in which these candies can be put into the box.
Output the answer modulo 1000000007(10^9+7).
EXPLANATION:
Suppose there is a candy already present in the box which has least sweetness, then only those k-1 candies can be put in the box which come in a certain range as described in the problem. Now this range will be easy to find if we sort the array in ascending order of sweetness level. So, first sort the given array.
One thing to note is that treat every candy different from each other even if they have the same values.
Now after that, you have to traverse the entire array and use binary search (upper bound) to find P*a[i] for each index i. From here you can get the range starting from i up to which you have to select candies with i^{th} candy being least sweetest.
One more thing to note is that upper bound will give 1 index higher than the required index so we need to decrease the index by 1. Now our job is reduced to selecting k-1 candies out of index-i available for selection.
calculate NCR(index−i, k−1) (k−1 because you have already selected the ith candy).
Now as Constraints for n is 100000, so we will have to pre-compute the factorial values and use them in finding the NCR. We will need to use Modulo exponentiation and Inverse modulo exponentiation to calculate NCR to meet the given constraints.
Adding the above-computed values for each i will give you the final answer.
Time complexity- O(n*(log(n)+ log(M)), Where M = 10^9 + 7.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.