Skip to Content
CTRL K

Field Day

Pista 1

Nótese que la cota de CC es ridículamente pequeña. ¿Qué complejidad temporal podría implicar esto?

Respuesta a la pista 1

O(2C⋅C)\mathcal{O}(2^C \cdot C) o similar. ¡Esto debería inspirarte a usar máscaras de bits!

Solución

Análisis oficial (C++, Java y Python) 

Explicación

Por el enunciado, queremos hallar el par de equipos con la diferencia máxima posible. Sin embargo, dado que fijamos el equipo para el que queremos hallar la diferencia máxima, podemos reformular el enunciado como hallar la diferencia mínima para el inverso de ese equipo.

Por ejemplo, el inverso de HGHH es GHGG, el de GGGG es HHHH, el de HGHG es GHGH, etc.

Como C≤18C \leq 18, podemos iterar sobre todos los equipos posibles. En lugar de calcular la distancia entre un par de equipos, imaginemos cada una de estas posiciones distintas como una operación de edición singular; la máscara final es una amalgama de una serie de ediciones.

Luego, para cada una de las 2C2^C máscaras posibles, podemos calcular la diferencia de editar cada uno de sus CC bits. Si inicializamos la distancia de todos los equipos de FJ como 00 y la de todos los demás equipos como un número arbitrariamente grande, podemos calcular la distancia mínima de cada máscara en tiempo O(2C⋅C)\mathcal{O}(2^C \cdot C).

Nuestra respuesta sería entonces C−distinv(teami)C - \texttt{dist}_{\text{inv}(\texttt{team}_i)} donde teami\texttt{team}_i es nuestro equipo actual, inv(x)\text{inv}(x) devuelve el inverso de xx, y distmask\texttt{dist}_{\texttt{mask}} nos da la distancia de edición mínima desde uno de los equipos de FJ.

También podemos calcular esta distancia mínima con una BFS multi-fuente con la misma complejidad temporal.

Implementación

Complejidad temporal: O(2C⋅C+NC)\mathcal{O}(2^C \cdot C + NC)

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int c, n;
	cin >> c >> n;
 
	vector<int> teams(n);
	vector<int> min_edits(1 << c, INT32_MAX);
 
	for (int i = 0; i < n; i++) {
		string breeds;
		cin >> breeds;
 
		// convertir equipos a máscaras de bits
		for (int j = 0; j < c; j++) {
			if (breeds[j] == 'G') { teams[i] += 1 << (c - j - 1); }
		}
 
		min_edits[teams[i]] = 0;
	}
 
	for (int edit = 0; edit < c; edit++) {
		for (int mask = 0; mask < (1 << c); mask++) {
			// mask ^ (1 << edit) invierte el bit edit-ésimo de mask
			if (min_edits[mask] != INT32_MAX) {
				min_edits[mask ^ (1 << edit)] =
				    min(min_edits[mask ^ (1 << edit)], min_edits[mask] + 1);
			}
		}
	}
 
	for (int i = 0; i < n; i++) {
		// teams[i] ^ ((1 << c) - 1) invierte todos los bits de teams[i]
		cout << c - min_edits[teams[i] ^ ((1 << c) - 1)] << endl;
	}
}
import java.io.*;
import java.util.*;
 
public class FieldDay {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int c = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());
 
		int[] teams = new int[n];
		int[] minEdits = new int[1 << c];
		Arrays.fill(minEdits, Integer.MAX_VALUE);
 
		for (int i = 0; i < n; i++) {
			String breeds = br.readLine();
 
			// convertir equipos a máscaras de bits
			for (int j = 0; j < c; j++) {
				if (breeds.charAt(j) == 'G') { teams[i] += 1 << (c - j - 1); }
			}
 
			minEdits[teams[i]] = 0;
		}
 
		for (int edit = 0; edit < c; edit++) {
			for (int mask = 0; mask < (1 << c); mask++) {
				// mask ^ (1 << edit) invierte el bit edit-ésimo de mask
				if (minEdits[mask] != Integer.MAX_VALUE) {
					minEdits[mask ^ (1 << edit)] =
					    Math.min(minEdits[mask ^ (1 << edit)], minEdits[mask] + 1);
				}
			}
		}
 
		for (int i = 0; i < n; i++) {
			// teams[i] ^ ((1 << c) - 1) invierte todos los bits de teams[i]
			System.out.println(c - minEdits[teams[i] ^ ((1 << c) - 1)]);
		}
	}
}
c, n = map(int, input().split())
teams = [0] * n
min_edits = [float("inf")] * (1 << c)
 
for i in range(n):
	breeds = input()
 
	# convertir equipos a máscaras de bits
	for j in range(c):
		if breeds[j] == "G":
			teams[i] += 1 << (c - j - 1)
 
	min_edits[teams[i]] = 0
 
 
for edit in range(c):
	for mask in range(1 << c):
		if min_edits[mask] != float("inf"):
			# mask ^ (1 << edit) invierte el bit edit-ésimo de mask
			min_edits[mask ^ (1 << edit)] = min(
				min_edits[mask ^ (1 << edit)], min_edits[mask] + 1
			)
 
for i in range(n):
	# teams[i] ^ ((1 << c) - 1) invierte todos los bits de teams[i]
	print(c - min_edits[teams[i] ^ ((1 << c) - 1)])
Fundamentos