This is the easy version of the problem. The differences between the two versions are…
- User
This is the easy version of the problem. The differences between the two versions are the constraints on all the variables. You can make hacks only if both versions of the problem are solved.
Tsovak and Narek are playing a game. They have an array a and a matrix b of integers with n rows and m columns, numbered from 1. The cell in the i-th row and the j-th column is (i,j)
.
They are looking for the elements of a in turns; Tsovak starts first. Each time a player looks for a cell in the matrix containing the current element of a (Tsovak looks for the first, then Narek looks for the second, etc.). Let's say a player has chosen the cell (r,c). The next player has to choose his cell in the submatrix starting at (r+1,c+1) and ending in (n,m) (the submatrix can be empty if r=n or c=m
). If a player cannot find such a cell (or the remaining submatrix is empty) or the array ends (the previous player has chosen the last element), then he loses.
Your task is to determine the winner if the players play optimally. Input
The first line of the input contains t (1≤t≤300
) – the number of test cases.
The first line of each test case contains three integers l , n, and m (1≤l,n,m≤300
) – the size of the array and the sizes of the matrix.
The second line contains l integers a1,a2,a3,…al (1≤ai≤min(7,n⋅m)) – the elements of the array a
.
The i -th of the last n lines contains m integers bi,1,bi,2,bi,3,…bi,m (1≤bi,j≤min(7,n⋅m)) – representing the i
-th row of the matrix.
It is guaranteed that the sum of n⋅m over all test cases does not exceed 105
.
It is guaranteed that the sum of l over all test cases does not exceed 300
. Output
You should output t lines, the i-th of them containing a character representing the answer of the i
-th test case: "T" if Tsovak wins or "N", otherwise (without quotes). Example Input Copy
3 2 2 3 1 2 1 3 5 4 5 2 2 2 4 1 2 1 1 3 2 4 2 5 1 2 4 2 1 2 3 4 5 5 5 5 5 5
Output Copy
N T N
Note
In the first example, Tsovak starts by looking for 1 . There is only one occurrence of 1 at (1,1), so he chooses it. Then Narek needs to look for 2 in the submatrix of (2,2), which consists of just the last two elements: 5 and 2. He chooses 2
, and then Tsovak loses since the array has ended.
In the second example, Tsovak needs to choose 1 . There is a 1 at the cell (n,m), so he chooses that cell. Then, since the submatrix of (n+1,m+1) is empty, Narek cannot find 2, so he loses. in c++
- Assistant
To solve the problem of determining the winner in the game between Tsovak and Narek, we need a strategic approach involving dynamic programming (DP). Given the constraints and the alternating nature of the game, this approach will help us efficiently determine the outcome for each test case.
Step-by-Step Reasoning:
-
Understanding the Game:
- Tsovak and Narek alternate turns to select cells from a matrix that match the current element from an array
a. - The selection is constrained by the submatrix region, which restricts future choices.
- The game is lost by the player who cannot make a valid selection or when the array elements are exhausted.
- Tsovak and Narek alternate turns to select cells from a matrix that match the current element from an array
-
Dynamic Programming Approach:
- We define a DP state
memo[k][r][c]indicating whether the current player can force a win starting from elementa[k]and submatrix starting at(r, c). - For each test case:
- Initialize
memo[k][r][c]for all possible states. - Iterate backwards from
k = ldown to1, updating the DP table based on possible moves and constraints. - Use prefix sums to efficiently calculate whether there exists a cell that can lead to a win.
- Initialize
- The base case is when
k = l + 1, where no moves are left, and the player loses.
- We define a DP state
-
Optimizing the Solution:
- Given the constraints (
l, n, m ≤ 300), we ensure that our solution runs efficiently by optimally building and querying the DP table. - We use two 2D arrays (
current_memoandnext_memo) to store states for the current and next steps, reducing memory usage and improving cache performance.
- Given the constraints (
-
Edge Cases:
- If
l = 1, Tsovak should select the only possible cell. - If no cells match at any step, the player to make the move loses.
- If
-
Implementation:
- The solution is implemented in C++ with careful handling of input, DP state transitions, and edge conditions.
- The use of prefix sums allows for efficient range queries, which is crucial given the problem's constraints.
Final C++ Implementation:
#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while(t--){ int l, n, m; cin >> l >> n >> m; vector<int> a(l); for(auto &x: a) cin >> x; // Read matrix vector<vector<int>> b(n+1, vector<int>(m+1)); for(int r=1;r<=n;r++) { for(int c=1;c<=m;c++) { cin >> b[r][c]; } } // Build L[k] vector<vector<pair<int,int>>> L(l+1, vector<pair<int,int>>()); for(int r=1;r<=n;r++) { for(int c=1;c<=m;c++) { if(b[r][c] >=1 && b[r][c]<=7){ for(int k=1;k<=l;k++) { if(b[r][c] == a[k-1]){ L[k].emplace_back(r, c); } } } } } // Initialize next_memo as False for k=l+1 // Use two 2D arrays: next_memo and current_memo // Initialize next_memo to False vector<vector<bool>> next_memo(n+2, vector<bool>(m+2, false)); // Iterate k from l downto1 for(int k=l; k>=1; k--){ // Initialize mark[r][c] =1 if choosing (r,c) leads to next player losing // Only for cells in L[k] vector<vector<int>> mark(n+1, vector<int>(m+1, 0)); for(auto &[r, c] : L[k]){ if(r +1 > n || c +1 > m){ mark[r][c] =1; } else{ if(!next_memo[r+1][c+1]){ mark[r][c] =1; } } } // Build prefix sum vector<vector<int>> pre(n+1, vector<int>(m+1, 0)); for(int r=1;r<=n;r++){ int row_sum =0; for(int c=1;c<=m;c++){ row_sum += mark[r][c]; pre[r][c] = pre[r-1][c] + row_sum; } } // Build current_memo based on prefix sum vector<vector<bool>> current_memo(n+1, vector<bool>(m+1, false)); for(int r=1;r<=n;r++){ for(int c=1;c<=m;c++){ // Sum from (r,c) to (n,m) int total = pre[n][m] - pre[r-1][m] - pre[n][c-1] + pre[r-1][c-1]; if(total >0){ current_memo[r][c] = true; } else{ current_memo[r][c] = false; } } } // Set next_memo to current_memo for next iteration next_memo = move(current_memo); } // After all k, check memo[1][1] if(next_memo[1][1]){ cout << 'T'; } else{ cout << 'N'; } } cout << '\n'; }This implementation efficiently determines the winner for each test case based on the dynamic programming approach described above.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.