Overview

Starting from the library counter (coordinate \(0\)), you repeatedly carry at most \(K\) books at a time back to their shelves. The goal is to minimize the total distance traveled. The positive and negative sides can be handled independently, and the problem is solved greedily by grouping books starting from the farthest ones on each side.

Analysis

Key Insight 1: The positive and negative sides can be considered independently

Let’s consider visiting shelves on both the positive and negative sides in a single round trip. For example, if we visit the farthest point \(p\) on the positive side and the farthest point \(-q\) (\(q > 0\)) on the negative side simultaneously, the optimal path is:

\[0 \to -q \to p \to 0 \quad \text{(distance: } q + (q + p) + p = 2p + 2q\text{)}\]

This is exactly the same distance as making separate round trips: \(2p\) for the positive side and \(2q\) for the negative side. Moreover, carrying books from both sides simultaneously requires sharing the capacity of \(K\) books between both sides, which may actually increase the number of round trips.

Therefore, it is optimal to process the positive and negative sides completely independently.

Key Insight 2: Group books starting from the farthest ones

Consider only one side. For example, suppose books on the positive side are at positions \([1, 3, 5, 7, 9]\) with \(K = 2\):

• 1st round trip: Carry books at coordinates \(9, 7\) → Cost \(2 \times 9 = 18\)
• 2nd round trip: Carry books at coordinates \(5, 3\) → Cost \(2 \times 5 = 10\)
• 3rd round trip: Carry the book at coordinate \(1\) → Cost \(2 \times 1 = 2\)

The cost of each round trip is the position of the farthest book in that group \(\times 2\) (since it’s a round trip). By grouping far books together, closer books get a “free ride,” minimizing the total distance.

Why group from the farthest?

The cost of a round trip is determined by the farthest point in the group. By placing far books in the same group, we reduce the number of “high-cost round trips.” Conversely, mixing far and close books is wasteful because it forces additional round trips for the close books.

Algorithm

1. Separate books into positive coordinates and negative coordinates
2. Positive side: Sort coordinates in ascending order, then group \(K\) books at a time starting from the farthest. The cost of each group is \(2 \times (\text{farthest coordinate in the group})\)
3. Negative side: Sort by absolute value in descending order, then similarly group \(K\) books at a time. The cost of each group is \(2 \times (\text{largest absolute value in the group})\)
4. Sum the total costs of the positive and negative sides and output the result

Concrete example: \(N=5, K=2, X = [-4, -1, 2, 5, 8]\)

• Positive side \([2, 5, 8]\): Group \(\{8, 5\}\) → \(2 \times 8 = 16\), Group \(\{2\}\) → \(2 \times 2 = 4\). Total \(20\)
• Negative side \([-4, -1]\): Group \(\{-4, -1\}\) → \(2 \times 4 = 8\). Total \(8\)
• Answer: \(20 + 8 = 28\)

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (for storing the lists split by sign)

Implementation Notes

• Converting negative coordinates to their absolute values allows them to be processed with the same logic as the positive side

• Grouping can be implemented simply by scanning indices from the end (farthest) of the sorted array, stepping by \(K\) at a time

• Ensure the solution works correctly even when one side is empty (no books)

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    X = [int(input_data[i + 2]) for i in range(N)]
    
    # Separate positive and negative positions
    pos = sorted([x for x in X if x > 0])
    neg = sorted([x for x in X if x < 0], key=lambda x: -x)  # sorted by distance from 0, descending abs value first
    # neg is sorted so that neg[0] is the most negative (farthest), etc.
    # Actually let's sort neg by absolute value descending
    # neg values are negative, sorted by ascending means most negative first
    # We want groups where each trip takes the K farthest remaining books
    
    # For positive side: sort ascending. Group from farthest.
    # Each trip of K books: go to the farthest in the group and come back = 2 * farthest
    # Optimal: group the farthest K together, next K together, etc.
    # The farthest in each group determines the trip cost (2 * that distance)
    
    # For negative side: same logic with absolute values
    
    # Positive trips: take every K-th from the end
    pos_cost = 0
    # pos is sorted ascending, so pos[-1] is farthest
    # Groups: pos[-K:], pos[-2K:-K], etc.
    # The cost for each group is 2 * max of group = 2 * pos[last_in_group]
    i = len(pos) - 1
    while i >= 0:
        pos_cost += 2 * pos[i]
        i -= K
    
    # Negative trips: absolute values
    neg_abs = sorted([abs(x) for x in neg], reverse=True)
    neg_cost = 0
    i = 0
    while i < len(neg_abs):
        neg_cost += 2 * neg_abs[i]
        i += K
    
    # Now, we can potentially save one trip by combining the last trip on one side
    # with a trip on the other side. Specifically, the farthest positive trip and
    # the farthest negative trip can potentially be combined into one trip if we
    # have capacity, but actually they can't share capacity since we must visit both sides.
    
    # Wait, actually the key optimization: on one trip, we can go both left and right.
    # In that case, the cost is 2 * max(farthest_left, farthest_right) instead of
    # 2 * farthest_left + 2 * farthest_right. But we use K capacity for both sides.
    
    # Actually, re-reading the problem: each trip starts and ends at 0. On a single trip,
    # we can carry up to K books and visit multiple shelves in any order.
    # The optimal path for a trip visiting shelves on both sides: go to one extreme, 
    # come back through 0, go to other extreme, come back. Cost = 2*max_pos + 2*max_neg.
    # Or go to one side first then the other: cost = max_pos + max_pos + max_neg + max_neg... 
    # Actually no: go right to max_pos, come back to 0, go left to max_neg, back to 0:
    # cost = 2*max_pos + 2*|max_neg|. Same as separate trips!
    # 
    # Better: go left to max_neg, then all the way right to max_pos, then back to 0:
    # cost = |max_neg| + (|max_neg| + max_pos) + max_pos = 2*max_pos + 2*|max_neg|
    # Hmm, that's the same. Wait: |max_neg| + |max_neg| + max_pos + max_pos? No.
    # Path: 0 -> max_neg -> max_pos -> 0. Distance = |max_neg| + |max_neg - max_pos| + max_pos
    #   = |max_neg| + |max_neg| + max_pos + max_pos = 2*(|max_neg| + max_pos). Same.
    # 
    # So combining doesn't help at all in terms of distance. The only saving would be
    # if we save a trip. But the distance is the same.
    # 
    # Therefore, positive and negative sides are completely independent.
    
    print(pos_cost + neg_cost)

solve()

---

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