Directory Traversal

Pista 1

Si no estás seguro de por dónde empezar, piensa en qué representan los directorios y los archivos. Luego deberías poder reestructurar el problema en uno que parezca más fácil de abordar.

Respuesta a la pista 1

Forman un árbol donde las longitudes de los nombres de archivos/directorios representan los pesos.

Ahora, podemos plantear el problema de la siguiente forma:

Para cada nodo de un árbol, ¿cuál es la suma mínima de las longitudes de los caminos desde un nodo hasta todas las hojas del árbol?

Solución

Editorial oficial (C++)

Explicación

Para calcular las distancias desde cada nodo, calcularemos las distancias “interiores” y “exteriores” de cada nodo.

La distancia “interior” es la suma de las longitudes de los caminos desde un nodo hasta las hojas dentro de su subárbol.

La distancia “exterior” es la suma de las longitudes de los caminos desde un nodo hasta las hojas fuera de su subárbol.

Por ejemplo, en el siguiente árbol, la distancia interior para el nodo $4$ sería igual a $4$ , y la distancia exterior sería igual a $7$ .

Nota: Para el valor exterior, también tenemos que incluir los dos ../ que se requieren para retroceder.

¡Sigue pensando!

Ahora que llegaste hasta aquí, intenta hallar una forma de calcular esto por tu cuenta. :)

Calcular las distancias interiores

Podemos resolver esto con un DFS sobre el árbol, ya que el valor interior del padre es simplemente el valor interior del hijo (más una barra).

Calcular las distancias exteriores

¡Sorprendentemente, también podemos resolver esto con un DFS!

Nótese que si ya calculamos el valor exterior del padre de un nodo, tenemos toda la información que necesitamos para calcular el suyo también.

Esto es porque todo nodo exterior debe estar en el subárbol del padre ( $\texttt{inside}[p] - \texttt{inside}[n]$ ), o fuera del subárbol de ese padre ( $\texttt{outside}[p]$ ). Aquí, $p$ representa el padre, y $n$ representa el nodo actual.

Implementación

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

C++


#include <bits/stdc++.h>
using namespace std;
 
struct Data {
	bool is_file;  // is it a leaf
	int len;       // length of name
	int nleaves;   // number of leaves in subtree
	vector<int> children;
};
 
int main() {
	freopen("dirtraverse.in", "r", stdin);
 
	int n;
	cin >> n;
 
	vector<Data> bessie(n);
	int total_leaves = 0;
	for (int i = 0; i < n; i++) {
		string s;
		int m;
		cin >> s >> m;
 
		bessie[i].len = (int)s.size();
 
		if (m == 0) {
			bessie[i].is_file = 1;
			total_leaves++;
		}
 
		for (int j = 0; j < m; j++) {
			int x;
			cin >> x;
			--x;
			bessie[i].children.push_back(x);
		}
	}
 
	// compute insides
	vector<long long> inside(n);
	function<void(int)> search_inside = [&](int v) {
		if (bessie[v].children.empty()) {
			bessie[v].nleaves = 1;
			return;
		}
 
		for (int u : bessie[v].children) {
			search_inside(u);
 
			// need a slash if it isn't a file
			bool slash = !bessie[u].is_file;
			bessie[v].nleaves += bessie[u].nleaves;
			inside[v] += inside[u] + ((bessie[u].len + slash) * bessie[u].nleaves);
		}
	};
	search_inside(0);
 
	// and then compute outsides
	vector<long long> outside(n);
	function<void(int)> search_outside = [&](int v) {
		for (int u : bessie[v].children) {
			long long same =
			    (inside[v] - inside[u]) -
			    ((bessie[u].len + !bessie[u].is_file) * (bessie[u].nleaves));
 
			// add all ../s too
			outside[u] = same + outside[v] + (3 * (total_leaves - bessie[u].nleaves));
			search_outside(u);
		}
	};
	search_outside(0);
 
	long long ans = LONG_LONG_MAX;
	for (int i = 0; i < n; i++) { ans = min(ans, outside[i] + inside[i]); }
 
	freopen("dirtraverse.out", "w", stdout);
	cout << ans << endl;
}