Page 1 of 1

3307 - Careful with Poison

Posted: Sat Sep 26, 2015 9:00 pm
by ymondelo20

Re: 3307 - Careful with Poison

Posted: Wed Oct 07, 2015 2:51 pm
by ymondelo20
Caribbean Local Contests (CLC 2015)
Problem B - ID 3307 - Careful with Poison / Cuidado con el Veneno

Calculate the total roads C(2N, N) and subtracting those who touch and cross the poison applying the principles of the sum and product. Furthermore, for the calculation of the binomial numbers it is necessary to apply the formula for factorials and having pre-calculated the modular inverse thereof.

Calcular el total de caminos C(2N, N) y restarle los que tocan y atraviesan el veneno aplicando los principios de la suma y producto. Además, para el cálculo de los números binomiales es necesario aplicar la fórmula de los factoriales y haber pre-calculado los inversos modulares de los mismos.

Re: 3307 - Careful with Poison

Posted: Sat Nov 07, 2015 4:06 pm
by alurquiza
Como calcular eficientemente N!/((N - K)! * K!), la formula de las combinaciones. Porque que otra manera hay de calcular el factorial que no sea lineal.

Re: 3307 - Careful with Poison

Posted: Sat Nov 07, 2015 10:47 pm
by isaac
Respecto al calculo de los factoriales, como decia Mondelo en el mensaje previo, hay que precalcularlos, lo cual entra muy facil en tiempo porque N es hasta 10^6. La operacion en si, lleva un poco más de conocimiento respecto a la aritmética modular y como realizar las operaciones teniendo un límite, en este caso, moduleando el numero por 10^9+7 que por suerte para nosotros, es primo y se puede calcular el inverso modular. Lo otro que queda es la parte combinatoria para eliminar los caminos que pasan por el veneno.

Re: 3307 - Careful with Poison

Posted: Wed Nov 11, 2015 10:20 am
by alurquiza
Si ya me di cuenta, estaba pensando erroneamente, pensaba que el limite de los factoriales era 10^12 y en verdad es 2 * 10^6, estaba multiplicando en vez de sumando.

Re: 3307 - Careful with Poison

Posted: Thu Nov 12, 2015 11:43 am
by messiah
alurquiza wrote:Como calcular eficientemente N!/((N - K)! * K!), la formula de las combinaciones. Porque que otra manera hay de calcular el factorial que no sea lineal.
Hasta donde sé, puedes calcular combinaciones eficientemente usando el triangulo de Pascal (sin recursividad ni factoriales).

Salu2

Re: 3307 - Careful with Poison

Posted: Thu Nov 12, 2015 11:51 am
by isaac
Ahi utilizar el triangulo de pascal es ineficiente porque la complejidad es de orden n^2 y es hasta 10^6. La mejor opcion es utilizando aritmetica modular que haria el precalculo de los factoriales moduleados en N y haria las combinaciones en log2(MOD), lo cual es exponencialmente mas rapido que el triangulo de pascal para ese caso (o para casi cualquier otro).

Re: 3307 - Careful with Poison

Posted: Tue Nov 17, 2015 1:58 pm
by messiah
isaac wrote:Ahi utilizar el triangulo de pascal es ineficiente porque la complejidad es de orden n^2 y es hasta 10^6. La mejor opcion es utilizando aritmetica modular que haria el precalculo de los factoriales moduleados en N y haria las combinaciones en log2(MOD), lo cual es exponencialmente mas rapido que el triangulo de pascal para ese caso (o para casi cualquier otro).
Tienes toda la razón, mano.