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.
Pista 1 · qué conservan los intercambios
Los intercambios conservan cuántas veces aparece cada letra. Empieza por comprobar esa condición en ambas subcadenas.
Pista 2 · clasificar desajustes
Distingue los pares ordenados de letras distintas en una posición. ¿Qué desajustes puedes reparar directamente intercambiando dos posiciones?
Pista 3 · responder consultas
Tras emparejar desajustes opuestos, piensa qué ciclos quedan con tres letras. Guarda prefijos de cada tipo de par para obtener sus conteos en un intervalo.
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.
Pista 1
La existencia de algún camino divide los vértices en componentes. Comprueba que todas las exigencias de cero respeten esa división.
Pista 2
Dentro de una componente, agrupa vértices que deben tener un único camino. ¿Qué contradicción aparece si esa relación no es transitiva?
Pista 3
Para conectar grupos con dos caminos, considera un ciclo de representantes. Revisa los casos de uno y dos grupos: no puedes crear aristas paralelas.
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.
Pista 1
Si ya conoces un prefijo, ensaya extensiones y usa la respuesta para decidir qué información ganaste. Escribe el invariante antes de reducir llamadas.
Pista 2
Separa descubrir el primer símbolo de extender el resto. El primer símbolo no reaparece en la secuencia; los demás sí pueden repetirse, incluso consecutivamente. Usa esa restricción para diseñar consultas.
Pista 3
Una consulta puede contener varias candidatas. Comprueba que coincidencias que crucen sus fronteras no invaliden la interpretación de la respuesta.
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.