Guía para interpretar enunciados

Enviado por jvilella el Mar, 19/12/2023 - 23:52

Introducción

A diferencia de otros concursos, los ejercicios de programación competitiva normalmente se corrigen mediante jueces automáticos. Esto quiere decir que en lugar de dedicar mucho tiempo a corregir las respuestas, ese mismo tiempo se ha invertido antes del concurso, para preparar ejercicios que se corrigen de manera automática. De hecho este proceso requiere bastante más tiempo que una corrección manual posterior.

Y entonces, ¿por qué se hace así? La corrección automática tiene diversas ventajas:

Los concursantes obtienen un “feedback” inmediato respecto a la validez de sus respuestas, y lo reciben durante el concurso, pudiendo así mejorarlas.
Permite a los concursantes conocer su rendimiento durante la prueba, pudiendo conocer su posición dentro de la clasificación en cada momento.
Los jueces pueden seguir, analizar y evaluar en tiempo real todas las respuestas de todos los concursantes.
La corrección es objetiva, igual para todos los concursantes, y no hay lugar a error humano.

Sin embargo este tipo de corrección requiere seguir unas pautas muy estrictas a la hora de que los concursantes entreguen sus respuestas, ya que sino el juez automático no será capaz de interpretarlas y las dará por inválidas.

En este documento se explica cómo interpretar los enunciados para hacer una entrega satisfactoria al juez automático.

Funcionamiento del juez automático

El juez automático funciona de la siguiente manera:

Recibe la respuesta del concursante (un código que debería resolver el problema que plantea el enunciado).
El juez compila el código y ejecuta el programa resultante.
El juez simula el teclado del usuario para introducir los datos al programa. Estos datos se conocen como entrada (o input). Estos datos de entrada no son aleatorios, los han configurado los jueces humanos con antelación.
El juez lee los datos que muestra el programa por pantalla. Estos datos se conocen como salida (o output).
Igual que los datos de entrada estaban configurados por los jueces humanos con antelación, estos mismos jueces humanos también han configurado con antelación al juez automático para que sepa que salida (resultado) debe generar un programa que cumpla correctamente con lo que pide el enunciado. De manera que en este último paso el juez comprueba que la salida se corresponde con la esperada.

Cada combinación de entrada-salida configurada por los jueces humanos se conoce como caso de prueba o testcase. Los casos de prueba son secretos, los concursantes no los conocen, para que no creen códigos diseñados específicamente para resolver esos casos de prueba. Existen varios casos de prueba para cada ejercicio, y el juez los prueba todos para cada entrega de cada concursante. Para que el código se dé por correcto tiene que responder la salida correcta para todos los casos de prueba.

El juez dará un veredicto sobre el código del concursante. Este veredicto suele ser uno de los siguientes:

Aceptado (o Accepted, AC)
El código es correcto, el ejercicio está correctamente solucionado.

Respuesta incorrecta (o Wrong Answer, WA)
El juez ha llegado hasta el paso 5 pero la salida generada por el código del usuario no se corresponde con la salida esperada.

Posibles causas:
1. El código no funciona correctamente.
2. El código funciona correctamente para algunos casos de prueba, pero no para todos. Una causa habitual de mal funcionamiento en C++ o Java (en Python esto no ocurre) es usar una variable de tipo int o float más allá del valor máximo (o mínimo) que puede almacenar.

Tiempo de espera excedido (o Time Limit Exceeded, TLE)
El juez ha llegado al paso 4 pero el programa es demasiado lento.

Posibles causas:
1. Hay un bucle infinito en el programa.
2. En algún caso de prueba (o en todos) el programa tarda demasiado en calcular la respuesta, es decir, el código del programa es demasiado lento y el juez requiere una solución más optimizada. Esto es porque el juez ejecuta el programa durante un máximo de 1 segundo (a no ser que se indique otra cosa en el enunciado), y en ese tiempo el programa tiene que haber dado una respuesta. Se puede estimar que en ese segundo se pueden ejecutar unas 10⁸ (cien millones) operaciones, así que una buena idea es estimar el número de operaciones que realizará nuestro programa en el peor de los casos antes de empezar a programarlo.

Error de ejecución (o Runtime Error, RE)
El juez ha llegado hasta el paso 4 pero durante la ejecución del programa algo ha fallado y el programa se ha abortado abruptamente.

Posibles causas:
1. Intentar dividir entre cero.
2. Intentar acceder a una posición inválida de un vector, como por ejemplo una posición negativa o una posición superior a la última posición del vector.

Error de compilación (o Compilation Error, CE)
El juez ha llegado al paso 2 pero el código recibido no compila.

