Page **1** of **1**

### Colombian Collegiate Programming League 2012 Problems

Posted: **Wed Jun 06, 2012 3:35 am**

by **AhmadKhatar**

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!

### Re: Colombian Collegiate Programming League 2012 Problems

Posted: **Wed Jun 06, 2012 11:19 pm**

by **brianfry713**

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 matrix-power method.

### Re: Colombian Collegiate Programming League 2012 Problems

Posted: **Thu Jun 07, 2012 8:36 am**

by **nupt-xxp**

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

### Re: Colombian Collegiate Programming League 2012 Problems

Posted: **Thu Jun 07, 2012 2:21 pm**

by **stubbscroll**

12465 - Number theory (number of divisors)

12466 - Topological sort, DP

12469 - Combinatorial game theory (win/loss-minimax 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.

### Re: Colombian Collegiate Programming League 2012 Problems

Posted: **Thu Jun 07, 2012 2:42 pm**

by **AhmadKhatar**

nupt-xxp 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

Hi and thanks for your help!

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 unit-matrix(i.e. I);

}

else if ( n is even ){

return F(n/2)*F(n/2);

}

else{

return F(n-1)*F(1);

}

Remember that at each step of the recursion you should use modulus. Otherwise the result will be an overflow.

### Re: Colombian Collegiate Programming League 2012 Problems

Posted: **Fri Jun 08, 2012 8:53 am**

by **nupt-xxp**

AhmadKhatar wrote:nupt-xxp 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

Hi and thanks for your help!

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 unit-matrix(i.e. I);

}

else if ( n is even ){

return F(n/2)*F(n/2);

}

else{

return F(n-1)*F(1);

}

Remember that at each step of the recursion you should use modulus. Otherwise the result will be an overflow.

Thanks , i solved it! And the picture you shows is wonderful !

Also i found another wonderful picture!

### Re: Colombian Collegiate Programming League 2012 Problems

Posted: **Sat Jun 09, 2012 5:27 pm**

by **nupt-xxp**

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 matrix-power method.

Now i'm thinking 12464,but i've no idea to solve it even you give the hints above.

a,b,n is so large and how to express a rational number ....

i'm puzzled and could someone tell me ?

### Re: Colombian Collegiate Programming League 2012 Problems

Posted: **Tue Jun 12, 2012 12:32 am**

by **brianfry713**

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.

### Re: Colombian Collegiate Programming League 2012 Problems

Posted: **Wed Jun 13, 2012 7:59 pm**

by **nupt-xxp**

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.

think you !i solved it!