Arrancamos con unos sencillos problemas que no requieren grandes conocimientos de programación.

No son más que una excusa para utilizar el juez, desentumecer tus músculos y comprobar que tus envíos aparecen. Para ello, solo debes completar la tarea del CV y esperar a que yo procese tus respuestas (manualmente).

Un consejo a no perder de vista: piensa con calma antes de lanzarte a programar.

Primeros problemas para descubrir que la algoritmia no es únicamente programar.

Algunos de estos problemas parecen tener solución obvia, pero al programarla, y enviarla al juez, descubrimos que es demasiado lenta. En eso consiste la algoritmia: en encontrar métodos más eficientes que la primera solución que se nos viene a la cabeza.

Si no conseguís escapar del time-limit (TLE), no os preocupéis. Los algoritmos eficientes son el alma de la asignatura y no hemos hecho más que empezar...

Estos problemas se resuelven guardando información sobre la parte del vector ya recorrida, o bien procesando el vector para obtener datos que luego permitan resolver el problema más fácilmente.

Debes pensar bien la información necesaria para resolver cada problema antes de empezar a programarlo, así como calcular el coste del algoritmo para evitar el time-limit (TLE).

Lo importante no es únicamente conseguir el AC, sino implementarlos con un código compacto y claro.

Además, recomendamos practicar en todos ellos su especificación pre/post, la función de cota y el invariante.

Con estos problemas pondrás en práctica varios de los esquemas algorítmicos iterativos que estudiamos durante el curso.

Debes pensar bien la información necesaria para resolver cada problema antes de empezar a programarlo, así como calcular el coste del algoritmo para evitar el time-limit (TLE).

Lo importante no es únicamente conseguir el AC, sino implementarlos con un código compacto y claro.

La recursión se utiliza mucho en FAL. El tema 4 construye las bases de los algoritmos recursivos que no se abandonarán el resto del cuatrimestre y que forman parte importante de algunos temas de ED (asignatura del segundo cuatrimestre).

Algunos de los ejercicios que aparecen aquí pueden implementarse también de forma iterativa. Pero para familiarizarte cuanto antes con el pensamiento recursivo, es mejor que los resuelvas con recursión y practiques así los conceptos del tema. Mejor aún sería que dieras varias pasadas por cada problema: empezando con recursión, que luego conviertes a recursión final, para terminar con la versión iterativa del algoritmo.

Hay un problema que, incluso, puede resolverse con una expresión.

El problema 357 - La prueba de las cajas y las bolas no es un ejercicio de divide y vencerás como tal, pero la estrategia seguida por el protagonista del concurso sí sigue esa idea.

Por su parte, el problema 342 - ¡No lo puedes saber! NO es de divide y vencerás, pero la temática es el juego de adivinar el número, por lo que se incluye aquí como testigo de que el juego es un ejemplo típico de divide y vencerás y búsqueda binaria.

El problema 306 - Dos igualdades sorprendentes presenta uno de los mejores algoritmos para calcular un número de Fibonacci: el primero que vimos tenía complejidad cuadrática, el segundo complejidad lineal y este tiene complejidad logarítmica. Es una consecuencia de la versión rápida de la exponenciación.

El problema 631 - Ascensores con nivel es el más complejo de resolver y por eso está el último. Si no lo conseguís, no os preocupéis, porque es difícil.

Algoritmos relacionados con vuelta atrás

Alguno es fuerza bruta, pues no se puede filtrar la solución hasta que ésta no está completamente construida.

Realízalos utilizando el esquema de vuelta atrás visto en clase para que te sirva de práctica.

El último necesita la función de estimación, que simula una estrategia voraz, consistente en estimar que en los pasos restantes siempre se elige lo mejor posible, ordenando los datos por mejor densidad / proporción, antes de la llamada a la vuelta atrás.

Estos problemas han aparecido en ediciones anteriores del concurso Las 12 uvas y están relacionados con el temario de la asignatura. Algunos, de hecho, han aparecido en pestañas anteriores.

Un buen número de estos problemas están inspirados en exámenes o pruebas de evaluación continua de la asignatura. Algunos hicieron el camino inverso, apareciendo primero en el concurso y terminando después en alguna prueba de evaluación continua o examen.

Algunos tienen restricciones fuertes de memoria que impiden ser resueltos con una función que implementa el algoritmo recibiendo los datos ya leídos, como exigimos en FAL. Para poder resolverlos hay que calcular la respuesta al vuelo, según se va leyendo la entrada. Aunque esa implementación no sería adecuada para la asignatura, sí sirven para practicar pues, al fin y al cabo, es un algoritmo que recorre el "vector de la entrada" de izquierda a derecha acumulando, quizá, la información procesada en variables adicionales y nunca leyendo en posiciones del vector anteriores a la tratada en cada vuelta del bucle.

Los problemas se listan por orden cronológico y no de temario por lo que la primera tarea es analizar qué tipo de algoritmo es el más adecuado (iterativo, recursivo, DYV o VA). La mayoría de los iterativos se prestan también a hacer precondición y postcondición, invariante y cota como en FAL, aunque hay algunos cuya especificación escapa al nivel de la asignatura.