Taskauthor

Parte 1 - algoritmos de camino más corto

En este subproblema, nos piden crear casos de prueba que rompan ciertos algoritmos de camino más corto provocando TLE.

Esto es muy educativo porque obliga a analizar los cuellos de botella de estos algoritmos y cómo funcionan exactamente.

Subtareas 1 y 3 - romper Floyd-Warshall

El algoritmo de Floyd-Warshall siempre usa exactamente $V^3$ iteraciones.

Esto significa que podemos simplemente poner $V$ en 101 y $E$ en 0 para forzar TLE.

Código

print(101)  # Generar el grafo
for i in range(101):
	print(0)
 
print(1)  # Una sola consulta
print(0, 1)

Subtareas 2 y 5 - romper Bellman-Ford

El algoritmo de Bellman-Ford normalmente usa exactamente $E(V - 1)$ iteraciones, pero en este caso está un poco optimizado.

Aun así, podemos forzar al algoritmo a usar exactamente $E(V - 1)$ iteraciones.

Primero, observemos que debemos tener $E \geq V$ o si no el algoritmo cortará antes de tiempo.

Si miramos la implementación de este Bellman-Ford en particular, notemos que “relajamos” las aristas conectadas al nodo 1, luego al nodo 2, etc.

Esto significa que si tenemos una línea recta desde el nodo $V - 1$ hasta el nodo 0 (y no hay otras aristas), entonces solo se relajará 1 arista por ciclo.

También podemos agregar algunas auto-aristas (con pesos positivos) del nodo 0 a sí mismo para aumentar $E$ sin disparar un corte temprano, ya que nunca es óptimo ir de un nodo a sí mismo vía una auto-arista.

$(V, E) = (100, 1100)$ para la subtarea 2 y $(V, E) = (300, 347)$ para la subtarea 5 nos permiten forzar TLE.

Código

print(300)  # Cambiar (300, 48) por (100, 1011) para la subtarea 2
print(48, end=" ")
for i in range(48):
	print(0, 1, end=" ")  # Auto-aristas
print()
for i in range(1, 300):
	print(1, i - 1, 1)
 
print(10)  # 10 consultas
for i in range(10):
	print(299, 0)

Subtareas 4 y 6 - romper Dijkstra

A primera vista, estas subtareas parecen imposibles: ¡el algoritmo de Dijkstra siempre tiene complejidad $\mathcal{O}(E \log V)$!

… ¿o no?

Observemos que la complejidad $\mathcal{O}(E \log V)$ solo es cierta si no hay aristas negativas.

¿Qué ocurre cuando hay aristas negativas en el grafo? Consideremos la siguiente construcción:

Si no hubiera aristas negativas, solo iteraríamos las aristas conectadas al nodo más a la derecha una vez.

Sin embargo, notemos que en la construcción de arriba, iteraremos esas aristas dos veces.

Esto significa que si encadenamos $N$ de esos triángulos, el algoritmo de Dijkstra usará $2^N$ iteraciones — mucho más que el $V \log E$ esperado.

Con 16 triángulos, podemos forzar TLE.

Código

print(33)
print(0)
print(1, 0, 1)
print(1, 1, 1)
for i in range(2, 31, 2):
	print(1, i, -2 * (2 ** (i // 2)))
	print(2, i + 1, 2 ** (i // 2), i, 0)
 
print(7)
for i in range(7):
	print(32, 0)

Parte 2 - el problema “misterioso”

Subtarea 7 - forzar TLE

Código

print(250, 1501)
for i in range(300):
	for j in range(i + 1, 250, i + 1):
		print(i, j)
for i in range(88):
	print(1, 2 * i + 3)

Subtarea 8 - forzar que no haya TLE

Código

print(753, 1501)
for i in range(1, 752):
	if i != 1:
		print(0, i)
	print(i, 752)

int main() {
	FOR(TC, 1, 7) {
		setOut("apio-2013-taskauthor_" + ts(TC) + ".out");
		int V;
		vpi adj[300];
		vpi query;
		if (TC == 1 || TC == 3) {
			V = 101;
			query.pb({0, 0});
		} else if (TC == 2) {
			V = 100;
			F0R(i, V - 1) adj[i + 1].pb({i, -1});
			F0R(i, 950) adj[0].pb({1, 1000});
			F0R(Q, 10) query.pb({V - 1, 0});
		} else if (TC == 5) {
			V = 300;
			F0R(i, V - 1) adj[i + 1].pb({i, -1});
			F0R(i, 40) adj[0].pb({1, 1000});
			F0R(Q, 10) query.pb({V - 1, 0});
		} else if (TC == 4 || TC == 6) {
			V = 33;  // 1+V+(V/2)*6+1+6*2
			int wei = 999999;
			for (int i = 0; i < V - 1; i += 2) {
				adj[i].pb({i + 2, -1});
				adj[i].pb({i + 1, 0});
				adj[i + 1].pb({i + 2, -wei});
				wei /= 2;
			}
			F0R(i, 6) query.pb({0, V - 1});
		}
		ps(V);
		F0R(i, V) {
			pr(sz(adj[i]));
			trav(t, adj[i]) pr(' ', t.f, ' ', t.s);
			ps();
		}
		ps(sz(query));
		trav(t, query) ps(t.f, t.s);
	}
}