logoChat01.ai

E1. Stop Gaming (Easy Version) time limit per test...

Creado el: 3 de mayo de 2025

Respondido usando O4 Mini High por Chat01

Pregunta

E1. Stop Gaming (Easy Version)
time limit per test3 seconds
memory limit per test256 megabytes
This is the easy version of the problem. The difference between the versions is that in this version you only need to find the minimum number of operations. You can hack only if you solved all versions of this problem.

You are given n
arrays, each of which has a length of m
. Let the j
-th element of the i
-th array be denoted as ai,j
. It is guaranteed that all ai,j
are pairwise distinct. In one operation, you can do the following:

Choose some integer i
(1≤i≤n
) and an integer x
(1≤x≤2⋅n⋅m
).
For all integers k
from i
to n
in increasing order, do the following:
Add the element x
to the beginning of the k
-th array.

Assign x
the value of the last element in the k
-th array.

Remove the last element from the k
-th array.
In other words, you can insert an element at the beginning of any array, after which all elements in this and all following arrays are shifted by one to the right. The last element of the last array is removed.

You are also given a description of the arrays that need to be obtained after all operations. That is, after performing the operations, the j
-th element of the i
-th array should be equal to bi,j
. It is guaranteed that all bi,j
are pairwise distinct.

Determine the minimum number of operations that need to be performed to obtain the desired arrays.

Input
Each test consists of multiple test cases. The first line contains a single integer t
(1≤t≤104
) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers n
and m
(1≤n,m≤3⋅105
) — the number of arrays and the number of elements in each array.

The i
-th of the following n
lines contains m
integers ai,1,ai,2,…,ai,m
(1≤ai,j≤2⋅n⋅m
) — the elements of the i
-th original array. It is guaranteed that all ai,j
are pairwise distinct.

The i
-th of the following n
lines contains m
integers bi,1,bi,2,…,bi,m
(1≤bi,j≤2⋅n⋅m
) — the elements of the i
-th final array. It is guaranteed that all bi,j
are pairwise distinct.

It is guaranteed that the sum of n⋅m
over all test cases does not exceed 3⋅105
.

Output
For each test case, output a single integer — the minimum number of operations that need to be performed.

Example

Input
4
2 2
2 6
3 4
1 2
7 8
1 5
5 4 1 2 3
5 4 3 2 1
3 3
1 2 3
4 5 6
7 8 9
11 1 2
12 3 4
13 5 6
4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 1 2 3
4 18 5 6
7 19 8 20
9 21 22 10

Output
3
5
3
6

Note
In the first test case, the following sequence of 3
operations is suitable:

Apply the operation to the first array with x=1
. Then the element 1
will be added to the beginning of the first array, and the value of x
will become 6
. The last element will be removed, and the first array will look like [1,2]
. Next, the element x
is added to the beginning of the second array, and the value of x
becomes 4
. The last element of the second array is removed, and both arrays look like [1,2]
and [6,3]
respectively after the first operation.
Apply the operation to the second array with x=8
. Then the first array remains unchanged, and both arrays will look like [1,2]
and [8,6]
respectively.
Apply the operation to the second array with x=7
, then both arrays will have the required appearance [1,2]
and [7,8]
respectively.
In the second test case, the desired array can only be achieved in 5
operations.

In the third test case, the following sequence of 3
operations is suitable:

Apply the operation with x=11
to the first array.
Apply the operation with x=12
to the second array.
Apply the operation with x=13
to the third array.

→ Problem tags brute force, constructive algorithms, greedy, hashing, strings, *2500

Hint 1 To minimize the number of operations, it is necessary to leave as many elements as possible in the original array. What are these elements?

Hint 2 These elements must form the initial array prefix and the final array subsequence.

Hint 3 What other condition needs to be imposed on the prefix so that additions can be used to obtain the final array?

Pensamiento

undefined

Pensamiento

Implementing the matching logic

If the element fails at position i, we compute p using the block index. Then the answer is either n - p + 1 or n - i + 1. The approach finds the largest feasible prefix and computes the answer based on that. If the match fails at i, we return either n - (p - 1) or n - i + 1. The goal is to implement this logic in a simple form, using these steps to determine the appropriate result.

Optimizing the matching conditions

At failure index i, the position p is computed from the block, and we check if p + (p + m - i) > pos[a[p]]. A simpler approach is to define the answer as N - L, where L is the largest feasible prefix of A. The key is defining f(i) = mat_i - i and ensuring that each element's position in B is greater than or equal to its index in A, with f(i) being non-decreasing. This guarantees the feasibility of the element mappings.

Feasibility conditions for matching

