Skip to Content
CTRL K

Fox And Names

Pista 1

Podemos hacer de los caracteres del alfabeto nodos de un grafo dirigido y hacer un orden topológico.

Pista 2

La dirección de las aristas de este grafo se puede determinar por pares adyacentes de palabras en nuestra entrada.

Solución

Explicación

La idea clave aquí es hacer un orden topológico sobre los caracteres del alfabeto.

Comparamos cada par de strings consecutivos para determinar la colocación relativa de un par de letras en el alfabeto. Al comparar dos strings, miramos la primera ocurrencia de letras distintas. En otras palabras, sacamos el prefijo común y comparamos las primeras letras.

Por ejemplo, si se nos da,

axcd
axbe

Vemos que el prefijo común es “ax”, así que el primer par de letras distintas es ‘c’ y ‘b’. Como “axcd” viene primero, eso significa que ‘c’ viene antes que ‘b’ en nuestro alfabeto modificado.

En el caso especial de que una palabra sea prefijo de la otra, como en el caso de,

abc
abcde

el string lexicográficamente mayor es el string más largo. Si los dos strings son iguales, entonces podemos simplemente imprimir “Impossible”.

Implementación

Complejidad temporal: O(n |namei∣)\mathcal{O}(n\text{ |name}_i|)

#include <bits/stdc++.h>
using namespace std;
 
// Used for topological sort
vector<int> indegree = vector<int>(26);
vector<vector<int>> conn = vector<vector<int>>(26, vector<int>());
vector<int> sorted;
 
void topological_sort() {
	queue<int> q;
	for (int i = 0; i < 26; i++) {
		if (indegree[i] == 0) { q.push(i); }
	}
	while (!q.empty()) {
		int pos = q.front();
		q.pop();
		sorted.push_back(pos);
		for (auto c : conn[pos]) {
			if ((--indegree[c]) == 0) { q.push(c); }
		}
	}
}
 
int main() {
	int n;
	// We make sure each pair of consecutive strings are in the right order
	string cur, prev;
 
	/*
	 * No previous string to compare the first string to,
	 * so we read it directly into prev
	 */
	cin >> n >> prev;
	for (int i = 1; i < n; i++) {
		cin >> cur;
 
		// Maximum length to compare
		int leng = min(prev.length(), cur.length());
		// How long the prefix has been the same for
		int samed = 0;
 
		while (samed < leng) {
			if (prev[samed] != cur[samed]) {
				/*
				 * As soon as we see a difference, we make sure
				 * the alphabetic follows the order presented
				 */
				int ncur = cur[samed] - 'a', nprev = prev[samed] - 'a';
				indegree[ncur]++;
				conn[nprev].push_back(ncur);
				break;
			}
			samed++;
		}
		/*
		 * If cur is a prefix of prev, then it is already impossible
		 * for cur to be lexicographically more than prev
		 */
		if ((samed == leng) && (prev.length() > cur.length())) {
			cout << "Impossible" << endl;
			return 0;
		}
		prev = cur;
	}
 
	topological_sort();
 
	// If topological sort not completeable, it's impossible
	if (sorted.size() < 26) {
		cout << "Impossible" << endl;
	} else {
		// Print out numbers converted back to characters
		for (int s : sorted) { cout << char(s + 'a'); }
	}
}
Fundamentos