Introducción a Omegaup, parte 2 - Problemas básicos
Hola de nuevo. Continuando con la serie Introducción a Omegaup, esta vez vamos a hacer referencia a los problemas más sencillos de la plataforma a la fecha. Aquí se encuentra la parte 1 de esta serie.
Para estos problemas, no se requiere conocer una técnica o un algoritmo en específico: simplemente requieren implementar (o simular) lo que se describe en el problema o hacer una o dos observaciones relativamente sencillas que permiten simplificar la implementación o acortar el número de operaciones que tu programa tendría que hacer y con ello poder resolver el problema dentro de los límites.
Material de estudio
Antes de pasar a la lista de problemas, quiero empezar con las lecturas recomendadas para empezar a resolver problemas en omegaUp:
- El Libro de Luis Vargas sobre Algoritmos. Este es el libro que usamos para preparar a los preseleccionados de México para la Olimpiada Internacional de Informática. Su lectura completa es recomendada, sin embargo las secciones VII y II son fundamentales.
- Los temas 1, 2, 4 y 5 del blog de Pier Paolo sobre algoritmos.
- The Importance of Algorithms (Topcoder Algorithm tutorials)
- Mathematics for Topcoders (Topcoder Algorithm tutorials)
Problemas directos
Estos concursos fueron diseñados para familiarizarse con la programación competitiva en general. Son excelentes para empezar y su solución generalmente no requiere dominar una técnica en específico, más bien requieren saber usar las construcciones (ciclos, condiciones, etc…) del lenguaje correctamente:
Problemas no-tan-directos
- Engranes (solución)
- Lento (solución)
- Subprimos (solución de diego_futbolm)
- La venganza de Silvio (solución)
- Las cartas del Dr. Lira (solución)
- El tablero de Bety (solución de spleensarethebest)
- Triángulos (solución TriangleConstruction en Topcoder)
y uno en Java:
Enviamos esta solución… y nos encontramos que no resuelve todos los casos (obtiene WA, wrong answer). Por qué? (Recomiendo al lector que haga una pausa aquí y trate de entender por qué no funciona).
Límites
Hay datos que no hemos considerado en la descripción del problema: los límites. Existen 3 tipos de límites comunes en omegaUp:
- Límite de tiempo: Tu solución no puede tardar más del tiempo indicado para resolver un caso. Para nuestro problema Sumas, tenemos 1 segundo para producir una solución. Para entender por qué el tiempo es un factor limitante, te recomiendo leer The Importance of Algorithms en los tutoriales de Topcoder.
- Límite de memoria: Tu solución no puede usar más megabytes de los permitidos por el límite para producir la respuesta.
- **Límites en las variables de entrada: **No todos los problemas tienen una sección específica donde se indice cuáles son los valores mínimos y máximos de una variable, por lo que necesitamos leer con atención el problema para obtenerlos.
En nuestra solución anterior, hay un dato que no consideramos: La suma de ambos números cabe en un entero de 64 bits. En nuestra solución anterior estábamos usando el tipo de datos int, los cuales tienen un límite de 32 bits (Un int en C puede guardar números entre $ -2^{31}$ hasta $ 2^{31}-1$, es decir, de -2147483648 hasta 2147483648 ). Para satisfacer el límite de 64 bits, necesitamos usar variables que puedan soportarlo: long long (en C)
Nota como tuvimos que cambiar el %d del printf/scanf por %lld para leer y escribir correctamente el entero long long. omegaUp evalúa las soluciones en Linux y para C/C++ usa el compilador g++.
La misma solución en Java:
Si quieres saber más sobre los tipos de variables y sus límites, te recomiendo leer: Representation of integers and reals en Topcoder.com .
Para saber más…
Aquí enlisto varias fuentes de muy buena información sobre cómo resolver problemas y diseñar algoritmos para concursos de programación en general. Los siguientes tutoriales estarán basados en estas fuentes, les recomiendo mucho darles una revisada:
- Problemas y Algoritmos, Luis Vargas.
- El blog de Pier Paolo sobre Algoritmos
- TopCoder tutorials. En particular les recomiendo empezar por The Importance of Algorithms y How to find a solution.
- El blog de Rodrigo Burgos (nivel avanzado)
Con qué otros problemas puedo practicar?
Aquí hay algunos otros problemas con los que puedes practicar para iniciarte en omegaUp. Incluyo un link al código de la solución, pero mi recomendación es que trates de hacerlos por tí mismo. Ve la solución sólo en caso de que estes completamente bloqueado:
Tienes otros tips o algunos tutoriales/soluciones que quieras compartir? Escríbelos en los comentarios.