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

Key observations

1. What a single operation really does
   Starting at array i we

   • insert an element at the front of Aᵢ,
   • take the last element of Aᵢ and push it to the front of Aᵢ₊_1,
   • …and so on until the last array loses its tail element.

   After k consecutive operations on the same row,

   • the k elements we inserted become the prefix (in the order we inserted them, newest in front);
   • the first m − k items of the array before the first operation slide right and form the suffix;
   • the last k items of that old array disappear – they are exactly the elements forwarded to Aᵢ₊_1.

2. How many operations does one row really need?
   Let

   L = longest  L ≥ 0  s.t.     prefix_L( Aᵢ )   ==   suffix_L( Bᵢ )
   

   (i.e. the longest prefix of the current array that already sits at the right end of the target array).
   Then the minimal number of operations for this row is

   kᵢ = m – L                                        (1)
   

   because we have to get rid of the last kᵢ elements of Aᵢ and insert the kᵢ missing prefix elements of Bᵢ.

   We can find L in O(m) with a standard prefix-function/Z-algorithm:

   text
   S =  Aᵢ  + [0] +  Bᵢ              // 0 is a delimiter not appearing in data
   π = prefix_function(S)
   L = π.back()                      // the very last value

   π.back() is precisely the length of the longest prefix of Aᵢ that appears as a suffix of Bᵢ.

3. Updating the next row without simulating every hop

   Before we start working on row i+1, its content must already include the kᵢ elements that row i has just forwarded. Those elements are the last kᵢ items of Aᵢ before the operations, and they maintain their order.

   text
   tail  = last kᵢ elements of the old Aᵢ
   keep  = first m−kᵢ elements of the current Aᵢ₊_1      (they will slide right)
   
   Aᵢ₊_1  =  tail  •  keep                               (2)

   Because we update one whole row at a time, the total amount of copying over the entire test case is Σ m = n·m ≤ 3·10^5, perfectly within the limit.

4. Why the greedy “row-by-row minimum” is globally optimal

   Every operation costs exactly 1, no matter in which row we perform it. If we did more than the minimum on some row, we would throw away an element that already matched its target suffix. That extra operation can at most save one later operation (because it forwards one element). So the overall sum of operations can never decrease by overspending earlier. Hence the greedy choice (1) is optimal.

Algorithm

text
ans = 0
cur = original arrays A[1…n]                    // vectors of size m each

for i = 1 .. n
    L = longest prefix of cur[i] matching suffix of B[i]   // KMP / Z, O(m)
    k = m - L
    ans += k

    // prepare the (i+1)-st array, if it exists
    if i < n
        tail  = last k elements of cur[i]       // copy, size k
        keep  = first m-k elements of cur[i+1]  // copy, size m-k
        cur[i+1] = tail + keep                  // (2)

    // row i is done; replace it by its target (optional)
    cur[i] = B[i]

output ans

Complexity

• Time: each row is handled once, every element is copied/compared O(1) times ⇒ O(n m) ≤ 3 · 10^5 per test case.
• Memory: we keep the current arrays, total O(n m) integers.

Reference implementation (C++ 17)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;                                                // test cases
    cin >> T;
    const int SEP = 0;                                    // separator (all aᵢⱼ &ge; 1)
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> cur(n, vector<int>(m));
        for (auto &row : cur)
            for (int &x : row) cin >> x;
        vector<vector<int>> B(n, vector<int>(m));
        for (auto &row : B)
            for (int &x : row) cin >> x;

        long long ans = 0;

        auto pref_func = [](const vector<int>& s) {
            vector<int> pi(s.size());
            for (size_t i = 1; i < s.size(); ++i) {
                int j = pi[i - 1];
                while (j > 0 && s[i] != s[j]) j = pi[j - 1];
                if (s[i] == s[j]) ++j;
                pi[i] = j;
            }
            return pi;
        };

        for (int i = 0; i < n; ++i) {
            /* ---- 1. longest overlap L ---- */
            vector<int> comb;
            comb.reserve(2 * m + 1);
            comb.insert(comb.end(), cur[i].begin(), cur[i].end());
            comb.push_back(SEP);
            comb.insert(comb.end(), B[i].begin(), B[i].end());

            int L = pref_func(comb).back();               // overlap length
            int k = m - L;
            ans += k;

            /* ---- 2. forward the tail to the next row ---- */
            if (i + 1 < n && k > 0) {
                const auto tailBeg = cur[i].end() - k;
                vector<int> next;
                next.reserve(m);
                next.insert(next.end(), tailBeg, cur[i].end());          // tail
                next.insert(next.end(), cur[i + 1].begin(),
                             cur[i + 1].begin() + (m - k));              // keep
                cur[i + 1].swap(next);
            }

            /* ---- 3. row i reaches its final form (not needed later) --- */
            cur[i].swap(B[i]);
        }
        cout << ans << '\n';
    }
    return 0;
}

The code follows exactly the steps explained above and runs comfortably within the 3 s / 256 MB limits for the whole easy version.