For a prefix of length L, elements need to follow the condition f(1) ≤ f(2) ≤ ... ≤ f(L) to be feasible. That is, the number of shifts at index i must be non-decreasing. If f(i) increases, then within the same block, the shift at i must be feasible, meaning mat_i should be greater than or equal to the end of the block. The result is answer = N - L, with edge cases when all elements are matched or one isn't matched, causing a failure.

Choosing between drop options

Let me think through this. The goal is minimizing the operations. When the code seems to pick between two options, N-p+1 and N-i+1, the key difference is how far they need to preserve the prefix of the block. Sometimes it makes sense to pick the larger answer, like N-p+1 if something about preserving the prefix up to p-1 isn’t feasible. But in most cases, they’ll go with the smaller number of operations, N-i+1, since it leads to fewer moves. It's about evaluating where the failure happens and whether preserving the initial part of the block works.

Thought for 2m 26s

Respuesta

To solve the easy version, we first “flatten” all n × m arrays into one sequence of length N = n · m, by listing row 1, then row 2, …, row n. Call these A[1…N] (the initial) and B[1…N] (the target). All values are distinct, so we build a map

cpp
pos[v] = j    // if B[j] == v, otherwise pos[v] = 0

in O(N).

We want to keep as large a prefix of A as possible “untouched” and only perform the remaining K = N–L operations to remove the rest and insert the needed values. One can show (via tracking how many front-insertions affect each position and where you must “cross” a block boundary of size m) that a prefix A[1…L] is feasible if and only if, when we write

mat[i] = pos[A[i]],   d[i] = mat[i] – i,

then for i from 1…L:

  1. Existence: mat[i] > 0.
  2. Monotonicity: d[i] ≥ d[i–1].
  3. Block-crossing: If d[i] > d[i–1], then the previous element A[i–1] must have landed at the end of its m‐block in B:
pos[A[i–1]] ≥ block_end(i–1)   where   block_end(k) = ((k–1)/m + 1)*m.

If any of these fail at position i, you stop:

  • If it fails only because of (1) or (2), you can still preserve A[1…i–1];
  • If it fails because of (3), you must drop back to the start of that block, i.e. preserve A[1…p–1] where
p = ((i–1)/m)*m + 1

is the first index of A’s block containing i.

In either case, once you determine the maximum feasible prefix length L, the answer is simply

K = N – L.

This runs in O(N) per test, easily handling ∑(n·m) ≤ 3·10^5.

cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> n >> m;
        int N = n * m;
        vector<int> A(N+1), B(N+1);
        for(int i = 1; i <= N; i++){
            cin >> A[i];
        }
        for(int i = 1; i <= N; i++){
            cin >> B[i];
        }
        // build position map for B
        vector<int> pos(2*N + 2, 0);
        for(int i = 1; i <= N; i++){
            pos[B[i]] = i;
        }
        int L = 0;
        int prev_d = 0;
        for(int i = 1; i <= N; i++){
            int x = A[i];
            int mat = pos[x];
            if(mat == 0){
                // unmatched: can only preserve up to i-1
                L = i - 1;
                break;
            }
            int d = mat - i;
            if(i == 1){
                prev_d = d;
                L = 1;
            }
            else{
                if(d < prev_d){
                    // monotonicity failure
                    L = i - 1;
                    break;
                }
                if(d > prev_d){
                    // need to cross block boundary:
                    // check if A[i-1] landed at its block's end
                    int prev = A[i-1];
                    int mat_prev = pos[prev];
                    int bel_prev = (i-2)/m + 1;
                    int block_end_prev = bel_prev * m;
                    if(mat_prev < block_end_prev){
                        // block-crossing failure: drop back to start of this block
                        int bel_curr = (i-1)/m + 1;
                        int p = (bel_curr - 1)*m + 1;
                        L = p - 1;
                        break;
                    }
                }
                prev_d = d;
                L = i;
            }
        }
        // if we never broke, L might be set to N already
        cout << (N - L) << "\n";
    }
    return 0;
}

Explanation of key steps

  • We flatten and map positions in B in O(N).
  • We walk i = 1…N, tracking d[i] = pos[A[i]] – i. Intuitively, d[i] is how many insertions have to happen before A[i] to shift it into place. These shifts can only increase as i grows, giving the monotonicity check.
  • Whenever d[i] strictly increases, we must have “crossed” the end of exactly one m‐sized block in the flattened array; if A[i–1] didn’t land at the end of its block in B, that crossing is impossible, so we must abandon preserving anything inside that block, hence reset L to just before the block began.
  • Otherwise, we keep extending the preserved prefix. Finally, every unpreserved element requires exactly one operation (a pop at the end of the cascade), so the minimum number of operations is N – L.

Compartir este Q&A