[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 122: include(/home/shoeb/public_html/www.matholympiad.org.bd/forum/includes/phpbb-latex.php) [function.include]: failed to open stream: No such file or directory
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 122: include() [function.include]: Failed opening '/home/shoeb/public_html/www.matholympiad.org.bd/forum/includes/phpbb-latex.php' for inclusion (include_path='.:/opt/php53/lib/php')
[phpBB Debug] PHP Warning: in file [ROOT]/includes/session.php on line 1042: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4786: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4788: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4789: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4790: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
BdMO Online Forum • View topic - A Combinatorial Programming Problem

A Combinatorial Programming Problem

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

Moderators: bristy1588, Labib

Facebook Twitter

A Combinatorial Programming Problem

Post Number:#1  Unread postby 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
Masum
 
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm
Location: Dhaka,Bangladesh

Re: A Combinatorial Programming Problem

Post Number:#2  Unread postby *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
*Mahi*
 
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974

Re: A Combinatorial Programming Problem

Post Number:#3  Unread postby 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
Masum
 
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm
Location: Dhaka,Bangladesh

Re: A Combinatorial Programming Problem

Post Number:#4  Unread postby *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
*Mahi*
 
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974

Re: A Combinatorial Programming Problem

Post Number:#5  Unread postby 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

Post Number:#6  Unread postby 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
Masum
 
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm
Location: Dhaka,Bangladesh

Re: A Combinatorial Programming Problem

Post Number:#7  Unread postby *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
User avatar
*Mahi*
 
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974


Share with your friends: Facebook Twitter

  • Similar topics
    Replies
    Views
    Author

Return to International Olympiad in Informatics (IOI)

Who is online

Users browsing this forum: No registered users and 1 guest

cron