A Combinatorial Programming Problem
Moderators:Labib, bristy1588
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}$.
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$.
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.
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
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
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$.
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).
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
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\]
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$.
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!
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$.
Re: A Combinatorial Programming Problem
As I thought the combinatorial solution is nice though (but not a recommended approach during a contest )Masum wrote:For coding, the solution with recursion works better. Because $n,k,l$ are of huge limits
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi