Introducción y jueces en línea
Qué vamos a ver hoy
| Min | Tema |
|---|---|
| 0–15 | Qué es la programación competitiva y formatos de competencia |
| 15–35 | El juez en línea, veredictos y el grupo del curso |
| 35–50 | Partes de un enunciado |
| 50–65 | Leer la entrada, escribir la salida y errores de formato |
| 65–90 | Cuatro problemas resueltos en vivo (los de la práctica) |
En la sesión 2 de esta semana cada estudiante resuelve un contest corto en el juez.
Un problema, un programa y un juez
En programación competitiva se escribe un programa que resuelve un problema descrito en un enunciado.
- El programa lee la entrada estándar y escribe en la salida estándar.
- Un juez en línea ejecuta el programa con casos de prueba ocultos.
- Cada caso tiene un límite de tiempo (por lo general 1 o 2 segundos) y un límite de memoria (por lo general 256 MB).
- La solución es correcta solo si pasa todos los casos.
Qué se practica
- Leer un problema y modelarlo.
- Elegir un algoritmo que quepa en el tiempo.
- Programarlo sin errores.
- Probarlo con casos borde antes de enviar.
ICPC, Codeforces y AtCoder
| ICPC | Codeforces (Div. 1 y 2) | AtCoder (ABC) | |
|---|---|---|---|
| Quién | Equipos de 3, un computador | Individual | Individual |
| Duración | 5 horas | 2 a 2.5 horas | 100 minutos |
| Ranking | Problemas resueltos, luego penalización | Puntos; el valor de cada problema baja con el tiempo | Puntos fijos por problema, luego tiempo |
| Envío rechazado | +20 min de penalización | −50 puntos en ese problema | +5 min de penalización |
Las rondas Div. 3, Div. 4 y Educational de Codeforces usan reglas tipo ICPC. En todos los formatos, un envío rechazado en un problema que nunca se resuelve no suma penalización.
Cómo se calcula la penalización
| Equipo | A | B | C | Resueltos | Penalización |
|---|---|---|---|---|---|
| Rojo | + 25' | +1 40' | −2 | 2 | 85 |
| Azul | +2 30' | + 50' | 2 | 120 | |
| Verde | + 10' | −3 | + 100' | 2 | 110 |
+1 40' significa: resuelto en el minuto 40, con 1 envío rechazado antes.
Penalización = suma, en los problemas resueltos, del minuto del AC + 20 por cada rechazo previo.
Rojo: 25 + (40 + 20) = 85
Azul: (30 + 40) + 50 = 120
Verde: 10 + 100 = 110. Los 3 rechazos en B no cuentan.
Orden final: Rojo, Verde, Azul.
El juez en línea
Qué hace con el código y qué significa cada veredicto.
Qué pasa después de enviar
- Los casos se ejecutan en orden. El juez se detiene en el primer caso que falla (Codeforces) o los ejecuta todos y muestra cada resultado (CSES, AtCoder).
- Cada caso mide tiempo y memoria por separado.
- El caso 1 suele ser el ejemplo del enunciado.
Qué significa cada veredicto
| Veredicto | Significa | Causa típica en Python |
|---|---|---|
| AC | Accepted: pasó todos los casos | |
| WA | Wrong Answer: la salida no coincide | Idea incorrecta, caso borde, formato de salida |
| TLE | Time Limit Exceeded | Algoritmo lento para el tamaño de la entrada |
| MLE | Memory Limit Exceeded | Listas enormes, guardar todo lo leído sin necesidad |
| RE | Runtime Error: el programa terminó con error | IndexError, ValueError, división por cero, recursión profunda |
| CE | Compilation Error | Error de sintaxis (según el juez, aparece como CE o RE) |
Seis envíos para el mismo problema
Problema: leer n y luego n enteros, uno por línea, e imprimir su suma. Restricción: n ≤ 2·10⁵. Elija un envío y presione Enviar.
Cómo se usa el juez en este curso
- Crear cuenta en Codeforces, AtCoder, CSES y vJudge con el mismo nombre de usuario.
- Unirse al grupo del curso: [enlace pendiente].
- Abrir el contest de la semana y leer los problemas en orden.
- Probar la solución en el computador con los ejemplos.
- Enviar eligiendo el lenguaje correcto.
Lenguaje al enviar
En el curso todos los envíos se hacen con PyPy 3.
PyPy compila el código mientras corre, así que los bucles son mucho más rápidos que con el intérprete normal de Python.
En Codeforces se elige PyPy 3-64. En AtCoder y CSES, la opción que dice PyPy.
Partes de un enunciado
Dónde está cada dato que necesita el programa.
Anatomía de un enunciado
Weird Algorithm (CSES), versión resumida
Un algoritmo recibe un entero positivo n. Si n es par, lo divide entre 2. Si n es impar, lo multiplica por 3 y le suma 1. Repite hasta que n sea 1. Debe simular el algoritmo para un n dado.Entrada
Una única línea con el entero n.Salida
Imprimir en una línea todos los valores que toma n, separados por espacios.Restricciones
1 ≤ n ≤ 10⁶Ejemplo
Entrada: 3 Salida: 3 10 5 16 8 4 2 1
Qué dicen las restricciones
Tamaño de la entrada
n ≤ 2·10⁵ o n ≤ 10⁶ dice cuántas operaciones caben. Con 10⁶ números hay que leer rápido (lo vemos en un momento).
Rango de los valores
aᵢ ≤ 10⁹ y n ≤ 2·10⁵ hacen que la suma llegue a 2·10¹⁴. En C++ eso no cabe en un int. En Python los enteros no tienen límite.
Número de casos
"La primera línea tiene t, el número de casos". A veces se garantiza que la suma de n en todos los casos no pasa de 2·10⁵.
Garantías
"Los números son distintos", "existe al menos una respuesta". Cada garantía elimina un caso que no hay que programar.
Entrada y salida en Python
Cómo leer la entrada, cómo escribir la salida y los errores de formato más comunes.
Leer y escribir en Python
def main():
n = int(input())
a = list(map(int, input().split()))
print(sum(a))
main()
input()lee una línea de la entrada y la devuelve como string.int()convierte el string en número.split()separa la línea por espacios.print()escribe y agrega un salto de línea.print(*a)imprime una lista separada por espacios.- Todo el código va dentro de
main().
Formatos de entrada comunes
# un entero n = int(input()) # varios enteros en una línea n, k = map(int, input().split()) a = list(map(int, input().split())) # un string s = input()
# t casos de prueba
t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))
print(sum(a))
Error frecuente: n, k = input().split() deja n y k como strings. Hay que convertirlos: n, k = map(int, input().split()).
Errores de formato de salida
· marca un espacio y ↵ un salto de línea.
Problemas de la práctica
Weird Algorithm, Missing Number, Repetitions e Increasing Array.
Simular el algoritmo paso a paso
def main():
n = int(input())
out = [n]
while n != 1:
if n % 2 == 0:
n //= 2
else:
n = 3 * n + 1
out.append(n)
print(*out)
main()
Usar // y no /: n / 2 da un float y se imprime 5.0.
Encontrar el número que falta
Se dan n − 1 números distintos entre 1 y n. Hay que encontrar el que falta. Ejemplo: n = 5, números 2 3 1 5.
Suma de 1 a n: n(n+1)/2 = 15
Suma de los dados: 2+3+1+5 = 11
Falta: 15 − 11 = 4
def main():
n = int(input())
a = list(map(int, input().split()))
total = n * (n + 1) // 2
print(total - sum(a))
main()
Hace una sola pasada sobre los datos: O(n). Ordenar y buscar el hueco también funciona, pero cuesta O(n log n).
La racha más larga de un mismo carácter
def main():
s = input()
best = cur = 1
for i in range(1, len(s)):
if s[i] == s[i - 1]:
cur += 1
if cur > best:
best = cur
else:
cur = 1
print(best)
main()
Mínimo de movimientos para que no decrezca
Un movimiento suma 1 a un elemento. Si a[i] es menor que el anterior, hay que subirlo hasta igualarlo.
def main():
n = int(input())
a = list(map(int, input().split()))
moves = 0
mx = a[0]
for x in a:
if x < mx:
moves += mx - x
else:
mx = x
print(moves)
main()
Problemas de la práctica
AtCoder (problemas A)
Antes de enviar
- Leer las restricciones y el formato de entrada y salida.
- Escribir el código dentro de
main(), leer coninput()e imprimir conprint(). - Probar con los ejemplos del enunciado.
- Probar casos borde: n = 1, el valor máximo, todos iguales.
- Quitar los
printde depuración. - Elegir PyPy 3 como lenguaje al enviar.