SOL01 - Editorial




Author: Ankit Jha
Tester: Bhushan Khanale
Editorialist: Bhushan Khanale




DP, Permutations and Combination basics


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.


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.


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.


Could contain more or less short descriptions of possible other approaches.


Author’s solution can be found here.
Tester’s solution can be found here.

when this contest was held .

i got no information about it and also this contest is not in previous contests list.