We can do this in $\mathcal{O}(1)$ time. Define $\texttt{beat}[i][j]$ to be $\texttt{true}$ if symbol $i$ wins against symbol $j$, and false otherwise. If Bessie reveals symbols $a$ and $b$, and Elsie reveals symbols $x$ and $y$, then Bessie is guaranteed to win if $a$ beats both $x$ and $y$ (i.e. $\texttt{beat[a][x] and beat[a][y]}$) or if $b$ beats both $x$ and $y$ (i.e. $\texttt{beat[b][x] and beat[b][y]}$).
For subtask 1, we can use brute-force. For every game, loop through every combination of symbols Bessie can play, and for each one, check to see if Bessie can guarantee a win. This runs in $\mathcal{O}(N^2M)$.
N, M = map(int, input().split()) data = [input() for _ in range(N)] beat = [[0] * N for _ in range(N)] for i in range(N): for j in range(i): if data[i][j] != "D": if data[i][j] == "W": beat[i][j] = 1 else: beat[j][i] = 1 for _ in range(M): x, y = map(lambda x: int(x) - 1, input().split()) ans = 0 for a in range(N): for b in range(N): ans += (beat[a][x] and beat[a][y]) or (beat[b][x] and beat[b][y]) print(ans)
In C++:
#include <iostream> #include <vector> #include <string> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<string> data(N); for (int i = 0; i < N; i++) { cin >> data[i]; } vector<vector<int>> beat(N, vector<int>(N, 0)); for (int i = 0; i < N; i++) { for (int j = 0; j < i; j++) { if (data[i][j] != 'D') { if (data[i][j] == 'W') { beat[i][j] = 1; } else { beat[j][i] = 1; } } } } for (int q = 0; q < M; q++) { int x, y; cin >> x >> y; x--; y--; long long ans = 0; for (int a = 0; a < N; a++) { for (int b = 0; b < N; b++) { if ((beat[a][x] && beat[a][y]) || (beat[b][x] && beat[b][y])) { ans++; } } } cout << ans << "\n"; } return 0; }
For subtask 2, this is too slow. Since $N$ and $M$ are $3000$, we can guess that the solution's time complexity might be something like $\mathcal{O}(NM)$. Let's see if we can get rid of one of the for loops.
To achieve our desired complexity of $\mathcal{O}(NM)$, we can loop through all $N$ symbols for every game. Consider a single game between Bessie and Elsie. Let's loop through the symbol Bessie reveals in her left hoof, $a$. We want to answer the following question in $\mathcal{O}(1)$: Which symbols $b$ can Bessie reveal in her right foot that will guarantee a win against Elsie?
Let's say Elsie plays symbols $x$ and $y$. There are two cases to consider.
Case 1: If $a$ beats both $x$ and $y$, i.e. $\texttt{beat[a][x] and beat[a][y]}$, then Bessie can reveal any symbol $b$ in her right hoof and she will guarantee a win against Elsie by playing symbol $a$. In this case, the answer to our question is $N$.
Case 2: If $a$ is unable to beat both $x$ and $y$, then Bessie must reveal a symbol $b$ in her right hoof that can beat both $x$ and $y$ in order to guarantee a win against Elsie. In this case, the answer to our question is the number of symbols that beat both $x$ and $y$.
Case 1 can be determined in $\mathcal{O}(1)$ time, but Case 2 requires $\mathcal{O}(N)$ time to compute since we have to loop through all $N$ symbols to count the number of symbols that beat both $x$ and $y$. If we have to do this for every symbol $a$ that is unable to beat both $x$ and $y$, doesn't this mean our final time complexity is $\mathcal{O}(N^2M)$?
As it turns out, we don't have to do this for every symbol $a$. Instead, we only have to do this once per game, and then we can reuse our computed result for all symbols $a$. So, for every game, we need to do an $\mathcal{O}(N)$ precomputation to count the number of symbols that beat both $x$ and $y$, then we have to loop through all symbols $a$ that Bessie can reveal in her left hoof, which is $\mathcal{O}(N)$. Our final time complexity is therefore $\mathcal{O}(M \cdot (N + N)) = \mathcal{O}(NM)$.
N, M = map(int, input().split()) data = [input() for _ in range(N)] beat = [[0] * N for _ in range(N)] for i in range(N): for j in range(i): if data[i][j] != "D": if data[i][j] == "W": beat[i][j] = 1 else: beat[j][i] = 1 for _ in range(M): x, y = map(lambda x: int(x) - 1, input().split()) # Number of symbols b that can beat both x and y winning = 0 for b in range(N): winning += beat[b][x] and beat[b][y] ans = 0 for a in range(N): if beat[a][x] and beat[a][y]: # Case 1: The symbol in Bessie's left hoof beats both symbols x and y # Bessie can play any symbol in her right hoof ans += N else: # Case 2: The symbol in Bessie's left hoof cannot beat both symbols x and y # Bessie must play a symbol that can beat both x and y in her right hoof ans += winning print(ans)
In C++:
#include <iostream> #include <vector> #include <string> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<string> data(N); for (int i = 0; i < N; i++) { cin >> data[i]; } vector<vector<int>> beat(N, vector<int>(N, 0)); for (int i = 0; i < N; i++) { for (int j = 0; j < i; j++) { if (data[i][j] != 'D') { if (data[i][j] == 'W') beat[i][j] = 1; else beat[j][i] = 1; } } } while (M--) { int x, y; cin >> x >> y; x--; y--; // Number of symbols b that can beat both x and y int winning = 0; for (int b = 0; b < N; b++) { if (beat[b][x] && beat[b][y]) winning++; } int ans = 0; for (int a = 0; a < N; a++) { if (beat[a][x] && beat[a][y]) { // Case 1: The symbol in Bessie's left hoof beats both symbols x and y // Bessie can play any symbol in her right hoof ans += N; } else { // Case 2: The symbol in Bessie's left hoof cannot beat both symbols x and y // Bessie must play a symbol that can beat both x and y in her right hoof ans += winning; } } cout << ans << "\n"; } return 0; }
You can also solve this problem with a bit of math. For every game, let $w$ be the number of "winning" symbols -- i.e. the number of symbols that can beat both symbols Elsie reveals, $x$ and $y$. In the code above, $w = \texttt{winning}$.
It turns out that the number of pairs of symbols $(a, b)$ that Bessie can reveal to guarantee a win is equal to $N^2 - (N-w)^2$. We arrive at this solution via complementary counting: We'll count the number of pairs that make it impossible to guarantee Bessie a win and subtract that from the total number of pairs Bessie can play. The result is the number of pairs Bessie can play that does guarantee a win.
How many pairs make it impossible to guarantee a win for Bessie? Well, neither symbol $a$ nor $b$ can be a "winning" symbol, otherwise Bessie could just play that to guarantee a win. If there are $w$ winning symbols and $N$ symbols total, the number of non-winning symbols is $N - w$. $a$ and $b$ must both be a non-winning symbol, so the number of pairs of symbols $(a, b)$ that make it impossible to guarantee a win for Bessie is $(N-w)^2$. Finally, the total number of pairs Bessie can play is $N^2$ (since there are $N$ options for each of the left / right hooves), so our final answer is $N^2 - (N-w)^2$.
Another way you could have arrived at this formula is to count the number of symbols that satisfy Case 1 and Case 2. Case 1, which is when $a$ beats both $x$ and $y$, is precisely the number of winning symbols. Every symbol is either Case 1 or Case 2, so if there are $w$ winning symbols, then there are $w$ symbols in Case 1 and $N - w$ symbols in Case 2.
For every symbol in Case 1, we add $N$ to our answer, so we get $N \cdot w$ in total. For every symbol in Case 2, we add $w$ to our answer, so we get $(N - w) \cdot w$ in total.
Summing the two, we get $Nw + (N - w) \cdot w = 2Nw - w^2 = N^2 - N^2 + 2Nw - w^2 = N^2 - (N^2 - 2Nw + w^2) = N^2 - (N - w)^2$.
N, M = map(int, input().split()) data = [input() for _ in range(N)] beat = [[0] * N for _ in range(N)] for i in range(N): for j in range(i): if data[i][j] != "D": if data[i][j] == "W": beat[i][j] = 1 else: beat[j][i] = 1 for _ in range(M): x, y = map(lambda x: int(x) - 1, input().split()) # Number of symbols b that can beat both x and y winning = 0 for b in range(N): winning += beat[b][x] and beat[b][y] total_playable_pairs = N ** 2 losing_pairs = (N-winning) ** 2 print(total_playable_pairs - losing_pairs)
In C++:
#include <iostream> #include <vector> #include <string> using namespace std; int main() { int N, M; cin >> N >> M; vector<string> data(N); for (int i = 0; i < N; i++) { cin >> data[i]; } vector<vector<int>> beat(N, vector<int>(N, 0)); for (int i = 0; i < N; i++) { for (int j = 0; j < i; j++) { if (data[i][j] != 'D') { if (data[i][j] == 'W') beat[i][j] = 1; else beat[j][i] = 1; } } } while (M--) { int x, y; cin >> x >> y; x--; y--; // Number of symbols b that can beat both x and y int winning = 0; for (int b = 0; b < N; b++) { if (beat[b][x] && beat[b][y]) winning++; } int total_playable_pairs = N * N; int losing_pairs = (N - winning) * (N - winning); cout << total_playable_pairs - losing_pairs << "\n"; } return 0; }