Problemas interactivos y de comunicación

En este módulo, asumimos que “interactivo” significa problemas que permiten un número limitado de consultas y “comunicación” significa problemas sobre comunicarse entre dos programas separados.

Problemas interactivos

Consejo 1 - Explotar los límites

Como casi todos los problemas interactivos tienen un límite en el número de consultas que se pueden hacer, hay que usar ese límite para guiar el razonamiento. ¡No tiene sentido intentar inventar una solución que use $\log N$ consultas cuando el límite es $N^2$!

Hay tres tipos de problemas interactivos:

1. Problemas que dicen directamente la complejidad objetivo de la solución (p. ej. IOI 2014 Rail).
2. Problemas que solo dicen el número máximo de consultas que se pueden usar (p. ej. IOI 2013 Cave).
3. Problemas que tienen un límite oculto en el número de consultas (p. ej. IOI 2015 Scales).

El primer tipo es agradable porque obtenemos una idea de cómo debería verse nuestra solución.

El segundo tipo es un poco menos agradable, pero todavía podemos aproximar la complejidad objetivo (p. ej. $N = 5000$ y $Q = 70000 \implies N \log N$ consultas).

El tercer tipo es el menos agradable, pero por suerte a veces todavía podemos averiguar el límite oculto. Por ejemplo, en problemas con puntuación relativa (como IOI 2015 Scales), podemos enviar una solución que usa un número fijo de consultas para cada entrada y luego reconstruir el límite a partir de nuestro puntaje.

Consejo 2 - Divide y vencerás

En la mayoría de los problemas interactivos, la solución es divide y vencerás. Suele ser o bien búsqueda binaria ($\log N$ consultas) o algo como mergesort ($N \log N$ consultas)

Cuando se ven límites de entrada grandes y límites de consultas pequeños, hay que pensar de inmediato en búsqueda binaria.

En este problema, tenemos $N = 512$ y $Q \leq 9$. Observar que $2^9 = 512$: esto sugiere que deberíamos usar búsqueda binaria.

En efecto, esa es la solución: hay que intentar llegar a ella por cuenta propia.

Solución

La solución es hacer búsqueda binaria sobre el orden DFS del árbol para hallar el prefijo más grande sin un huevo de Pascua. Esto funciona porque cualquier prefijo del orden DFS es una componente conexa.

#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
 
vector<int> graph[513], ord;
 
void dfs(int node = 1, int parent = 0) {
	ord.push_back(node);
	for (int i : graph[node])
		if (i != parent) dfs(i, node);
}
 
int findEgg(int N, vector<pair<int, int>> bridges) {
	for (int i = 1; i <= N; i++) graph[i].clear();
	ord.clear();
	for (pair<int, int> i : bridges) {
		graph[i.first].push_back(i.second);
		graph[i.second].push_back(i.first);
	}
	dfs();
	int l = 0, r = N - 1;
	while (l != r) {
		int mid = (l + r + 1) / 2;
		if (query(vector<int>(ord.begin(), ord.begin() + mid))) r = mid - 1;
		else l = mid;
	}
	return ord[l];
}

Problemas

Problemas de comunicación

Consejo 1 - No enviar todo

No hay que preocuparse por no poder enviar toda la información disponible: ¡en la mayoría de los casos, no se debería poder!

En este problema, se nos pide guardar y comparar un entero con varios otros enteros.

Como estos números pueden llegar hasta $2^{12} - 1$, no podemos guardar y acceder $A$ de forma naive (porque eso tomaría 24 operaciones).

Por suerte, todavía podemos guardar información suficiente sobre $A$, ¡solo que no en binario!

Solución - cmp

Así funciona nuestro algoritmo:

• Consideramos $A$ y $B$ en base 4
• Primero, codificamos cada prefijo de $A$ (6 operaciones)
• Luego, hacemos búsqueda binaria del prefijo común más largo $P$ de $A$ y $B$ (3 operaciones)
  • Si este prefijo tiene longitud 6, $A = B$
• En caso contrario, consideramos el dígito $d$ inmediatamente después de este prefijo para $B$:
  • Si $d > 1$, entonces solo hace falta comprobar si $4P + 3$ está codificado
  • En caso contrario, solo hace falta comprobar si $4P$ está codificado
  • Comprobamos si lo está y devolvemos la respuesta (1 operación)

Este algoritmo usa solo 10 operaciones en lugar de las 24 originales: ¡una mejora significativa!

#include "cmp.h"
 
int delta[6]{1, 4097, 5121, 5377, 5441, 5457};
 
void remember(int n) {
	for (int i = 0; i < 6; i++) bit_set((n >> i * 2) + delta[i]);
}
 
int compare(int b) {
	int l = 0, r = 6;
	while (l != r) {
		int mid = (l + r) / 2;
		if (bit_get((b >> mid * 2) + delta[mid])) r = mid;
		else l = mid + 1;
	}
 
	if (!l) return 0;
	int last_digit = (b >> l * 2 - 2) & 3;
	if (last_digit > 1) {
		if (bit_get((((b >> l * 2) << 2) + 3) + delta[l - 1])) return -1;
		return 1;
	} else {
		if (bit_get(((b >> l * 2) << 2) + delta[l - 1])) return 1;
		return -1;
	}
}

Consejo 2 - Fuerza bruta

A veces, la cantidad de información que podemos enviar es (ligeramente) mayor que la cantidad de información que necesitamos decodificar.

En este caso, simplemente podemos mapear cada pieza de información que queremos decodificar a una pieza de información que podemos enviar.

En este problema, queremos codificar y decodificar un arreglo de 64 enteros menores que 256 usando una secuencia no ordenada de 320 enteros menores que 256.

El número de arreglos de 64 enteros menores que 256 es ligeramente menor que el número de secuencias crecientes de 320 enteros menores que 256, así que podemos mapear cada arreglo a una secuencia creciente (usando bignums) y enviar esa secuencia.

Consejo 3 - XOR

XOR tiene una propiedad agradable: $A \oplus B \oplus A = B$. Esto nos permite resolver muchos problemas donde los datos enviados están corruptos o el receptor no sabe qué datos envió el emisor.

Solución - Coins

Sea la xor-suma de las posiciones con monedas cara arriba $X$. Observar que si volteamos la moneda $X \oplus c$, entonces la nueva xor-suma de las posiciones con monedas cara arriba es ahora $c$.

¡Esto permite que Shahrnaz determine $c$ después de que Arnavaz voltee exactamente 1 moneda!

#include "coins.h"
 
std::vector<int> coin_flips(std::vector<int> b, int c) {
	std::vector<int> flips(1);
	int xr = c;
	for (int i = 0; i < b.size(); i++) { xr ^= b[i] * i; }
	flips[0] = xr;
	return flips;
}
 
int find_coin(std::vector<int> b) {
	int xr = 0;
	for (int i = 0; i < b.size(); i++) { xr ^= b[i] * i; }
	return xr;
}

Problemas

Las tareas de CEOI se pueden encontrar aquí .