02 · La competencia y la estrategia

Aprender a programar · Ruta de Aprendizaje

Antes de empezar. Leer, compilar y ejecutar un programa: 01 - Tu primer programa.

🎯 Objetivos

Al terminar este módulo sabes:

  • Leer un enunciado de competencia: entrada, salida, restricciones y subtareas.
  • Usar las restricciones para decidir si tu idea alcanza en tiempo.
  • Evitar el error clásico de desbordar un int, y entender los veredictos del juez.

📖 La lección

Cómo es una competencia

En una olimpiada (OCI, IOI) recibes unos pocos problemas y varias horas. Cada problema vale 100 puntos repartidos en subtareas: versiones más fáciles del problema (con límites más chicos) que valen puntos parciales. Esto define la estrategia central de toda la ruta: asegurar subtareas vale más que perseguir la solución perfecta. Una solución sencilla puede obtener puntos si cumple las condiciones de alguna subtarea; la distribución depende del problema.

Un problema típico se ve así (los números cambian de problema en problema; la forma, no):

15 ptsn ≤ 20fuerza bruta (2ⁿ)35 ptsn ≤ 5 000doble ciclo (n²)50 ptsn ≤ 200 000ordenar o mejor (n log n)Subtarea 1Subtarea 2Subtarea 3la fuerza bruta correcta ya vale 15; con el doble ciclo llevas 50 sin haber “resuelto” el problema

Si el diagrama no cabe, deslízalo horizontalmente.

Cada subtarea es, en la práctica, un problema distinto con su propio límite: la primera se gana con la idea más simple que exista, la última exige la solución eficiente. Por eso se leen todas antes de programar.

Anatomía de un enunciado

Un enunciado describe una situación, una tarea, la entrada, la salida y los límites. La historia puede contener condiciones esenciales: tradúcelas a operaciones, sin saltártelas.

Ejemplo: entradas para un festival. Se venden n entradas a p pesos cada una. Se pide el dinero recaudado.

ParteQué diceQué deducimos
Entradados enteros n y phay dos datos, no una lista de compradores
Restricciones0 ≤ n ≤ 10⁹, 1 ≤ p ≤ 10⁶repetir n veces puede ser demasiado trabajo
Tareacalcular la recaudaciónsumar p n veces o multiplicar n por p
Salidaun enterocon 3 2000, imprimir 6000

La suma repetida usa n operaciones; el producto hace una cantidad constante. Pero elegir la fórmula no resuelve el rango: el máximo es 10¹⁵, de modo que hay que multiplicar en long long. Rapidez y representación son dos decisiones distintas.

Las restricciones son tu brújula

Volvamos al festival. Con n = 3, sumar 2000 tres veces y multiplicar 3 * 2000 dan 6000. Con n = 10⁹, la primera idea exige mil millones de sumas; la segunda sigue haciendo una multiplicación. Esa comparación ya permite elegir sin conocer todavía una notación matemática especial.

No confundas el valor de n con la cantidad de datos de entrada. El festival entrega solo dos números. Si otro problema entrega una lista de n precios, incluso una buena solución necesita leer sus n valores.

Por ahora haz dos preguntas: ¿cuántas veces se repite el trabajo?, ¿cuánto puede valer el resultado? En el módulo 07 contaremos ciclos y aprenderemos a resumir su crecimiento. Una tabla de tamaños no reemplaza ese razonamiento ni garantiza un tiempo de ejecución.

El template y la lectura de varios casos

Muchos problemas traen t casos de prueba en una sola ejecución:

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;                 // número de casos de prueba
    while (t--) {             // repite t veces (t-- resta 1 en cada vuelta)
        long long n;
        cin >> n;
        cout << (n % 2 == 0 ? "PAR" : "IMPAR") << "\n";
    }
    return 0;
}

Las dos líneas de sync_with_stdio/cin.tie aceleran la lectura — inclúyelas siempre; en entradas grandes marcan la diferencia entre pasar y TLE. El while (t--) es la forma corta de “repetir t veces”: la condición usa el valor de t y de paso le resta 1, hasta que llega a 0.

