darroyue / iic2283 Goto Github PK

Hola, me surgió una duda sobre el input, cuando dicen que g_i < g_i+1 entiendo que el input esta ordenado, pero, antes se menciona que "Pueden haber varios guardaparques en una misma zona", me gustaría confirmar ¿esto significa que en el input no habrán guardaparques en mismas zonas, pero durante el algoritmo podrían haber guardaparque en mismas zonas?

Hola, podemos asumir largo par de los strings ?

Hola! Quisiera saber si puedo usar la librería bisect de python. Básicamente necesito hacer una búsqueda binaria y es mas eficiente que implementar el algoritmo por mi mismo. Gracias de antemano! (acá esta la referencia: https://docs.python.org/3/library/bisect.html)

Hola! Podemos numpy.fft y numpy.ifft para la tarea?

En el enunciado sale que el índice de similitud se calcula así

Entonces se tendrían que hacer n(n-1)/2 operaciones F. Lo que haría que el problema tuviera una complejidad intrínseca mínima de O(n^2). Sin embargo se nos pide una complejidad distinta de esa

¿Es esto un error? ¿O existe alguna forma de comparar cada par de string entre ellos menos de n(n-1)/2 veces?

Hola!

Respecto a la relación entre los valores de N y M, en la sección de input del enunciado aparece que $1 \leq N \leq M \leq 2 \cdot 10^3$, entonces, N (el largo del string S) es menor o igual que M (el largo del string T). Sin embargo, en los tests de ejemplo al final del enunciado, el valor de N siempre aparece como mayor al valor de M. Quisiera saber cuál es la relación correcta entre ambos valores, para así poder probar con tests acorde a lo que en verdad se pide.

Gracias de antemano!

Hola, llevo algunos días pensando en la solución pero no he logrado llegar a a algo suficientemente bueno. Seria posible pedir alguna pista adicional sobre el hint? No logro ver como podría calcular a partir de una secuencia A la lexicograficamente menor que cumpla la relación, incluso suponiendo que tengo una forma de hacerlo, no veo como me ayuda.

Si un guardaparques inicia en un foco de incendio y lo apaga, puede en ese mismo minuto moverse una casilla al lado?

¿Se podrán probar los tests antes de la entrega de la tarea como en edd? ¿Hay fecha para su liberación?

Hola, el input de los tranvías cumple con algún orden o en los ejemplos coincidió que el orden de los $l_i$ (cuadra de origen) es del menor al mayor?
Además, puede haber más de un tranvía con cuadra inicial y de destino iguales?

Hola! cuando se subira y cual sera el plazo de entrega, el original o se movera?
Pregunto para organizar las semanas nomas.

Hola, tengo una duda respecto al formato de entrega. Para mantener cierto orden separé las funciones que uso (como fft y fft inverso) del código mismo de la tarea, tengo el archivo t3.py junto a un utils.py, ¿puedo mantener ese formato o necesariamente todo mi código debe estar en el archivot3.py? Preferiría dejarlo separado, pero imagino que podrían haber problemas si la corrección es automatizada

Leyendo la pauta de la ayudantía y yendo a la ayudantía no me quedo claro para qué sirve la relajación K sobre las convoluciones que se deben hacer.

Buenas, acabo de hacer la p1 y en todos mis tests "creados a mano". Mi código con programación dinámica da el mismo resultado que mi código hecho con recursión (el cual es más probable que sea correcto).

Mi problema es que al hacerle push, el tercer test me da un valor que no corresponde y se me ocurre que hay dos causas posibles de esto. La primera causa posible es que mi código esté malo y la segunda causa posible es que estoy ocupando el mod más veces de las que ocupa el código que se usó para corregir (no es lo mismo (1 % 2) + (1 % 2), que (1 +1) %2).

En cualquier caso, lo que me ayudaría mucho para encontrar el problema y solucionarlo sería si pudieran publicar tests de menor magnitud que el tercero. Esto también ayudaría a futuros estudiantes que se encuentren con el mismo problema.

Por su tiempo, muchas gracias.

Hola! Llevo ya un par de horas pensando la tarea y buscando recursos en línea, y la verdad no estoy llegando a nada. Creo saber cómo resolverlo en O(nlogn) si K = 0, pero para valores mayores francamente no se me ocurre cómo plantearlo. ¿Pueden darme alguna recomendación?

Hola, está permitido el uso de la librería heapq? O en su defecto queue
Evidentemente, lo necesito para crear una cola de prioridades.

Hola! De clases tengo entendido que lo que hace que la multiplicación utilizando FFT sea O(n) es lo siguiente:

Donde se asume que los puntos v_i son iguales. Lo que me tiene confundido es que en el ejemplo de la implementación adjuntada en el enunciado dan de resultado en el ejemplo:

Donde se repite el punto -2. Esto me lleva a dos preguntas:

1. ¿Es válido que se repita un punto? ¿Cómo podemos asegurar que el resultado de la FFT de los mismos puntos para realizar la multiplicación más fácilmente?
2. Como la multiplicación es de 2n punto valores ¿con qué llenamos los otros puntos si el algoritmo siempre nos entrega n punto valores?

Hola, tengo una duda respecto a los caracteres que hacen overlap entre si debido a un K muy alto, mi duda es si estos casos se consideran como que agregan "caracteres extras" para matchear o no. Ejemplo:

K = 1
S = AABBAA

T = BBB

Mi duda es si T matchea con S en alguna posición o no matchea con S siguiendo las reglas de la tarea.

Hola buenas, quería saber si es que se podía usar la librería sortedcontainers, en específico SortedList

Podrían dar algún otro hint para la p2? Llevo estancado un buen rato y no logro llegar a una solución greedy que obtenga un óptimo local que sea óptimo global y finalmente acabo con que mi greedy se transforma en backtracking porque le falta información para decidir.

He pensado muchos algoritmos greedy, pero siempre se da un contraejemplo.

Si el enunciado pidiera un resultado sub óptimo, como dan muchos algoritmos greedy, entonces ya podría verlo mejor, pero al pedir el óptimo me parece imposible.

Tengo una duda respecto a los test cases y cómo funciona el algoritmo en si:

En el test case 3, nos da una relación de similitud = 3 y noto que esto es debido a que si separamos las 3 secuencias, nos queda:

ccdd ffdd
ddff ddcc
ffdd ddcc

Hasta este punto, tenemos un índice de similitud 2? pues las cadenas que se repiten son ddcc y ffdd no? Y luego con las cadenas que nos quedan, podemos dividir nuevamente y hacer:

cc dd
dd ff

Donde tenemos una nueva similitud con dd y ahí el índice de similitud es 3.

Estoy entendiendo bien el problema?

Hola,

Viendo los I/O de los ejemplos me entró la duda de lo que significa $A_1, A_2, A_3,$ etc. Por ejemplo, para el primer input donde debo encontrar la similitud entre frff y ffrf. Según la fórmula de similitud debiera comparar $A_1$ con $A_2$, $A_3$ y $A_4$. Luego, $A_2$ se entiende como el segundo caracter de ffrf (f) o como los dos primeros (ff)?

Lo mismo para $A_3$, en donde no estoy seguro si es r o ffr.

Gracias de antemano.

Hola, quería saber si está permitido el uso de la librería numpy

Hola!

Existe la posibilidad de ocupar la librería copy de python? En particular necesito la función deepcopy.

Saludos

Hay 2 test del github action que el resultado me da 1 mas que el correcto, pero si lo ejecuto en mi computador me da el resultado correcto, influye en algo eso? Que puede estar pasando?
Github Action:

Local:

Hola, que tal?

La implementación de FFT que dan en el enunciado entrega el siguiente forma de punto valor. Es esto correcto? Considerando que en el link sale que el output deberia ser el número sin estar en su forma de numero complejo?

Saludos

Hola! En mi computador logré obtener un tiempo de ejecucción cercano a 1.2 segundos. Quería saber si existe un grado de flexibilidad respecto al timeout cuando corran los tests con M cercano a $10^5$? Porque asumo el tiempo variará según la máquina que utilicen para correrlos.

Saludos y gracias de antemano.

Hola! soy Mauricio, el ayudante de tareas. aquí se van a responder las dudas de las tareas. Por favor revisen los issues anteriores antes de abrir uno nuevo y no cierren las issues.

Algunas dudas comunes sobre las tareas las respondo aquí:

¿Se puede usar librería X que no es parte de la "Python standard library"? En general, salvo que lo digamos en el enunciado de tareas, la respuesta será no.
¿Nos pueden dar una idea/pista/guía sobre cómo hacer la tarea X? En general no, pero a veces se darán ciertas ideas guías y/o posibles cosas a considerar para guiarlos.
¿Pueden dar más casos de prueba? No, pero ustedes son libres de crear y compartir casos entre ustedes. Si tienen dudas sobre cómo crear casos de prueba, pueden crear casos al azar y/o pensar en posibles casos bordes de su posible solución.