Hoof Paper Scissors Minus One

Explicación

Para resolver esto, hay que revisar cuántos pares posibles de gestos existen en los que uno de los dos gestos puede vencer a ambos gestos de Elsie, el de la izquierda y el de la derecha.

Casos de prueba 1 a 6

Esto se puede resolver creando primero un arreglo 2D que indique si el gesto $i$ puede ser vencido por el gesto $j$ , derivado de la «pirámide de victorias» dada en la entrada.

C++Python


vector<vector<bool>> beatenBy(n, vector<bool>(n));
for (int i = 0; i < n; i++) {
	for (int j = 0; j <= i; j++) {
		char state;
		cin >> state;
		if (state == 'L') {
			beatenBy[i][j] = true;
		} else if (state == 'W') {
			beatenBy[j][i] = true;
		}
	}
}


n, m = map(int, input().split())
beats = [[False for i in range(n)] for j in range(n)]
for i in range(n):
	state = input()
	for j in range(len(a)):
		if state[j] == "W":
			beats[i][j] = True
		elif state[j] == "L":
			beats[j][i] = True

Con esto, una fuerza bruta de $\mathcal{O}(N^2)$ por cada partida funciona. Aquí hay un ejemplo:

C++Python


for (int myL = 0; myL < n; myL++) {
	for (int myR = 0; myR < n; myR++) {
		if ((beatenBy[l][myL] && beatenBy[r][myL]) ||
		    (beatenBy[l][myR] && beatenBy[r][myR]))
			possible++;
	}
}


for myL in range(n):
	for myR in range(n):
		if (beats[myL][l] and beats[myL][r]) or (beatsy[myR][l] and beats[myR][r]):
			possible += 1

Casos de prueba 7 a 12

Para optimizar el cálculo por partida de $\mathcal{O}(N^2)$ a $\mathcal{O}(N)$ , hace falta una serie de optimizaciones que, al final, se convierten en una sola fórmula.

Optimización 1:

Se puede notar que si myL ya es capaz de vencer tanto a l como a r, no hace falta probar todos los myR.

C++Python


for (int myL = 0; myL < n; myL++) {
	if (beatenBy[l][myL] && beatenBy[r][myL]) {
		possible += n;
	} else {
		for (int myR = 0; myR < n; myR++) {
			if (beatenBy[l][myR] && beatenBy[r][myR]) possible++;
		}
	}
}


for myL in range(n):
	if beats[myL][l] and beats[myL][r]:
		possible += n
	else:
		for myR in range(n):
			if beats[myR][l] and beats[myR][r]:
				possible += 1

Optimización 2:

Si $x$ es cuántos gestos de los $N$ pueden vencer tanto a l como a r de Elsie, entonces podemos asumir que esta comprobación:

C++


for (int myL = 0; myL < n; myL++) {
	if (beatenBy[l][myL] && beatenBy[r][myL]) possible += n;

es equivalente a


possible += x * n;

y la cláusula else se ejecuta $n-x$ veces, y suma $x$ posibilidades.


possible += x * (n - x)

Con esto, se obtiene que la fórmula de los pares ganadores es $xn + x(n-x)$ . Implementar directamente esta fórmula permite resolver cada partida en $\mathcal{O}(N)$ .

Nótese que se puede derivar una fórmula equivalente basada en conteo:


2 * x * n - x ** 2

Implementación

Complejidad temporal: $\mathcal{O}(N^2+MN)$

C++Python


#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	int n, m;
	cin >> n >> m;
 
	// Read the win triangle
	vector<vector<bool>> beatenBy(n, vector<bool>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			char state;
			cin >> state;
			if (state == 'L') {
				beatenBy[i][j] = true;
			} else if (state == 'W') {
				beatenBy[j][i] = true;
			}
		}
	}
 
	// Read Elsie's moves
	for (int i = 0; i < m; i++) {
		int l, r;
		cin >> l >> r;
		l--;
		r--;
 
		int x = 0;
		for (int a = 0; a < n; a++) {
			if (beatenBy[l][a] && beatenBy[r][a]) x++;
		}
 
		int possible = x * n + x * (n - x);  // equation is explained above
		cout << possible << "\n";
	}
}


n, m = map(int, input().split())
beats = [[False for i in range(n)] for j in range(n)]
 
for i in range(n):
	state = input()
 
	for j in range(len(state)):
		if state[j] == "W":
			beats[i][j] = True
		elif state[j] == "L":
			beats[j][i] = True
 
for _ in range(m):
	l, r = map(int, input().split())
	x = 0
 
	for my_symbol in range(n):
		if beats[my_symbol][l - 1] and beats[my_symbol][r - 1]:
			x += 1
 
	print(2 * x * n - x**2)  # this is also equivalent to x*n + x*(n-x)