PROBLEM LINK
Contest link
Setter: Kunal Jain, Gaurang Tandon
Tester: Announcement
DIFFICULTY
Hard
PREREQUISITES
Observation, combinatorics
PROBLEM
Given a set of N numbers, the code needs to find the total number of subsets who’s sum is less than or equal to M. Find the bug in the given code
BUGGY CODE
EXPLANATION
The bug
The answer needs to printed module 1879048192. To do so correctly, we need to take a mod whenever we’re adding 2 numbers. This has been done in the code everywhere but on line 34. On line 34, we’re printing ret + 1 as it is. So if the value of ret is equal to the modulo, then adding 1 to it and printing would print the answer to be modulo, instead of 0.
Therefore, the code fails when the answer to the problem is equal to the modulo.
The modulo
Notice that this isn’t one of the usual modulo’s we get. Notice that it is not even a prime number! On factorizing the modulo, we notice
1879048192 = 2^{29} * 7 = 2*{29} * (8 - 1)
1879048192 = 2^{32} - 2^{29}
Breaking down the problem
The problem asks us to count the number of subsets who’s sum is less than or equal to M. To get our answer equal to the modulo, we need a testcase such that the total number of subsets in it are 2^{32} and from them, 2^{29} have their sum greater than M
Creating the testcase
Since we need 2^{32} total subsets, our testcase will have N=32. Now, to make 2^{29} of these sum upto more than M, we can have 3 elements who’s sum is greater than M. Then, taking any of the remaining 29 of them with these 3 would also result in an invalid subset. However, we also need to make sure that any subset that doesn’t contain all the 3 of these elements is a valid subset. We can do that in the following manner:
N = 32
M = 400
A = [1, 1, ... (29 times), 100, 101, 200]
Proof of correctness
Let Count be the total number of valid subsets
First of all, taking any subset of the first 29 elements gets us a valid subset.
Count = 2^{29}
Now, taking any subset of the first 29 elements with 100 gets us a subset who’s sum is \leq129. Therefore, all these subsets are valid.
Count = 2 * 2^{29}
Similarly, taking any subset of the first 29 elements with 101 and 200 also gives us a valid subset
Count = 4 * 2^{29}
Now, taking any subset of the first 29 elements with both, 200 and 101 gives us a subset who’s sum is \leq 330. Therefore, all these subsets are valid.
Count = 5 * 2^{29}
similarly, taking any subset of the first 29 elements with (100, 200) and (100, 101) also gives us a vaid subset
Count = 7 * 2^{29}
The remaining 2^{29} subsets are those which contain all 3 of the last 3 elements. Since 100 + 101 + 200 = 401 > M, all these subsets would be invalid.
Hence, our answer would be equal to the modulo and the output would be incorrect!