Search found 51 matches

by frankr
1 year ago
Forum: Problem set
Topic: 2681 - Indian Line
Replies: 1
Views: 1777
Gender: Male

Re: 2681 - Indian Line

En este y en Indian Line II están pasando las soluciones con costo O(N^3).
by frankr
3 years ago
Forum: Problem set
Topic: 3239 - Find the Next Letter
Replies: 2
Views: 1305
Gender: Male

Re: 3239 - Find the Next Letter

Los casos de prueba parecen estar débiles puesto que la solución FB con costo O(T * N^2) da AC. Hay soluciones lineales para este problema.
by frankr
3 years ago
Forum: Problem set
Topic: 3560 - How Many Square Free Numbers
Replies: 2
Views: 1140
Gender: Male

Re: 3560 - How Many Square Free Numbers

Este problema es una versión más fuerte o generalizada de http://coj.uci.cu/24h/problem.xhtml?pid=2916.
by frankr
3 years ago
Forum: Problem set
Topic: 3560 - How Many Square Free Numbers
Replies: 2
Views: 1140
Gender: Male

Re: 3560 - How Many Square Free Numbers

Solución. Es necesario probar lo siguiente: * El producto A*B de dos números square free A y B es square free sí y solo sí A y B son primos relativos. * El producto de N números square free es square free también sí y solo sí ellos son primos relativos dos a dos. Una vez que se demuestre lo anterior...
by frankr
3 years ago
Forum: Problem set
Topic: 3540 - Exactly K Times
Replies: 8
Views: 3417
Gender: Male

Re: 3540 - Exactly K Times

Claro, con búsqueda binaria, muy buena idea! A pesar de que ya lo hice por la vía del hashing voy a implementar esta otra idea. Gracias nuevamente teruel.
by frankr
3 years ago
Forum: Problem set
Topic: 2171 - Another Range Tree Problem?
Replies: 8
Views: 4943
Gender: Male

Re: 2171 - Another Range Tree Problem?

No es necesario ordenar, si ordenas puedes subirlo a O(N Log N) dependiendo de método de ordenamiento que uses. Solo mantener la frecuencia de inicios y fines y luego cuando haces el barrido mantener un contador con la cantidad de intervalos activos.
by frankr
3 years ago
Forum: Problem set
Topic: 3540 - Exactly K Times
Replies: 8
Views: 3417
Gender: Male

Re: 3540 - Exactly K Times

También podemos añadir la versión II del problema con rangos mayores. Particularmente me gusta la idea de que existan varias variantes de un problema con distintos grados de dificultad, eso contribuye al entrenamiento en general y en particular al de los estudiantes de preuniversitario porque sería ...
by frankr
3 years ago
Forum: Problem set
Topic: 3540 - Exactly K Times
Replies: 8
Views: 3417
Gender: Male

Re: 3540 - Exactly K Times

teruel, gracias por la sugerencia del KMP, pero solo se me ocurre un O(N^3), no es eso no?. Yo lo hice con hash en O(N^2 Log N), pero también me asombré de ver las FB O(N^3 Log N) aceptadas.
by frankr
3 years ago
Forum: Problem set
Topic: 2171 - Another Range Tree Problem?
Replies: 8
Views: 4943
Gender: Male

Re: 2171 - Another Range Tree Problem?

Aunque el propio texto del problema y el título sugieren que puede haber una solución más sencilla que implementar un ST con lazy. Un ST para resolver este problema sería como tirarle con un arma nuclear, de todos modos es un buen problema para probar la implementación de un ST con lazy, y más aún, ...

Go to advanced search