A Combinatorial Programming Problem

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

Moderators:Labib, bristy1588

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh
A Combinatorial Programming Problem

Unread post by Masum » Thu Dec 19, 2013 6:57 pm

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$.

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

Re: A Combinatorial Programming Problem

Unread post by *Mahi* » Sun Dec 22, 2013 1:16 am

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.
Please read Forum Guide and Rules before you post.

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

Nur Muhammad Shafiullah | Mahi

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: A Combinatorial Programming Problem

Unread post by Masum » Mon Dec 23, 2013 3:39 am

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$.

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

Re: A Combinatorial Programming Problem

Unread post by *Mahi* » Mon Dec 23, 2013 1:24 pm

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).
Please read Forum Guide and Rules before you post.

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

Nur Muhammad Shafiullah | Mahi

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: A Combinatorial Programming Problem

Unread post by Masum » Mon Dec 23, 2013 8:39 pm

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$.

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: A Combinatorial Programming Problem

Unread post by Masum » Tue Jan 07, 2014 12:12 pm

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$.

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

Re: A Combinatorial Programming Problem

Unread post by *Mahi* » Tue Jan 07, 2014 11:47 pm

Masum wrote:For coding, the solution with recursion works better. Because $n,k,l$ are of huge limits
As I thought :P the combinatorial solution is nice though (but not a recommended approach during a contest :P )
Please read Forum Guide and Rules before you post.

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

Nur Muhammad Shafiullah | Mahi

Post Reply