Overview

This problem asks you to compute the total variation (the sum of absolute differences between adjacent sensors’ values) given the normal values of sensors and the estimated values for malfunctioning sensors.

Analysis

In the problem, \(K\) out of \(N\) sensors are malfunctioning, and estimated values are assigned to the malfunctioning sensors. The variation is defined as the sum of absolute differences between the values of adjacent sensors.

A straightforward approach is to store all sensor values in an array \(V\) (using the normal value \(A_i\) for functioning sensors and the estimated value \(C_j\) for malfunctioning sensors), then sequentially compute and sum up the absolute differences between adjacent elements. This method is intuitive and easy to understand, and given the constraints, it is sufficiently efficient.

The maximum value of \(N\) is 200,000, which can be handled with a simple linear scan (\(O(N)\)). Therefore, no special optimization is needed.

Algorithm

1. Read the input data
2. Prepare an array \(V\) to store sensor values (initialized with the normal values \(A\))
3. For each malfunctioning sensor \(B_j\), overwrite the corresponding position in \(V\) with the estimated value \(C_j\)
4. Iterate through the array \(V\) from the beginning, summing up the absolute differences between adjacent elements
5. Output the total sum

Complexity

• Time complexity: \(O(N)\)
  • \(O(N)\) for initializing the array and updating malfunctioning sensors
  • \(O(N)\) for computing the variation
• Space complexity: \(O(N)\)
  • For storing the arrays \(A\), \(B\), \(C\), and \(V\)

Implementation Notes

• Since sensor numbers are given in 1-indexed format, pay attention to array indexing

• Use an efficient method for reading input data (such as sys.stdin.read())

• When updating malfunctioning sensors, \(B_j\) directly indicates the sensor number, so it can be used as an index as-is

• When computing the variation, be careful not to access out-of-bounds indices (\(i\) ranges from 1 to \(N-1\))

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    N = int(next(it))
    K = int(next(it))
    A = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = int(next(it))
    
    B = [0] * K
    for i in range(K):
        B[i] = int(next(it))
        
    C = [0] * K
    for i in range(K):
        C[i] = int(next(it))
        
    V = A[:]
    for i in range(K):
        idx = B[i]
        V[idx] = C[i]
        
    total = 0
    for i in range(1, N):
        total += abs(V[i + 1] - V[i])
        
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.