Posibles causas:
1. Error de sintaxis en el código.
2. Utiliza funciones que no son estándar o no están incluidas mediante #include (C++) o import (Python, Java).
3. El lenguaje seleccionado no se corresponde con el lenguaje del código enviado.

Descripción de un ejercicio

Para garantizar que el concursante conoce con claridad los requisitos para hacer una entrega correcta al juez automático, los enunciado de un ejercicio de programación competitiva tienen siempre la misma estructura:

Enunciado: Explica el objetivo del ejercicio. Normalmente está adornado con un contexto para hacer del problema un ejercicio interesante.
Entrada o Input: Describe detalladamente el formato que tendrán los datos que introducirá el juez automático.
Salida o Output: Describe detalladamente cómo debe ser el formato de la respuesta que genere el código escrito por el concursante.
Restricciones o Constraints: Detalla qué tipo de condiciones se tienen que tener en cuenta, y cuáles no. Por ejemplo, puede decir que no se deben tener en cuenta número negativos, o valores superiores a 1000. Algunos ejercicios tienen subcasos (o subtasks), que quiere decir que la cantidad de puntos que se da a una solución es diferente en función de si funciona para todas las restricciones listadas o solo para algunas (por ejemplo, un código que funciona para valores todos los valores positivos puede recibir una puntuación mayor que otro código que solo funciona para valores entre 0 y 1000).
Ejemplo o Example: Uno o más ejemplos de entrada y su salida correspondiente. Esto tiene dos utilidades:
- Sirve para comprobar que se ha entendido bien el enunciado, el formato de entrada y el formato de salida.
- Es cómodo poder copiar y pegar el ejemplo de entrada durante las primeras comprobaciones que hace el concursante con su código de respuesta.

Los ejemplos no son exhaustivos, es decir, no pretenden cubrir todos los casos posibles, ni se muestran todos los casos de prueba que probará el juez automático.

Vocabulario

Leer	Obtener de la entrada (cin en C++, input() en Python, readLine() en Java)
Escribir	Mostrar por pantalla, es decir, en la salida (cout en C++, print() en Python, println() en Java)

La salida debe ser exacta

Cuando el juez automático compare la salida prevista (proporcionada por los jueces humanos) con la salida del programa entregado por el concursante, comparará letra por letra: cualquier letra que no deba estar, o cualquier espacio o salto de línea de más, etc serán motivo para resolver como erróneo el código.

Por ejemplo, si el Enunciado dice “Lee un número, multiplícalo por 2 y muestra el resultado”, el programa solo debe mostrar por pantalla el resultado de la multiplicación, sin ningún texto previo (ni “Resultado:”, ni “Escribe un número:”, ni ningún otro texto).

Expresiones matemáticas

Las matemáticas se caracterizan por su precisión y exactitud, y con los siglos se ha desarrollado un lenguaje igual de preciso y exacto para interpretarlas. Como los jueces automáticos requieren exactitud los enunciados de programación competitiva utilizan lenguaje matemático para expresar las características del problema.

Algunos ejemplos habituales:

Un valor v, tal que 0 < v < 100	El valor (al que hemos llamado v) tiene que ser superior a 0 e inferior a 100, es decir, está comprendido entre 1 y 99 (ambos incluidos)
Lee n líneas con k valores. 0 < n ≤ k	Al número de líneas lo llamamos n. Habrá por lo menos una línea, no habrá más líneas que valores en cada línea.
Un tablero n x m, donde 1 ≤ n,m ≤ 1000	Un tablero donde al número de filas lo llamamos n filas y al número de columnas lo llamamos m. El tamaño del tablero puede tener cualquier combinación de 1 a 1000 filas y 1 a 1000 columnas.
k valores x: 0 < x₁ ≤ 1000 0 ≤ x₂,...,x_n ≤ 1000	El primer valor (x₁) será un número entre 1 y 1000 (ambos incluidos). El resto de valores pueden ser cualquier número entre 0 y 1000 (ambos incluidos).

Restricciones

En el apartado restricciones se definen los valores que pueden tener los datos de la entrada. La solución del concursante no tiene que preocuparse de valores que estén fuera de esas restricciones.

Por ejemplo, si el ejercicio pide encontrar el valor más mayor de una serie numérica en el que las restricciones indican que los valores serán siempre negativos, no hace falta preocuparse por los valores negativos, ni tampoco mostrar un mensaje por pantalla si por la entrada se lee un valor negativo. No hace falta hacer nada porque a ese programa no se le va a poner nunca un valor negativo en la entrada, ningún caso de prueba tendrá valores negativos.