Cambio en P5 y tamaños de input

[FGarridoV]

Estimados alumnos,

Primero que todo, espero hayan tenido unas reponedoras Fiestas Patrias en familia. Mediante esta issue quisiera anunciar un pequeño cambio en el problema 5 y entregar los tamaños de inputs solicitados.

Cambio en P5

En el P5 se pide entregar una lista de listas de todas las secuencias máximas de bloques. Esto va a quedar como Bonus de 2 décimas extra en este laboratorio. Por lo tanto, quien entregue todas las posibles secuencia máximas del problema, tendrá 2 décimas extra en el laboratorio.

Como nuevo requisito de la pregunta, solo se pide 1 una secuencia máxima. Por lo tanto, si hubiera más de una. Se le pide retornar igualmente en una lista de listas solo una de esas soluciones.

Para que quede claro, si la secuencia máxima en un ejemplo es [4,5,4,3], entonces la respuesta es [[4,5,4,3]].

Tamaños de input para los problemas

A continuación entregaré los tamaños de inputs con los que se espera que los problemas sean resueltos en menos de 1 segundo. Estas ejecuciones fueron realizadas en Google Colab con el objetivo de que se evalúen de forma equitativa y justa.

• Problema 1b: lista de enteros del orden de *310^6** elementos debe ser resuelta en menos de un segundo.

• Problema 2: lista de enteros del orden de *410^6** elementos debe ser resuelta en menos de un segundo.

• Problema 3: palabras de *310^3** letras debe ser resuelta en menos de un segundo.

• Problema 4: listas de palabras (palabras de 4 letras) del orden de *2.310^4** elementos debe ser resuelta en menos de un segundo.

• Problema 5: matriz cuadrada de enteros de lado igual a 310^3 elementos. Lo que implica un orden de 910^6 elementos en la matriz debe ser resuelta en menos de un segundo.

Saludos y éxito en sus trabajos, Francisco

[jiechevarria]

Hola, como hago para probar mi codigo con inputs asi de grandes? Que no sea ingresando a mano una lista de 1 millon de elementos?

[FGarridoV]

Puedes crearte un método que genere listas con números. El output de ese método que sea el input de tu problema.

El método random.randint(a,b) genera un número aleatorio entre a y b (debes usar import random).

[jnsanhueza]

¡Hola profe! Respecto a la misma pregunta: ¿podrían entregar los rangos en que serán esos números aleatorios? En la pregunta 5, por ejemplo, si los números son entre 1 y 9 el tiempo de resolución será mayor que si son entre 1 y 100. Lo anterior, debido a que (en el segundo caso), es mucho más probable que no se pueda saltar entre bloques.

Lo mismo sucede con los otros ejercicios. ¡Quizás lo estoy haciendo mal y debería funcionar para cualquier par de números aleatorios de a y b!

[FGarridoV]

Efectivamente, podrían generarse caminos muy cortos. Dado un size, yo generé números con:

int(random.uniform(1,min((10000,size))+1)))

[pcseisdedos]

Para probar el tiempo de su código pueden usar esto:

Nosotros vamos a ejecutar las tareas en colab por lo tanto es altamente recomendable que ustedes prueben su código en esa plataforma, de esta manera podemos estandarizar la corrección independiente del computador y podemos calificar justamente sus algoritmos.

EDIT: En este ejemplo size es 500.000, la idea es que ustedes lo modifiquen según los tamaños descritos anteriormente.