3304 - Super Pow

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.
User avatar
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

3304 - Super Pow

Post by ymondelo20 » 4 years ago



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

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

Re: 3304 - Super Pow

Post by isaac » 4 years ago

La idea es precalcular los factoriales hasta 10^6 y luego exponenciacion modular.

ypizarroza
Posts: 3
Joined: 4 years ago
Gender: Male

Re: 3304 - Super Pow

Post by ypizarroza » 4 years ago

Me parece admin que se deben revisar los juego de datos de este problema. Por aunque lo resolvi no creo que sea esa la solucion. Para resolver este tipo de problemas hay que aplicar los teoremas o bien de Fermat o Euler y no se esta teniendo en cuenta esto.

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

Re: 3304 - Super Pow

Post by isaac » 4 years ago

Brow no veo por ningun lado la utilizacion del teorema de Fermat. Este por lo general se utiliza para buscar el inverso multiplicativo, cosa que no hay que hacer en este problema porque en ningun momento hay que dividir. Es solamente potencia y mas potencia, todo moduleado.

ypizarroza
Posts: 3
Joined: 4 years ago
Gender: Male

Re: 3304 - Super Pow

Post by ypizarroza » 4 years ago

Si pero para resolver A^B mod M hay q aplicar esto A^phi(M) es congruente con 1 mod M. Y en la solucion usaste para generar los JD no lo tuviste en cuenta. A^B % M no es igual a (A%M)^(B%M) % M.

humbertodiaz
Posts: 97
Joined: 5 years ago
Gender: None specified

Re: 3304 - Super Pow

Post by humbertodiaz » 4 years ago

Saludos a todos. Puedo confirmar que los datos deben estar mal. Yosvany, me da mucha curiosidad sobre como supiste intentar esa solucion. Al menos ahora se por que el ejercicio parecia requerir alguna tecnica imposible. Calcular (A! ^ B!) mod P se puede hacer con el pequeño teorema de Fermat, pero añadir otro exponente factorial se vuelve problematico.

El problema se podria arreglar removiendo el factorial del ultimo exponente. Es decir, si se cambia la expresion que se debe calcular a (A! ^ (B! ^ C)) mod P.

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

Re: 3304 - Super Pow

Post by isaac » 4 years ago

OK, tienen toda la razon, gracias por hacermelo saber. Un error de mi parte. La unica solucion que le veo por el momento es desactivar el problema del problemset.

humbertodiaz
Posts: 97
Joined: 5 years ago
Gender: None specified

Re: 3304 - Super Pow

Post by humbertodiaz » 4 years ago

El ejercicio todavia sigue activo. Creo que deberiamos arreglarlo y rejuzgar todos los envios, por que no seria justo que algunas personas mantengan los puntos del ejercicio mientras esta sellado eternamente. Originalmente pense que el ejercicio no tiene una solucion eficiente. Sin embargo, encontre un algoritmo que debe funcionar. Tengo que implementarlo y probarlo para asegurar que no se me haya escapado algun detalle. Con eso se podrian crear datos nuevos para el ejercicio.

Edit: Ya complete una solucion correcta. La verifique con otra solucion mas lenta pero confiable. Tengo datos para reemplazar las pruebas incorrectas, pero la cantidad maxima de casos tendria que ser 10^5 (en vez de 10^3) para asegurar que se hagan suficientes pruebas.

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

Re: 3304 - Super Pow

Post by ymondelo20 » 4 years ago

Hola Humberto,

Si les parece, me puedes enviar los nuevos juegos de datos para actualizarlo... y especificar los cambios que lleva el enunciado.

Saludos.
"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: 3304 - Super Pow

Post by ymondelo20 » 4 years ago

Disculpas por la demora, es que son muchas cosas :D
Ya he actualizado los JD, con las versiones enviadas por Humberto.
Los envíos serán rejuzgados en los siguientes minutos; Humberto puedes probar tú mismo la solución correcta.

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

Post Reply

Return to “Problem set”