Need help in MIC and PIC

1

here is the link to the my solution (Python)
https://www.codechef.com/viewsolution/30874226
I make a formula with the help of oesis and it was working correctly for n = 2 and n=4
Why it gives wrong answer?

1 Like
2

I also did the same thing and got WA.
c++ submission

3

OEIS (A174061 - OEIS) has the formula
a(n) = \sum_{k=0..n-1} (-1)^k * \binom{2n}{k} * \binom{11n-1-10k}{2n-1}
Yours seem different.

3 Likes
4

Ooo dude…how you got this?
I mean you already had done such problem?
how you come to this
I should learn how to use oesis

1 Like
5

look at @rahul_g solution
we were thinking of how to get 10, 670
but he finds the direct formula for it!!
I am totally amazed

1 Like
6

plz explain about this formula
is this possible to achieve this formula with basic combinatorics only :sweat_smile: :sweat_smile:

7

https://oeis.org/search?q=1%2C16%2C100%2C400&sort=&language=&go=Search
I was thinking of this…I tried to go with it’s summation

1 Like
8

I don’t know how to achieve it. I just copied the formula from description.

9

Yeah, i tried to make the formula using multinomial theorm and got correct results for n = 2 and 4. But it seems to give wrong answers for other numbers .

10

I mean, you can get this with “Basic” Combinatorics.
Let the number of chocolates gotten by mic an pic on their i th day be a_i and b_i respectively and are bounded between 0 and 9.
That implies \sum a_i = \sum b_i.
Therefore \sum a_i - \sum b_i =0 . Let us define a new sequence c where c_i = 9 - b_i. It can be seen that c is also bounded by 0 to 9. \sum c_i = 9n - \sum b_i. If we substitute this equation in the first equation we get
\sum a_i + \sum c_i = 9n. Since all terms are bounded between 0 and 9, let’s redefine a to include c.
If the bound was only \geq0 we can calculate the answer as \binom{9n+2n -1}{2n-1}, if you remember your basic combinotorics. Now because of the bounds, we have to use inclusion exclusion. Let’s say k numbers were greater than 10. How many ways do we have to choose those numbers? \binom{2n}{k} ways. Now to put it back into bounded by greater than 0, we write those numbers as 10 + a_i. Now the sum would be \sum a_i = 9n - 10k. The number of ways here would be f(k)=\binom{2n}{k} \binom{9n - 10k +2n - 1}{2n - 1}. Now the answer would be
\sum (-1)^k f(k).

4 Likes
11

I have not read whatever you wrote…maybe I will read it later.
I want to ask a question…do you know how to solve this-
x1+ x2 + x3 + … + xr =n where xi>=0
number of ways to achieve this equation is C(n+r-1,r-1)
but if there is condition that xi>=0 and xi<=p where p<n…then how to solve it…I did similar kind of question during jee days (about some die…I don’t remember exactly) but now I don’t remember how to do it. Can you help?

12

That’s exactly what my formula solves.
To be clear, the answer would be \sum (-1)^k\binom{r}{k} \binom{n + r - 1 -(p+1)k}{r-1}

1 Like
13

Ok…I will read it.

14

do u get how to make the formula when there are given conditions on xi ? If yes, please explain

1 Like
15

Please can you once again briefly tell about how to put constraints on xi without taking concept of this question.
I simply want to know if they give…
x1 + x2 + … + xr = n
then how many ways are there if value of xi lies in [10, 20] ?

1 Like
16

\sum (-1)^k \binom{r}{k} \binom{n- 10r - 11k + r -1}{ r-1}
Just force y_i to lie between 0 and 10 by writing x_i=10+y_i and then solve it.

1 Like