Overview

This is a problem where, after replacing the measurements of malfunctioning sensors with estimated values, you need to compute the sum of absolute differences between adjacent sensors (the total variation).

Analysis

This problem is a simulation problem where you update data as instructed and perform calculations.

First, the normal measurements of all sensors \(A_1, A_2, \ldots, A_N\) are given. Next, the numbers \(B_j\) of malfunctioning sensors and their estimated values \(C_j\) are given, so you overwrite the values of the corresponding sensors. Finally, you sum up all absolute differences between adjacent values to obtain the answer.

Key observations: - No special algorithm is needed; you just need to implement faithfully according to the problem statement - However, the malfunctioning sensor numbers \(B_j\) are given as 1-indexed (starting from 1), so you need to convert them to array indices (starting from 0) - The malfunctioning sensor numbers are not necessarily in ascending order, but since \(B_j\) and \(C_j\) have a correspondence, they should be processed together as pairs

Verification with a concrete example:

For example, with \(N=5, K=2\), \(A = [10, 20, 30, 40, 50]\), \(B = [2, 4]\), \(C = [25, 35]\):

1. Replace the value of sensor 2 with \(25\) and the value of sensor 4 with \(35\)
2. \(V = [10, 25, 30, 35, 50]\)
3. Total variation \(= |25-10| + |30-25| + |35-30| + |50-35| = 15 + 5 + 5 + 15 = 40\)

Algorithm

1. Create array \(V\) as a copy of \(A\)
2. For each \(j = 0, 1, \ldots, K-1\), overwrite \(V[B_j - 1]\) with \(C_j\) (converting from 1-indexed to 0-indexed)
3. Compute and output \(\sum_{i=0}^{N-2} |V[i+1] - V[i]|\)

Complexity

• Time complexity: \(O(N + K)\)
  • \(O(N)\) for copying the array, \(O(K)\) for replacing malfunctioning sensor values, \(O(N)\) for computing the total variation
• Space complexity: \(O(N)\)
  • \(O(N)\) for the array \(V\) storing the values after replacement

Implementation Notes

• Index conversion: Since the malfunctioning sensor numbers \(B_j\) are 1-indexed, you need to convert them using B[j] - 1 when accessing the array. Forgetting this will cause an off-by-one error.

• Don’t modify the original array: We create a copy using V = A[:]. If you write V = A, it creates a reference copy, and \(A\) itself will be modified (in this problem, since \(A\) is not used later, it wouldn’t cause an issue, but it’s a good practice).

• Value range: \(A_i, C_j\) can be up to \(10^9\), and the sum of adjacent differences can be approximately up to \(2 \times 10^{14}\). However, since Python does not have integer overflow, no special handling is needed.

  Source Code

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

V = A[:]
for j in range(K):
    V[B[j] - 1] = C[j]

result = sum(abs(V[i + 1] - V[i]) for i in range(N - 1))
print(result)

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