Colombian Collegiate Programming League 2012 Problems
Moderator: Board moderators

 New poster
 Posts: 28
 Joined: Fri Mar 30, 2012 12:57 am
Colombian Collegiate Programming League 2012 Problems
Hi!
Does anybody know the algorithms used in the contest mentioned above?
I mean problems 12461 through 12470. I only need the names of the algorithms.
Thanks in advance!
Does anybody know the algorithms used in the contest mentioned above?
I mean problems 12461 through 12470. I only need the names of the algorithms.
Thanks in advance!

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: Colombian Collegiate Programming League 2012 Problems
12461  Airplane  Probability theory.
12462  Rectangle  I haven't solved it yet.
12463  Little Nephew  Simple math.
12464  Professor Lazy, Ph.D.  Simulation, GCD, rational numbers.
12465  The Turanga Leela Problem  I haven't solved it yet.
12466  Ancestors  I haven't solved it yet but you could call it graph theory.
12467  Secret Word  String processing.
12468  Zapping  Simple math, absolute value.
12469  Stones  DP.
12470  Tribonacci  I haven't solved it yet but you could try the matrixpower method.
12462  Rectangle  I haven't solved it yet.
12463  Little Nephew  Simple math.
12464  Professor Lazy, Ph.D.  Simulation, GCD, rational numbers.
12465  The Turanga Leela Problem  I haven't solved it yet.
12466  Ancestors  I haven't solved it yet but you could call it graph theory.
12467  Secret Word  String processing.
12468  Zapping  Simple math, absolute value.
12469  Stones  DP.
12470  Tribonacci  I haven't solved it yet but you could try the matrixpower method.
Check input and AC output for thousands of problems on uDebug!
Re: Colombian Collegiate Programming League 2012 Problems
yes, as brianfry713 says,i just plus that the 12467 can be solved by KMP.
and i don't know how to solve 12470,Could somebody tell me how to solve it?
maybe it's matrics , but i don't know its details,Could someone explain it to me ?
Please..
sorry for my bad english
and i don't know how to solve 12470,Could somebody tell me how to solve it?
maybe it's matrics , but i don't know its details,Could someone explain it to me ?
Please..
sorry for my bad english

 Experienced poster
 Posts: 151
 Joined: Tue Nov 16, 2004 7:23 pm
 Location: Norway
 Contact:
Re: Colombian Collegiate Programming League 2012 Problems
12465  Number theory (number of divisors)
12466  Topological sort, DP
12469  Combinatorial game theory (win/lossminimax with memoization)
12470  Convert recurrence into matrix, fast matrix exponentiation
I think it's better to ask questions about individual problems in their own threads in order to keep this forum more tidy.
12466  Topological sort, DP
12469  Combinatorial game theory (win/lossminimax with memoization)
12470  Convert recurrence into matrix, fast matrix exponentiation
I think it's better to ask questions about individual problems in their own threads in order to keep this forum more tidy.

 New poster
 Posts: 28
 Joined: Fri Mar 30, 2012 12:57 am
Re: Colombian Collegiate Programming League 2012 Problems
Hi and thanks for your help!nuptxxp wrote:yes, as brianfry713 says,i just plus that the 12467 can be solved by KMP.
and i don't know how to solve 12470,Could somebody tell me how to solve it?
maybe it's matrics , but i don't know its details,Could someone explain it to me ?
Please..
sorry for my bad english
I solved it using the recurrence attached at the bottom.
Then you can use fast exponentiation to find the answer. For example to find matrix F to the power of n (i.e. F(n)):
if ( n is 0 ){
return unitmatrix(i.e. I);
}
else if ( n is even ){
return F(n/2)*F(n/2);
}
else{
return F(n1)*F(1);
}
Remember that at each step of the recursion you should use modulus. Otherwise the result will be an overflow.
 Attachments

 Eq.JPG (12.55 KiB) Viewed 8854 times
Re: Colombian Collegiate Programming League 2012 Problems
Thanks , i solved it! And the picture you shows is wonderful !AhmadKhatar wrote:Hi and thanks for your help!nuptxxp wrote:yes, as brianfry713 says,i just plus that the 12467 can be solved by KMP.
and i don't know how to solve 12470,Could somebody tell me how to solve it?
maybe it's matrics , but i don't know its details,Could someone explain it to me ?
Please..
sorry for my bad english
I solved it using the recurrence attached at the bottom.
Then you can use fast exponentiation to find the answer. For example to find matrix F to the power of n (i.e. F(n)):
if ( n is 0 ){
return unitmatrix(i.e. I);
}
else if ( n is even ){
return F(n/2)*F(n/2);
}
else{
return F(n1)*F(1);
}
Remember that at each step of the recursion you should use modulus. Otherwise the result will be an overflow.
Also i found another wonderful picture!
 Attachments

 1339053958563_a041658666f48ccb0df4d242.jpg (8.16 KiB) Viewed 8823 times

 1339053958547_fb515764a20fdb2deaf8f87b.jpg (16.83 KiB) Viewed 8823 times
Re: Colombian Collegiate Programming League 2012 Problems
Now i'm thinking 12464,but i've no idea to solve it even you give the hints above.brianfry713 wrote:12461  Airplane  Probability theory.
12462  Rectangle  I haven't solved it yet.
12463  Little Nephew  Simple math.
12464  Professor Lazy, Ph.D.  Simulation, GCD, rational numbers.
12465  The Turanga Leela Problem  I haven't solved it yet.
12466  Ancestors  I haven't solved it yet but you could call it graph theory.
12467  Secret Word  String processing.
12468  Zapping  Simple math, absolute value.
12469  Stones  DP.
12470  Tribonacci  I haven't solved it yet but you could try the matrixpower method.
a,b,n is so large and how to express a rational number ....
i'm puzzled and could someone tell me ?

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: Colombian Collegiate Programming League 2012 Problems
On 12464 Try to solve the sample input with small n first. Code the rationals with two variables, one for the numerator and one for the denominator.
Check input and AC output for thousands of problems on uDebug!
Re: Colombian Collegiate Programming League 2012 Problems
think you !i solved it!brianfry713 wrote:On 12464 Try to solve the sample input with small n first. Code the rationals with two variables, one for the numerator and one for the denominator.