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). solve using c++
- Assistant
The problem can be approached as a game where the players pick numbers according to the sequence in the array
afrom the positions in the matrixbwhile moving to lower right, with the positions strictly increasing in both row and column indices. The main idea is to use dynamic programming along with memoization to determine the winner.First, flatten the matrix into a sequence
Bin lexicographical order of the positions (row and column). The players need to pick numbers from this sequenceBaccording to the arraya. Each move must advance to a higher position inB, fulfilling the constraints.Here's how you can proceed:
- Map the positions where each number (from 1 to 7) occurs in the matrix
b. - For each index
pinB, precompute the next occurrence of each numbernumgreater thanp. This will be stored in thenextNumarray. - Implement a recursive function
f(k, p)that determines whether the player can win starting from positionpin the sequenceBand thek-th element in the arraya.- If the current element in
acannot be found after positionp, the player loses. - Otherwise, the function checks if the opponent loses in the next move. If the opponent loses, the current player wins.
- If the current element in
- Use memoization to store the results of
f(k, p)to avoid redundant calculations. - The initial call is
f(1, 0), and you can determine the winner based on its return value.
Here's the C++ code reflecting the above logic:
#include <iostream> #include <vector> #include <map> #include <cstring> #include <algorithm> using namespace std; const int MAX_L = 310; const int MAX_S = 100010; int t; int l, n, m; int a[MAX_L]; int B[MAX_S]; vector<int> pos[8]; int nextNum[MAX_S][8]; int s; map<pair<int, int>, bool> memo; bool f(int k, int p, int l, int s) { if (k > l) return false; // No more moves, the player loses int key = k * MAX_S + p; if (memo.count({k, p})) return memo[{k, p}]; int num = a[k]; int t = nextNum[p][num]; while (t != -1 && t < s) { if (!f(k + 1, t + 1, l, s)) { // Opponent loses memo[{k, p}] = true; return true; } t = nextNum[t + 1][num]; } memo[{k, p}] = false; return false; } int main() { cin >> t; while (t--) { cin >> l >> n >> m; for (int i = 1; i <= l; ++i) { cin >> a[i]; } s = 0; memo.clear(); for (int i = 1; i <= 7; ++i) pos[i].clear(); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { int num; cin >> num; B[++s] = num; pos[num].push_back(s); } } // Precompute nextNum for (int num = 1; num <= 7; ++num) { int lastPos = -1; nextNum[s][num] = -1; for (int i = s - 1; i >= 0; --i) { if (B[i + 1] == num) { lastPos = i + 1; } nextNum[i][num] = lastPos; } } bool res = f(1, 0, l, s); cout << (res ? 'T' : 'N') << '\n'; } return 0; } - Map the positions where each number (from 1 to 7) occurs in the matrix