Overview

This is a problem where we need to find the minimum number of flowers to add so that the difference in the number of flowers between adjacent flower beds is at most \(K\). Since flowers cannot be removed, the number of flowers in each flower bed can only be increased.

Analysis

Key Observations

1. Flowers cannot be removed: If we let \(B_i\) be the final number of flowers in flower bed \(i\), there is a constraint that \(B_i \geq A_i\).
2. Adjacency constraint: For all adjacent flower beds, we must satisfy \(|B_i - B_{i+1}| \leq K\).
3. Minimization: We want to minimize the total number of flowers added: \(\sum_{i=1}^{N} (B_i - A_i)\).

Reformulating the Constraints

\(|B_i - B_{i+1}| \leq K\) can be decomposed into the following two conditions: - \(B_{i+1} \geq B_i - K\) (the right neighbor cannot be more than \(K\) less than the left flower bed) - \(B_i \geq B_{i+1} - K\) (the left neighbor cannot be more than \(K\) less than the right flower bed)

Constraints from Both Directions

For example, consider the case where \(A = [10, 1, 10]\) and \(K = 2\). - Looking from the left: if \(B_1 = 10\), then \(B_2 \geq 10 - 2 = 8\) - Looking from the right: if \(B_3 = 10\), then \(B_2 \geq 10 - 2 = 8\)

In this way, the value of a flower bed is subject to constraints from both left and right.

Algorithm

Step 1: Calculate Constraints from the Left

Define the array left_min[i]. This represents “the minimum value \(B_i\) should take when considering only constraints from the left side.”

• \(\text{left\_min}[0] = A_0\)
• \(\text{left\_min}[i] = \max(A_i, \text{left\_min}[i-1] - K)\)

This combines the constraint \(B_i \geq B_{i-1} - K\) with the constraint \(B_i \geq A_i\).

Step 2: Calculate Constraints from the Right

Similarly, define the array right_min[i].

• \(\text{right\_min}[N-1] = A_{N-1}\)
• \(\text{right\_min}[i] = \max(A_i, \text{right\_min}[i+1] - K)\)

Step 3: Integrate Both Constraints

Since the final number of flowers in each flower bed \(i\) must satisfy both constraints:

\[B_i = \max(\text{left\_min}[i], \text{right\_min}[i])\]

Step 4: Calculate the Answer

The total number of flowers to add is:

\[\sum_{i=0}^{N-1} (B_i - A_i)\]

Complexity

• Time Complexity: \(O(N)\)
  • \(O(N)\) for the left-to-right scan
  • \(O(N)\) for the right-to-left scan
  • \(O(N)\) for the final calculation
• Space Complexity: \(O(N)\)
  • \(O(N)\) for each of the arrays left_min, right_min, and B

Implementation Notes

1. Using the max function: By expressing each constraint with max, we can naturally handle both the condition “flowers can only be added” and the condition “the difference with neighbors is at most \(K\).”

2. Bidirectional scanning: Scanning in only one direction is insufficient. For example, scanning only from left to right would miss constraints coming from large values on the right side.

3. Special case when \(N = 1\): When there is only one flower bed, there are no adjacent flower beds, so no flowers need to be added (this implementation handles this case naturally).

Source Code

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    if N == 1:
        print(0)
        return
    
    total_flowers = 0
    
    for i in range(N - 1):
        diff = A[i + 1] - A[i]
        
        if diff > K:
            # A[i+1] is more than K greater than A[i]
            # We need to increase A[i]
            # Set A[i] to A[i+1] - K
            needed = diff - K
            A[i] = A[i + 1] - K
            total_flowers += needed
        elif diff < -K:
            # A[i] is more than K greater than A[i+1]
            # We need to increase A[i+1]
            # Set A[i+1] to A[i] - K
            needed = -diff - K
            A[i + 1] = A[i] - K
            total_flowers += needed
    
    # Also check in reverse direction (right to left)
    # Actually, if we increased A[i] in the left-to-right pass,
    # it might break the left-side conditions
    
    # Check again from left to right
    for i in range(N - 1):
        diff = A[i + 1] - A[i]
        if diff > K:
            needed = diff - K
            A[i] = A[i + 1] - K
            total_flowers += needed
        elif diff < -K:
            needed = -diff - K
            A[i + 1] = A[i] - K
            total_flowers += needed
    
    print(total_flowers)

# Alternative approach: Calculate the minimum required value at each position
def solve_v2():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    if N == 1:
        print(0)
        return
    
    # B[i] is the final number of flowers in flower bed i (B[i] >= A[i])
    # Condition: |B[i] - B[i+1]| <= K
    # Minimize: sum(B[i] - A[i])
    
    # Left to right: B[i+1] >= B[i] - K but B[i+1] >= A[i+1] so
    #                B[i+1] >= max(A[i+1], B[i] - K)
    # Right to left: B[i] >= B[i+1] - K but B[i] >= A[i] so
    #                B[i] >= max(A[i], B[i+1] - K)
    
    # Calculate minimum values from the left
    left_min = [0] * N
    left_min[0] = A[0]
    for i in range(1, N):
        # B[i] >= A[i] and B[i] >= B[i-1] - K
        left_min[i] = max(A[i], left_min[i-1] - K)
    
    # Calculate minimum values from the right
    right_min = [0] * N
    right_min[N-1] = A[N-1]
    for i in range(N-2, -1, -1):
        # B[i] >= A[i] and B[i] >= B[i+1] - K
        right_min[i] = max(A[i], right_min[i+1] - K)
    
    # The final value at each position must satisfy max(left_min[i], right_min[i])
    # However, the actual minimum value satisfies both left_min and right_min constraints
    
    # Does setting B[i] = max(left_min[i], right_min[i]) satisfy the conditions?
    # Actually, B[i] >= max(A[i], constraint from left, constraint from right)
    
    total = 0
    B = [max(left_min[i], right_min[i]) for i in range(N)]
    
    for i in range(N):
        total += B[i] - A[i]
    
    print(total)

solve_v2()

---

This editorial was generated by claude4.5opus.