Skip to Content
CTRL K

Hangman 2

Pista 1

Notemos cómo el problema solo da una cota sobre n⋅kn \cdot k. ¿Cuál es la cota sobre min(n,k)min(n, k), respecto de n⋅kn \cdot k?

Pista 2

Partamos el problema en dos casos: n<kn < k y n≥kn \geq k.

Explicación

Primero, notemos que min(n,k)≤nkmin(n, k) \leq \sqrt{nk} porque min(n,k)⋅min(n,k)≤n⋅kmin(n, k) \cdot min(n, k) \leq n \cdot k. Esto será importante para analizar la complejidad temporal de nuestra solución. Ahora, consideremos los dos casos dados en la segunda pista.

Caso 1: n<kn < k

Como n<nkn < \sqrt{nk}, podemos hacer fuerza bruta sobre cada par de strings y comprobar si difieren en no más de dos caracteres. Esto toma tiempo O(N2K)\mathcal{O}(N^2K), que es equivalente a tiempo O(NKNK)\mathcal{O}(NK\sqrt{NK}).

Caso 2: n≥kn \geq k

Comparemos dos strings. Notemos que permitir que a lo sumo dos caracteres sean distintos es equivalente a ignorar dos caracteres en ambos strings y comprobar la igualdad. Así, podemos hacer fuerza bruta sobre cada par de caracteres que ignoramos, y luego comprobar la igualdad entre strings.

Sea (i,j)(i, j) el par de caracteres sobre el que hacemos fuerza bruta. Entonces, tenemos los siguientes intervalos que necesitan ser idénticos en ambos strings:

[0,i−1],[i+1,j−1],[j+1,k−1][0, i - 1], [i + 1, j - 1], [j + 1, k - 1]

Ahora, si queremos comparar nuestros dos strings, solo necesitamos que las subcadenas sean iguales. Esto se puede comprobar usando hashing de strings.

Para cada string de nuestra lista, necesitamos hallar otro string que tenga los mismos hashes. Esto se hace mejor ordenando todas las tuplas de hashes, y luego comprobando ítems adyacentes y viendo si los hashes son iguales.

En total, esto toma tiempo O(NK2log⁡(N))\mathcal{O}(NK^2\log({N})). Con un poco más de análisis, se puede llegar a la complejidad temporal de O(NKNKlog⁡(NK))\mathcal{O}(NK\sqrt{NK}\log(\sqrt{NK})).

Implementación

Complejidad temporal: O(NKNKlog⁡(NK))\mathcal{O}(NK\sqrt{NK}\log(\sqrt{NK}))

#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{String Hashing Template (from the module)}
class HashedString {
  private:
	// change M and B if you want
	static const long long M = 1e9 + 9;
	static const long long B = 9973;
 
	// pow[i] contains B^i % M
	static vector<long long> pow;
 
	// p_hash[i] is the hash of the first i characters of the given string
	vector<long long> p_hash;
 
  public:
	HashedString(const string &s) : p_hash(s.size() + 1) {
		while (pow.size() <= s.size()) { pow.push_back((pow.back() * B) % M); }
 
		p_hash[0] = 0;
		for (int i = 0; i < (int)s.size(); i++) {
			p_hash[i + 1] = ((p_hash[i] * B) % M + s[i]) % M;
		}
	}
 
	long long get_hash(int start, int end) {
		long long raw_val = (p_hash[end + 1] - (p_hash[start] * pow[end - start + 1]));
		return (raw_val % M + M) % M;
	}
};
vector<long long> HashedString::pow = {1};
// EndCodeSnip
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n, k;
		cin >> n >> k;
		vector<string> s(n);
		for (string &i : s) { cin >> i; }
 
		vector<bool> res(n);
		if (n < k) {
			for (int i = 0; i < n; i++) {
				for (int j = i + 1; j < n; j++) {
					int diff_chars = 0;
					for (int x = 0; x < k; x++) { diff_chars += (s[i][x] != s[j][x]); }
					if (diff_chars <= 2) { res[i] = res[j] = true; }
				}
			}
		} else {
			vector<HashedString> hashed;
			for (int i = 0; i < n; i++) { hashed.push_back(HashedString(s[i])); }
 
			for (int i = 0; i < k; i++) {
				for (int j = i + 1; j < k; j++) {
					vector<array<long long, 4>> hashes(n);
					for (int x = 0; x < n; x++) {
						long long hash_1 = hashed[x].get_hash(0, i - 1);
						long long hash_2 = hashed[x].get_hash(i + 1, j - 1);
						long long hash_3 = hashed[x].get_hash(j + 1, k - 1);
						hashes[x] = {hash_1, hash_2, hash_3, x};
					}
 
					sort(begin(hashes), end(hashes));
					for (int x = 1; x < n; x++) {
						bool works = true;
						for (int y = 0; y < 3; y++) {
							works &= hashes[x - 1][y] == hashes[x][y];
						}
						if (works) { res[hashes[x - 1][3]] = res[hashes[x][3]] = true; }
					}
				}
			}
		}
 
		for (int i = 0; i < n; i++) { cout << res[i]; }
		cout << "\n";
	}
}
Fundamentos