Primeros problemas IOI

Tres problemas para empezar a usar el archivo IOI, con prerrequisitos, enfoques iniciales y pistas opcionales. Puedes seguir este orden o elegir el que se relacione con la clase que estás estudiando. No hay un tiempo de intento ni un registro requerido: las pistas están plegadas para que puedas decidir cuándo consultarlas.

Las subtareas y puntos indicados proceden de los PDFs oficiales. Las variantes propuestas al final de cada problema son ejercicios para explorar la idea, no subtareas adicionales del juez.

1. Consultas y conteos · Mutating DNA

Prerequisitos: strings, arreglos y 17 - Sumas de prefijos. Abre Mutating DNA y su PDF. Primero compila la interfaz pedida y comprueba los ejemplos. Objetivo inicial: resolver correctamente una consulta sobre un intervalo pequeño, incluso cuando es imposible transformar una cadena. La primera meta oficial es la subtarea 1: intervalos de largo a lo sumo tres (y−x ≤ 2, 21 puntos). Después busca evitar recorrer el intervalo en cada consulta. Fuente: PDF de Mutating DNA, página 2.

Para explorar la idea: compara un caso con pares opuestos y otro con un ciclo de tres letras. ¿Por qué uno requiere un intercambio y el otro dos? Si el alfabeto tuviera cuatro letras, ¿seguirían siendo esos los únicos casos? La solución oficial permite contrastar el argumento.

2. Construcción y validación · Connecting Supertrees

Prerequisitos: 15 - Grafos I - BFS y DFS, 19 - Union-Find (DSU) y recorridos para verificar conectividad. Trabaja con Connecting Supertrees. Objetivo inicial: construir o rechazar instancias con valores solamente 0 y 1 (subtarea 2, 10 puntos; el caso de todos unos tiene además su grupo de 11 puntos). Luego estudia qué cambia al permitir 2: la subtarea 5 permite 0, 1 y 2 y vale 21 puntos, sin garantizar que exista una construcción. Dibuja los grafos antes de codificar. Fuente: PDF de Supertrees, página 3.

Para explorar la idea: en un grafo pequeño, enumera los caminos simples entre cada par y compáralos con la matriz pedida. Estar conectado no basta: ¿puedes dar una matriz que exija un camino de A a B y de B a C, pero ninguno de A a C? Esa contradicción ayuda a entender las condiciones de rechazo.

3. Presupuesto de consultas · Combo

Prerequisitos: strings, invariantes y Formato IOI y debugging. Trabaja con Combo y lee literalmente la definición de press y las restricciones de la secuencia. Objetivo inicial: descubrir la secuencia con una estrategia sencilla que extienda un prefijo correcto, registrando cuántas llamadas realiza. La subtarea 1 fija N=3 y vale 5 puntos. Para conseguir los 95 puntos completos del segundo grupo, necesitas q ≤ N+2 llamadas; existen escalones de puntaje parcial descritos en el PDF. Además, cada consulta tiene largo a lo sumo 4N y nunca puedes superar 8000 llamadas. No asumas que acertar la cadena basta para obtener 100. Fuente: PDF de Combo, páginas 1 y 3.

Para explorar la idea: sigue las consultas de un caso pequeño y cuenta por separado las usadas para el primer símbolo, los intermedios y el último. Una estrategia puede acertar la secuencia y exceder el presupuesto: esa es la razón de analizar las llamadas además de la respuesta. La solución oficial muestra cómo aprovechar más información en cada consulta.

Para seguir, puedes buscar problemas del mismo tema en Temas, volver a una clase que quieras profundizar o probar una sesión de Simulacros.