PROBLEM LINK:
Author: Ankit Jha
Tester: Bhushan Khanale
Editorialist: Bhushan Khanale
DIFFICULTY:
EASY
PREREQUISITES:
DP, Permutations and Combination basics
PROBLEM:
The questions asks you to find the maximum value of N such that the total number of ways of selecting soup bowls would be less than a given number max.
QUICK EXPLANATION:
You simple need to form the combination used to find the number of ways for each N. You can see that the N will not exceed value 25 for any max up-to 10^9. Hence you can easily iterate over N until you get its maximum value as per the condition given.
EXPLANATION:
First of all, we have to construct a table with the combination values. Here, we have to simply consider values up-to 25 so that we can get the values of each combination in O(1). Even it is possible to calculate the value of each combination individually every time because the N is not so large. The combination table can be generated as per following snippet:
void getCombinations() {
ll i, j;
C[0][0] = 1;
for(i = 1; i < N; i++) {
C[i][0] = 1;
for(j = 1; j <= i; j++) {
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
}
On constructing we can get the combination in O(1) time. Further looking at the problem, we know that we have to select at least 2 soup bowls with different variety. Also, we don’t necessarily need to select N bowls. Hence we can select the bowls which are at least 2 and up-to N. It is required that 2 bowls must be of different variety. Hence, we can select those 2 from N by ^nC_2. Now, say we decided to select 3 bowls from N out of which we know that 2 must be of different variety and the one can be any of the N varieties. This can be done in ^NC_2 + ^NC_2 * ^NC_1. Hence, we can simply reduce this formula for selecting M such soups like ^NC_2 + ^NC_2 * ^NC_1 + ^NC_2 * ^NC_2 + ... + ^NC_2 * ^NC_M. We can get each of the combination values for the table created. While iterating over to values of M from 1 if we find that the number of ways at certain M is greater than the max we can stop iterating and print the value of M - 1 there.
ALTERNATIVE SOLUTION:
Could contain more or less short descriptions of possible other approaches.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.