Hii there,in the Question “Too Much Sweetness”, during the contest I tried this approach
Algo:
- Generate all the 2^N permutations containing 1 and 2.
-check every permutations if it satisfies all conditions
if yes cnt++;
this approach has Time complexity = O(2^N)
for subtask 2, N=p+q<=20 so TO(2^N) = 10O(2^20) = 10^7(approximately)
so this solution should pass subtask 1 and 2.
But my solution is clearing only subtask1 and give TLE for the second.
my code :https://www.codechef.com/viewsolution/16713300
Plz help me to rectify this.
Approach for your solution, is it just Observation or can you derive it mathematically ?
@wittyceaser Suppose we have the following: a_1 + a_2 + a_3 + ... + a_k = n and we have to find the number of positive solutions such that 1 \leqslant a_i \leqslant s for all i in [1, k]. We can first find the unbounded solutions (i.e., a_i in the range [1, n] using (n-c)C(k-1). Then, we will choose one of the a_i and substitute it by b_i such that b_i = a_i + s. Now, all the solutions to b_1 + a_2 + ... + a_k = n-s will be invalid and we need to subtract it from the previous found unbounded solution. (1)
1 Like
@wittyceaser Now, instead of choosing a_1 we could have substituted any other a_i and all those solutions need to be excluded too. We have kC1 choices for this. But, while excluding these, we have excluded some solutions twice and we need to add it back. This process of inclusion and exclusion will keep on repeating till we replace all a_i with b_i in the final step. The final form will be: (-1)^i(nCr(k, i) * nCr(n-i*s-1, k-1)) for all i in range [1, k]. (2)
1 Like
you made an assumption that N= P+Q but N<=(P+Q) its value can be less than (P+Q) then in that case we can’t reduce 6 to 5 variables in your way N= P-p+Q-q.
P<=20 and q<=20. So N can be 40,thats y tle
@taran_1407 ur editorials are easy to understand than most others
too much sweetness u explained in just 2 lines …
