Level Generation

Solución en video

Por Ruben Jing

Nota: La solución en video puede no ser la misma que las otras soluciones. Código en C++, Python y Java.

Solución en video

Pistas

Pista 1

La cota superior para la cantidad de puentes que podemos tener es $n - 1$ porque cada puente está presente en cualquier árbol de expansión (spanning tree) del grafo.

Pista 2

Consideremos asignar cierta cantidad de estos nodos a formar un árbol. ¿Cómo podemos usar el resto de estos nodos para usar tantas aristas como sea posible?

Solución

Explicación

La mayor cantidad de puentes que podemos tener en un grafo con $n$ nodos es $n - 1$ puentes. En consecuencia, nuestra respuesta está en el rango $[n - 1, 2n - 2]$ .

Consideremos hacer búsqueda binaria sobre nuestra respuesta. Si tenemos $x$ aristas que hay que usar, entonces $\lfloor \frac{x + 1}{2} \rfloor$ de esas aristas deben ser puentes.

Recordemos que la mejor forma de crear puentes es crear un árbol. Así, usamos todas estas aristas puente para formar un árbol, y luego usamos la arista extra para conectar este árbol a alguna componente de nodos. Nótese que esta arista extra también es un puente. Con el resto de nuestros nodos, podemos formar un grafo completo de nodos para usar tantas aristas como sea posible.

Implementación

Complejidad temporal: $\mathcal{O}(Q\log{N})$

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int main() {
	int test_num;
	cin >> test_num;
	for (int i = 0; i < test_num; i++) {
		int nodes;
		cin >> nodes;
 
		ll low = nodes - 1;
		ll high = 2ll * (nodes - 1);
		while (low < high) {
			ll mid = (low + high + 1) / 2;
			int num_bridges = (mid + 1) / 2;
			int cycle_nodes = nodes - num_bridges;
			ll cycle_edges = 1ll * cycle_nodes * (cycle_nodes - 1) / 2;
 
			if (mid - num_bridges <= cycle_edges) {
				low = mid;
			} else {
				high = mid - 1;
			}
		}
 
		cout << low << '\n';
	}
}


import java.io.*;
 
public class LevelGeneration {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		int testNum = Integer.parseInt(br.readLine());
		for (int t = 0; t < testNum; t++) {
			int nodes = Integer.parseInt(br.readLine());
 
			long low = nodes - 1;
			long high = 2L * (nodes - 1);
			while (low < high) {
				long mid = (low + high + 1) / 2;
				long num_bridges = (mid + 1) / 2;
				long cycle_nodes = nodes - num_bridges;
				long cycle_edges = cycle_nodes * (cycle_nodes - 1) / 2;
 
				if (mid - num_bridges <= cycle_edges) {
					low = mid;
				} else {
					high = mid - 1;
				}
			}
 
			System.out.println(low);
		}
	}
};


t = int(input())
 
for _ in range(t):
	nodes = int(input())
 
	lo = nodes - 1
	hi = 2 * (nodes - 1)
 
	while lo < hi:
		mid = (lo + hi + 1) // 2
		num_bridges = (mid + 1) // 2
		cycle_nodes = nodes - num_bridges
		cycle_edges = cycle_nodes * (cycle_nodes - 1) // 2
 
		if mid - num_bridges <= cycle_edges:
			lo = mid
		else:
			hi = mid - 1
 
	print(lo)