Skip to Content
CTRL K

Airline Map

Pista 1

No hay límite en el número de aristas del grafo que enviamos.

Como extraer los datos de las aristas es tan difícil, probablemente queremos enviar el grafo original más algunos vértices extra. Ahora el problema principal pasa a ser identificar los números de los nodos.

Pista 2

210≈10002^{10} \approx 1000, así que esto sugiere que deberíamos codificar datos bit a bit de alguna forma.

Pista 3

N2>N−512\frac{N}{2} > N - 512 cuando N≤1000N \leq 1000.

Solución

Además del grafo original, enviamos 10 “nodos-bit” extra, donde el nodo-bit ii y el nodo jj están conectados solo si el ii-ésimo bit de jj es 1. Si podemos identificar estos nodos-bit y sus números, hemos terminado.

Conectamos el nodo-bit ii con el nodo-bit i+1i + 1 para formar una “cadena”, de modo que podamos ordenarlos si los encontramos.

Todavía tenemos dos nodos extra para enviar, así que hacemos lo siguiente:

  • Conectamos el primer nodo extra con cada nodo que no es nodo-bit.
  • Conectamos el segundo nodo extra con el primer nodo extra.

El grado del primer nodo extra será N+1N + 1 mientras que el grado del segundo nodo extra será 1. Esto significa que podemos identificarlos de forma única y, por tanto, también los nodos-bit.

Todavía necesitamos deducir qué extremo de la “cadena” de nodos-bit es el nodo-bit 1. La observación clave es que el nodo-bit 1 siempre tendrá mayor grado que el nodo-bit 10. Así podemos identificar tanto los nodos-bit como sus números.

Esta solución envía exactamente 12 nodos extra.

Anna.cpp

#include "Alicelib.h"
#include <vector>
 
void Alice(int N, int M, int A[], int B[]) {
	std::vector<std::pair<int, int>> edges;
	// Original graph
	for (int i = 0; i < M; i++) edges.push_back({A[i], B[i]});
	// Bit nodes to find node numbers
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < N; j++) {
			if (j & (1 << i)) edges.push_back({N + i, j});
		}
		if (i < 9) edges.push_back({N + i, N + i + 1});
	}
	// Special vertex connected to all nodes but bit nodes
	for (int i = 0; i < N; i++) edges.push_back({N + 10, i});
	// Other vertex to identify the special vertex
	edges.push_back({N + 11, N + 10});
	// Send the graph
	InitG(N + 12, edges.size());
	for (int i = 0; i < edges.size(); i++) MakeG(i, edges[i].first, edges[i].second);
}

Bob.cpp

#include "Boblib.h"
#include <vector>
 
std::vector<int> graph[1012];
bool adj[1012][1012], is_bit[1012], visited[1012];
int actual[1012];
 
void Bob(int V, int U, int C[], int D[]) {
	for (int i = 0; i < U; i++) {
		graph[C[i]].push_back(D[i]);
		graph[D[i]].push_back(C[i]);
		adj[C[i]][D[i]] = adj[D[i]][C[i]] = true;
	}
	// Find the 2 special vertices
	int special;
	for (int i = 0; i < V; i++) {
		if (graph[i].size() == 1 && graph[graph[i][0]].size() == V - 11) {
			special = graph[i][0];
			break;
		}
	}
	is_bit[special] = true;
	// Identify the bit vertices
	int last_bit = special;
	for (int i = 0; i < V; i++) {
		if (i != special && !adj[i][special]) {
			is_bit[i] = true;
			if (graph[i].size() <= graph[last_bit].size()) last_bit = i;
		}
	}
	for (int i = 9; ~i; i--) {
		visited[last_bit] = true;
		for (int j : graph[last_bit]) actual[j] += 1 << i;
		for (int j : graph[last_bit])
			if (is_bit[j] && !visited[j]) {
				last_bit = j;
				break;
			}
	}
	// Construct the graph again
	std::vector<std::pair<int, int>> edges;
	for (int i = 0; i < V; i++)
		for (int j = i + 1; j < V; j++) {
			if (adj[i][j] && !is_bit[i] && !is_bit[j])
				edges.push_back({actual[i], actual[j]});
		}
	InitMap(V - 12, edges.size());
	for (std::pair<int, int> i : edges) MakeMap(i.first, i.second);
}
Fundamentos