El enemigo silencioso: overflow

Un int aguanta hasta ~2·10⁹. Multiplica dos números de un millón y…

int chico = 1000000;
long long malo = chico * chico;          // ¡se desborda ANTES de guardarse!
long long bueno = 1000000LL * 1000000LL; // la LL fuerza aritmética de 64 bits
cout << malo << "\n" << bueno << "\n";

La primera multiplicación se desborda con int de 32 bits: en C++ el desbordamiento de enteros con signo tiene comportamiento indefinido, así que no hay una salida garantizada. Guardar después en long long no lo repara: la multiplicación ya ocurrió entre ints. La segunda expresión sí se calcula en 64 bits y vale 1000000000000.

El dibujo muestra el rango representable. No asigna un resultado a una operación que desborda.

¿Cabe el resultado en el tipo elegido?−2 147 483 64802 147 483 64710¹²: fueraRango de int de 32 bits; la flecha indica fuera de rango, no una escala.Una operación con signo que desborda no tiene un resultado garantizado.

Si el diagrama no cabe, deslízalo horizontalmente.

Regla práctica de competencia: si los valores pueden superar 10⁹, trabaja en long long de punta a punta. Y el reflejo que salva partidas: cuando un resultado que debería ser positivo aparece negativo o absurdamente chico, la primera sospecha es overflow.

Los veredictos del juez

AC aceptado · WA respuesta incorrecta · TLE se pasó del tiempo · RTE el programa se cayó (índice fuera de rango, división por cero) · CE no compiló. Son pistas, no diagnósticos exclusivos: un acceso inválido también puede causar WA, y un ciclo infinito puede causar TLE. Como punto de partida, mira WA → lógica o caso borde; TLE → complejidad; RTE → índices y límites.

Del enunciado a una solución

  1. Lee la tarea y las restricciones (¿qué n? ¿qué cabe?).
  2. Piensa un ejemplo chico a mano antes de programar.
  3. Compara el trabajo de tus ideas con el tamaño máximo, como en el festival.
  4. Programa, prueba con los ejemplos y un caso borde propio.
  5. Envía. Si falla, el veredicto te dice dónde buscar.

🏋️ Práctica

Práctica directa: Elegir tipo y trabajo

Lee n y p con 0≤n≤10⁹, 1≤p≤10⁶; imprime n·p. Entrada: 1000000000 1000000. Salida: 1000000000000000.

Aplicar en problemas

Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.

Problemas OCI reales, en español (cada nota trae el link a su mirror):

#ProblemaFaseQué practica
1Gastón y las baldosasNacional 2018la fórmula antes que el ciclo
2CubiertosRegional 2017reducir el enunciado a una línea
3CachipunNacional 2023restricciones que prohíben el O(n²)
4Ricardo y su nóctuloRegional 2024períodos y casos borde
5⭐ BaldosasRegional 2024n·m hasta 10¹⁸: puro long long

Más aplicaciones (en inglés)

#ProblemaDificultadQué practica
1Team (231A)★ (800)t casos, contar condiciones
2Domino piling (50A)★ (800)pensar la fórmula antes de codear
3Weird Algorithm (CSES 1068)★ (—)ciclo while, trampa de long long
4Missing Number (CSES 1083)★★ (—)fórmula n(n+1)/2, overflow
5Required Remainder (1374A)★★ (800)restricciones grandes ⇒ O(1)
6⭐ Theatre Square (1A)★★★ (1000)redondeo hacia arriba + long long

Un ejemplo para pensar

Un problema pide la suma de n números de hasta un millón. Una subtarea permite n ≤ 100; la completa, n ≤ 200 000. Una solución recorre los números una sola vez y acumula en un int de 32 bits. ¿Basta con que sea rápida?


← 01 - Tu primer programa · Ruta de Aprendizaje · 03 - Arreglos y búsqueda lineal →