3307 - Careful with Poison

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Post Reply
User avatar
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

3307 - Careful with Poison

Post by ymondelo20 » 4 years ago



"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

User avatar
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: 3307 - Careful with Poison

Post by ymondelo20 » 4 years ago

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.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

User avatar
alurquiza
Posts: 54
Joined: 4 years ago
Gender: Male

Re: 3307 - Careful with Poison

Post by alurquiza » 4 years ago

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.

User avatar
isaac
Posts: 83
Joined: 4 years ago
Gender: None specified

Re: 3307 - Careful with Poison

Post by isaac » 4 years ago

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.

User avatar
alurquiza
Posts: 54
Joined: 4 years ago
Gender: Male

Re: 3307 - Careful with Poison

Post by alurquiza » 4 years ago

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.

messiah
Posts: 2
Joined: 6 years ago
Gender: None specified

Re: 3307 - Careful with Poison

Post by messiah » 4 years ago

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

User avatar
isaac
Posts: 83
Joined: 4 years ago
Gender: None specified

Re: 3307 - Careful with Poison

Post by isaac » 4 years ago

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).

messiah
Posts: 2
Joined: 6 years ago
Gender: None specified

Re: 3307 - Careful with Poison

Post by messiah » 4 years ago

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.

Post Reply

Return to “Problem set”