Overview

This problem asks you to choose a consecutive \(K\)-day operation period and minimize the total dissatisfaction (sum of absolute differences from desired dates) when delivering all packages.

Analysis

Key Observations

1. Packages within the period have 0 dissatisfaction: If a package’s desired date \(D_i\) falls within the operation period \([s, s+K-1]\), it can be delivered on the desired date, resulting in 0 dissatisfaction.

2. Optimal delivery date for packages outside the period:

   • For packages with desired date \(D_i < s\) (before the period) → Delivering on the first day \(s\) is optimal → Dissatisfaction is \(s - D_i\)
   • For packages with desired date \(D_i > s+K-1\) (after the period) → Delivering on the last day \(s+K-1\) is optimal → Dissatisfaction is \(D_i - (s+K-1)\)

3. Narrowing down candidates for starting day \(s\): Since \(s\) can be any positive integer, exhaustive search is impossible (\(K \leq 10^9\)). However, the optimal \(s\) is limited to cases where some package’s desired date becomes an endpoint of the period.

Why Can We Narrow Down the Candidates?

When we consider the cost function as a function of \(s\), it becomes a piecewise linear function. The slope changes at the moment when a package switches from “outside the period” to “inside the period”. This happens when \(s = D_i\) (package \(i\) is at the left endpoint) or \(s = D_i - K + 1\) (package \(i\) is at the right endpoint).

Therefore, the candidates are narrowed down to at most \(2N\).

Algorithm

1. Sort the desired dates \(D\)
2. If all desired dates fit within \(K\) days (\(D_{max} - D_{min} + 1 \leq K\)), the answer is 0
3. Compute prefix sums \(prefix[i] = D_0 + D_1 + \ldots + D_{i-1}\)
4. Enumerate candidate values of \(s\) (for each \(D_i\): \(s = D_i\) and \(s = D_i - K + 1\))
5. Calculate the cost for each candidate \(s\) and find the minimum

Cost Calculation Method (with fixed \(s\))

Let the operation period be \([s, e]\) (where \(e = s + K - 1\)):

• Overflow on the left: Total dissatisfaction for packages where \(D_j < s\)

  • Let \(L\) be the count and \(S_L\) be the sum, then the cost is \(L \cdot s - S_L\)

• Overflow on the right: Total dissatisfaction for packages where \(D_j > e\)

  • Let \(R\) be the count and \(S_R\) be the sum, then the cost is \(S_R - R \cdot e\)

Using binary search and prefix sums, we can calculate the cost for each candidate in \(O(\log N)\).

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting: \(O(N \log N)\)
  • Building prefix sums: \(O(N)\)
  • Cost calculation for each candidate (at most \(2N\)): \(O(N \log N)\)
• Space complexity: \(O(N)\)
  • Storing the sorted array and prefix sums

Implementation Notes

1. Proper use of binary search:

   • bisect_left(D, s): Number of elements where \(D_j < s\) (count of elements less than \(s\))
   • bisect_right(D, e): Number of elements where \(D_j \leq e\) (starting position of elements greater than \(e\))

2. Utilizing prefix sums: Precompute prefix sums to obtain range sums in \(O(1)\)

3. Removing duplicate candidates: Use a set to manage candidates and avoid calculating the same \(s\) multiple times

4. Handling special cases: If all packages fit within \(K\) days, output 0 early and terminate

Source Code

import sys
from bisect import bisect_left, bisect_right

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    D = [int(input_data[i + 2]) for i in range(N)]
    
    D.sort()
    
    # Case where all packages fit within K days
    if D[-1] - D[0] + 1 <= K:
        print(0)
        return
    
    # Compute prefix sums
    # prefix[i] = D[0] + D[1] + ... + D[i-1]
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + D[i]
    
    # Let the operation period be [s, s+K-1]
    # If package i's desired date D[i] is within the period, dissatisfaction is 0
    # If D[i] < s, delivering on day s is optimal → dissatisfaction is s - D[i]
    # If D[i] > s+K-1, delivering on day s+K-1 is optimal → dissatisfaction is D[i] - (s+K-1)
    
    # Candidates for optimal s are cases where some package's desired date becomes the left or right endpoint
    # That is, s = D[i] or s = D[i] - K + 1
    
    # When s is fixed:
    # - Packages where D[j] < s: total dissatisfaction = (count) * s - (sum of those D[j])
    # - Packages where D[j] > s + K - 1: total dissatisfaction = (sum of those D[j]) - (count) * (s + K - 1)
    
    def calc_cost(s):
        # Operation period [s, s + K - 1]
        e = s + K - 1
        
        # Count and sum where D[j] < s
        left_count = bisect_left(D, s)
        left_sum = prefix[left_count]
        
        # Count and sum where D[j] > e
        right_idx = bisect_right(D, e)
        right_count = N - right_idx
        right_sum = prefix[N] - prefix[right_idx]
        
        cost = left_count * s - left_sum + right_sum - right_count * e
        return cost
    
    min_cost = float('inf')
    
    # Enumerate candidate values of s
    candidates = set()
    for d in D:
        candidates.add(d)  # s = d (d is the left endpoint of the period)
        candidates.add(d - K + 1)  # s = d - K + 1 (d is the right endpoint of the period)
    
    for s in candidates:
        cost = calc_cost(s)
        min_cost = min(min_cost, cost)
    
    print(min_cost)

solve()

---

This editorial was generated by claude4.5opus.