I’ve tried my best to explain it.
We have to distribute K objects among 6 people. Suppose, all the K objects are lying in a row on the floor equally spaced. Now, if you put 5 bars, beetween any of the objects (gap b/w the objects), it will divide K objects into 6 parts and will be one possible solution of the equation above. So, all possible combinations can be given by (k-1)c(5) ( i.e. selecting 5 gaps among k-1 gaps).
6 Likes
yeah got it thanks…i was missing the point that we need an integer solution (a(i) > 0)…so i was effectively considering 6 bars…
yeah…thats what i did during contest…basically we need to find the total integer solutions to equation. a1 + a2 + … + a6 <= K…
it comes to combination(K,6)
2 Likes
explanation to the solution is provided below
C(M,6) where M=(n-1)/2
C(M,6) where M=(n-1)/2
Can you tell me where my reasoning is wrong? For K=7, there is 1 solution: 1…7. for K=8, you can choose any one of [1,7] to clone, so ans=7. *For K=9, you can again choose any one of [1,7] to clone, including one chosen before (for. eg. 1,2,2,2,3,4…), so ans = 7**7. Continuing this way, shouldn’t it be 7^(K-7)?
Could you explain your reasons for believing so?
Can anybody tell if the formula (k-1)C(5) is applicable for k<7 ,because in all these cases answer will come out to be 1.
for example: a1+a2+a3+a4+a5+a6=2 ,here k=2,by using above formula answer will be 1.but in actual it should be 21…please help,any kind of help will be appreciated
for nCr to work n must be greater than equal to r. In your case k-1=1 is less than 5 therefore answer is 0.
1 Like
Dude Awesome !!
why C(K-1,5) ?
It should be 6, right?
@amit001 i think you perhaps misunderstood the solution given in the editorial. As we are brute forcing all the values for 7 so we need to distribute the rest of the values in six containers. agree ??
@kodoos my bad. i was reading solutions in comments so thought 6 should be used but solution above brute force a7. now got it
python nails it.
Why is it not C(k+5,5)?
The link is just for a reference to such kind of equations.
Why is it not C(k+5,5)? http://cseweb.ucsd.edu/classes/wi10/cse20/CSE20%20Lecture%2015.pdf The link is just for a reference to such kind of equations.
awesome!!!
if you are facing problems in implementing the aforesaid algorithm, using C++, you can have a look at my solution:
https://www.codechef.com/viewsolution/16738557
Note: 1. I was completely blown off by this idea (still can’t figure out why) @ma5termind
2. I just figured out that ‘int’ in python has a larger range than ‘long long int’ in C++