this one only xD
Well, you can read more about partition function at Partitions Into Distinct Parts as well as combinatorics - Integer partition of n into k parts recurrence - Mathematics Stack Exchange .
Also, there might be other pages which you may find on google.
1 Like
I am also on the same boat as you. Exact same verdict with same approach. Hope someone finds out the problem in this approach.
I tried testing it with 50 test cases but it returns everything correct. Saw one thing tho, for input-
1
2 50
50 1
I got output of-
0
1
from your code. Can this be it?
Not enough karma to reply to the comment in question so this is a separate comment.
@kal013 you’re missing a couple of edgecases - one with a continue and one where there are no -1’s but the sum of the array elements is less than s. Fix those 2 and it passes - see CodeChef: Practical coding for everyone.
Found the bug @kal013
you handled the corner cases incorrectly. I have corrected and submitted. Here you go. CodeChef: Practical coding for everyone
PS: Nice running time xD
OK so I too found out the bug in my solution. In my solution, if the initial sum was unequal to required sum and there were no -1 present, it would print sum of gcd instead of 0.
I fixed two bugs. One which your solution pointed. Another one which I found.
But, the problem is, how do we know how many times a partition will appear. Fortunately, we can rush to Combinatorics 
for answers. We can see, It is just the number of Distinct permutations of the given sequence. ??
You are only following that part of the editorial which will give 30pts. Follow editorial from above statement to fetch rest 70pts.
1 Like
I’m sorry I sent you the wrong solution. This is the latest solution I submitted with the idea you suggested- CodeChef: Practical coding for everyone
It is still giving 30 points. WHat do I do?
Nevermind, I found my mistake. I was not using modular inverse while dividing by factorials.
2 Likes
At least explain your dp tables else no1s gonna understand it XD. Edit: Much better now 
1 Like
looks like only I did it with same approach as editorial XD
everyone is coming up with DP
If we consider non-decreasing permutations, we can obtain them by a recursive function f(pos, sum_left, min) where pos is index of array, sum_left is the sum we want to achieve using remaining elements, and since we want our sequence to be increasing, our current element is never less than min, the element at position pos-1.
If we remove the min constraint, all we get will be any permutation having sum S, not only non-decreasing ones.
See count function in my solution. I first check if we have reach end of the array.
It not, I try to fill the remaining elements.
We assign a value to a position, say pos, try all possible values for all remaining positions (pos+1, n-1) and consider all cases.
Then, backtrack to pos-1 and again assign a different value at position pos and try all possible values for all remaining positions (pos+1, n-1) and consider all cases.
In case we know, from values assigned in range (0, pos) that no possible solution exist, we terminate immediately.
Read more about backtracking, especially the n-queen problem. Backtracking - Wikipedia and Introduction to Backtracking - Data Structure and Algorithm Tutorials - GeeksforGeeks