## A Combinatorial Programming Problem

Discuss everything related to IOI here. For more general or advanced topics use CS forum.

Moderators: bristy1588, Labib

Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm

### A Combinatorial Programming Problem

A mini bus has length $5$ and a bus has length $10$. There are $k$ and $l$ colors respectively available to color a minibus and a bus. If the length of a mini-bus and bus line is $n$(obviously divisible by $5$), then find the number of different coloring possible.
Even after you find the combinatorial summation, there are coding difficulties(though that depends on how smart your idea is). Note that, $1\leq n,k,l\leq10^{15}$.
One one thing is neutral in the universe, that is $0$.

*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

### Re: A Combinatorial Programming Problem

FInd the answer mod something, right? :/
And are $n,k$ really $\leq 10^{15}$? that'd mean using big int library for nearly every single calculation.

Use $L^AT_EX$, It makes our work a lot easier!

Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm

### Re: A Combinatorial Programming Problem

Hmm. But I posted it mainly for combinatorial part so forgot to say that you are asked to print the last six digits of the value
One one thing is neutral in the universe, that is $0$.

*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

### Re: A Combinatorial Programming Problem

Well it should be something very similar to calculating $f_n$ in $lg(n)$ time - breaking the line in the middle (and two cases about that).

Use $L^AT_EX$, It makes our work a lot easier!

Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm

### Re: A Combinatorial Programming Problem

I found two solutions for this problem. One is direct combinatorial and the other uses recursion. For both, we just need to consider $m=\dfrac n5$ instead of $n$. Just divide all lengths by $5$. Thus, the length of a minibus is $1$ and a bus has $2$. And, we have to find $f(m)$.

Using recursion: Let's say we have all the values $f(0),f(1),...,f(m-1)$. Now we find the value of $f(m)$. Then, we have two choices, we can use a minibus(length $1$) or bus(length $2$). If we use a minibus, then we have to find the number of ways with length $m-1$ i.e. this gives us $f(m-1)$ and since there are $k$ colors to paint a minibus, this options yields $kf(m-1)$. Now, similarly, if we use a bus, there are $l$ colors to paint a bus and it takes length $2$ leaving to find $f(m-2)$. So this option yields $lf(m-2)$. Thus, $f(m)=kf(m-1)+lf(m-2)$.

Direct combinatorial solution: Let's say we will take $x$ minibus(es) and $y$ bus(es). Then obviously $x+2y=m$. All solutions to this are of the type $(m-2t,t)$. So for a fixed $i$, we have to take $m-2i$ minibus(es) and $i$ bus(es). Now the minibus(es) can be colored in $k^{m-2i}$ ways(why?). And the buses can be colored in $l^i$ colored(same reasoning). Thus for a fixed permutation of the buses they can be colored in $k^{m-2i}l^i$ ways. Again, since they can be permuted themselves in
$\dfrac{(m-2i+i)!}{(m-2i)!i!}=\binom{m-i}i$
ways, for a fixed $i$, we have a total of $\binom{m-i}ik^{m-2i}l^i$ coloring. Since $i$ can run through $0,1,...,q$ where $q=\left\lfloor\dfrac m2\right\rfloor$(why?) the total number of coloring we have is $\sum_{i=0}^{q}\binom{m-i}ik^{m-2i}l^i$
One one thing is neutral in the universe, that is $0$.

Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm

### Re: A Combinatorial Programming Problem

For coding, the solution with recursion works better. Because $n,k,l$ are of huge limits, we have to use Matrix Exponentiation on the recursion we have found. To know what this is, you can search google with keywords "I, Me and Myself Matrix Exponentiation".
And once again, I got to understand how powerful "counting the same object in different ways" is!
One one thing is neutral in the universe, that is $0$.

*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

### Re: A Combinatorial Programming Problem

Masum wrote:For coding, the solution with recursion works better. Because $n,k,l$ are of huge limits
As I thought the combinatorial solution is nice though (but not a recommended approach during a contest )
Use $L^AT_EX$, It makes our work a lot easier!