Overview

This problem asks you to determine whether you can transform array \(A\) into exactly array \(B\) by repeatedly applying an operation that adds +1 to a contiguous segment of length \(K\), and if possible, find the minimum number of operations. In fact, the assignment of operation counts is uniquely determined, so the problem can be solved by simply verifying whether that assignment is valid.

Analysis

Introducing the Difference Array

First, compute \(D_i = B_i - A_i\) (the required increase for each section). Since operations can only increase values, if any \(D_i < 0\) exists, it is immediately impossible.

Uniqueness of Operation Counts

Let \(M = N - K + 1\), and let \(x_l\) (\(l = 1, \ldots, M\)) be the number of operations starting at position \(l\). Define \(P_i = x_1 + x_2 + \cdots + x_i\) (the prefix sum of \(x\)). Then the constraint for section \(i\) is as follows:

• Case \(1 \leq i \leq K\) (and \(i \leq M\)): The operations affecting section \(i\) are \(l = 1, \ldots, i\), so \(P_i = D_i\)
• Case \(K < i \leq M\): The operations affecting it are \(l = i-K+1, \ldots, i\), so \(P_i - P_{i-K} = D_i\), i.e., \(P_i = D_i + P_{i-K}\)
• Case \(M < i \leq N\): The operations affecting it are \(l = i-K+1, \ldots, M\), so \(P_M - P_{i-K} = D_i\)

From the first two formulas, \(P_1, P_2, \ldots, P_M\) are uniquely determined. In other words, if a solution exists, there is only one possible assignment of operation counts, and the total \(P_M\) is the answer.

Conditions to Verify

1. All \(D_i \geq 0\)
2. All \(x_l = P_l - P_{l-1} \geq 0\) (operation counts are non-negative)
3. For sections at position \(M+1\) and beyond, \(P_M - P_{i-K} = D_i\) holds

Algorithm

1. Compute \(D_i = B_i - A_i\). If any \(D_i < 0\), output -1.
2. Build the prefix sum \(P\):
   • If \(i \leq K\), then \(P_i = D_i\)
   • If \(i > K\), then \(P_i = D_i + P_{i-K}\)
3. Non-negativity check: Verify \(P_i - P_{i-1} \geq 0\) (\(P_0 = 0\)) for all \(i\).
4. Consistency check: For \(i = M+1, \ldots, N\), verify \(P_M - P_{\max(0, i-K)} = D_i\).
5. If all checks pass, output \(P_M\).

Concrete Example

For \(N = 5, K = 3, M = 3\), \(D = [2, 3, 4, 2, 1]\):

• \(P_1 = 2, P_2 = 3, P_3 = 4\)
• \(x_1 = 2, x_2 = 1, x_3 = 1\) (all non-negative ✓)
• Section 4: \(P_3 - P_1 = 4 - 2 = 2 = D_4\) ✓
• Section 5: \(P_3 - P_2 = 4 - 3 = 1 = D_5\) ✓
• Answer: \(P_3 = 4\)

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• \(P_M\) (the answer) can reach up to \(3 \times 10^{14}\), so use long long.

• Set \(P_0 = 0\) as the initial value when managing prefix sum indices.

• For cases where \(i - K \leq 0\), use \(P_0 = 0\) (handle with max(0, i-K)).

  Source Code

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, K;
    cin >> N >> K;
    
    vector<long long> A(N+1), B(N+1), D(N+1);
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= N; i++) cin >> B[i];
    
    for (int i = 1; i <= N; i++) {
        D[i] = B[i] - A[i];
        if (D[i] < 0) {
            cout << -1 << endl;
            return 0;
        }
    }
    
    int M = N - K + 1;
    vector<long long> S(M+1, 0);
    
    for (int i = 1; i <= M; i++) {
        if (i <= K) {
            S[i] = D[i];
        } else {
            S[i] = D[i] + S[i-K];
        }
    }
    
    for (int i = 1; i <= M; i++) {
        if (S[i] - S[i-1] < 0) {
            cout << -1 << endl;
            return 0;
        }
    }
    
    for (int i = M+1; i <= N; i++) {
        int lower_minus_1 = max(0, i - K);
        long long expected = S[M] - S[lower_minus_1];
        if (expected != D[i]) {
            cout << -1 << endl;
            return 0;
        }
    }
    
    cout << S[M] << endl;
    return 0;
}

---

This editorial was generated by claude4.6opus-thinking.