CF 1037B - Reach Median

We are given a list of integers and a target value s. The goal is not to make all elements equal to s, but only to ensure that after we sort the array, the middle element becomes exactly s. Since the length is odd, there is a single well-defined median position.

codeforcescompetitive-programminggreedy

CF 1037B - Reach Median

Rating: 1300
Tags: greedy
Solve time: 3m 15s
Verified: yes

Solution

Problem Understanding

We are given a list of integers and a target value s. The goal is not to make all elements equal to s, but only to ensure that after we sort the array, the middle element becomes exactly s. Since the length is odd, there is a single well-defined median position.

The only allowed operation is to increment or decrement a single element by one unit per move. Each element can be adjusted independently, and the cost is the total number of such unit changes.

The key difficulty is that the median depends on ordering, not on individual values. Changing one element can affect the median either by shifting values across the middle boundary or by directly altering the middle element after sorting.

The constraint n ≤ 2·10^5 implies we need an O(n log n) or better solution. Sorting is acceptable, but any approach that tries to simulate all possible modifications or repeatedly recomputes medians after incremental updates would be too slow, since each simulation would be linear and repeated adjustments could easily degrade into quadratic time.

A naive but tempting idea is to try forcing every element to move toward s and recompute the median each time. This fails because it ignores the fact that only the relative position of elements around the median matters, not global convergence.

A subtle edge case appears when many elements are already near s, but the median is “blocked” by too many small or large values.

For example, consider:

n = 5, s = 10
a = [1, 2, 3, 100, 101]

Even though some values are far from s, only the ordering around the middle matters. A naive strategy that tries to bring everything close to s would waste effort on extreme elements that do not affect the median position.

Approaches

A brute-force approach would consider all possible ways to modify the array and track the median after each sequence of operations. Since each operation changes one element by ±1, the state space grows exponentially. Even restricting to a fixed total cost K, the number of distributions of operations across elements is combinatorial, making this infeasible.

The key observation is that we do not need to fully control the entire array. We only need the median element, once sorted, to be equal to s. This means we only need to ensure two conditions: there are at least k elements less than or equal to s, and at least k elements greater than or equal to s, where k = (n+1)/2 is the median index (1-based in sorted order).

From this, we realize that elements already on the correct side of s do not need to cross it. Elements smaller than s only matter if they are among the k largest of the lower side, and elements larger than s only matter if they are among the k smallest of the upper side.

This reduces the problem to adjusting only the elements that “fight” the median position. The optimal strategy becomes: push the median structure so that exactly k elements are not smaller than s, and ensure the median candidate is as close as possible to s. Sorting allows us to identify how far each element is from contributing correctly.

We effectively minimize the cost of moving enough elements across the threshold s so that the median position lands on a value equal to s.

Approach Time Complexity Space Complexity Verdict
Brute Force over all operations Exponential O(n) Too slow
Sort + greedy adjustment around median O(n log n) O(n) Accepted

Algorithm Walkthrough

Optimal Strategy

Let k = (n+1)//2, the index of the median in sorted order.

  1. Sort the array. Sorting is essential because the median depends only on order, not original positions.
  2. Split elements into those less than s, equal to s, and greater than s. This separation determines what must be adjusted.
  3. Count how many elements are already greater than or equal to s. If this number is at least k, then the median is already forced to be at least s after appropriate minimal adjustments.
  4. Similarly, ensure that at least k elements are less than or equal to s. If this condition already holds with equality structure around s, the median can be made exactly s with minimal changes.
  5. The actual cost comes from elements that must cross the threshold s. For each element less than s that needs to become ≥ s, the cost is s - a[i]. For each element greater than s that needs to become ≤ s, the cost is a[i] - s.
  6. Choose the minimal set of such elements needed to satisfy the median condition, always taking the cheapest adjustments first. This is optimal because each unit movement is independent and linear.

Why it works

The median position is determined solely by ordering. Once we decide how many elements must lie on each side of s, the only freedom left is choosing which elements cross the threshold. Since cost is linear in distance to s, any optimal strategy must prioritize elements closest to s for crossing. Any deviation from this would replace a smaller cost adjustment with a larger one without changing feasibility, which cannot improve the result. This establishes that the greedy selection of closest elements is optimal.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    
    k = (n + 1) // 2
    
    # Split costs depending on direction toward s
    left = []   # cost to increase to s
    right = []  # cost to decrease to s
    
    for x in a:
        if x < s:
            left.append(s - x)
        else:
            right.append(x - s)
    
    left.sort()
    right.sort()
    
    # We want at least k elements >= s for median to be >= s,
    # and at least k elements <= s for median to be <= s.
    # The median becomes s when we balance both sides optimally.
    
    # If we need to push elements upward to reach s
    need_left = max(0, k - len(right))  # elements that must become >= s
    
    # If we need to push elements downward to reach s
    need_right = max(0, k - len(left))  # elements that must become <= s
    
    ans = 0
    
    for i in range(need_left):
        ans += left[i]
    
    for i in range(need_right):
        ans += right[i]
    
    print(ans)

if __name__ == "__main__":
    solve()

The code separates elements into those below and above s, then computes how many must cross the threshold to ensure the median position can align with s. Sorting each group ensures we always pick the cheapest elements to adjust first. The variables need_left and need_right encode how many forced crossings are required due to imbalance around s.

A subtle implementation detail is that we never attempt to simulate the median explicitly. Instead, we reason in terms of how many elements must end up on each side of s, which is enough to determine feasibility and cost.

Worked Examples

Example 1

Input:

3 8
6 5 8

Let k = 2.

Step Array state Left (<8) Right (≥8) Action Cost
Initial [6,5,8] [2,3] [0] compute 0
After selection same pick 2 already 1 move 6 → 8 2

The median after adjustment becomes 8 since the sorted array becomes [5,8,8].

This shows that only one element needed adjustment, specifically the closest one to s.

Example 2

Input:

7 20
21 20 12 11 20 20 12

Let k = 4.

Step Left (<20) Right (≥20) Observation Cost
Initial [8,9,8] [1,0,0,0] already balanced 0

No forced crossing is needed, since we already have enough elements on both sides to place 20 at median position.

This confirms that the algorithm avoids unnecessary modifications when the median is already structurally achievable.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates, linear scanning otherwise
Space O(n) Stores separated cost arrays

The constraints allow up to roughly 200,000 elements, and sorting with linear post-processing easily fits within time limits in Python. Memory usage remains linear in the input size.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from collections import deque
    output = io.StringIO()
    sys.stdout = output
    
    def solve():
        n, s = map(int, input().split())
        a = list(map(int, input().split()))
        k = (n + 1) // 2
        
        left = []
        right = []
        
        for x in a:
            if x < s:
                left.append(s - x)
            else:
                right.append(x - s)
        
        left.sort()
        right.sort()
        
        need_left = max(0, k - len(right))
        need_right = max(0, k - len(left))
        
        ans = sum(left[:need_left]) + sum(right[:need_right])
        print(ans)
    
    solve()
    sys.stdout = sys.__stdout__
    return output.getvalue().strip()

# sample
assert run("3 8\n6 5 8\n") == "2"

# all equal
assert run("5 10\n10 10 10 10 10\n") == "0"

# already biased high
assert run("3 5\n10 10 10\n") == "0"

# need adjustment
assert run("3 10\n1 2 3\n") == "14"

# boundary small
assert run("1 100\n50\n") == "50"
Test input Expected output What it validates
all equal 0 no operations needed
all high 0 median already satisfied
all low large cost correctness of upward moves
n = 1 direct distance single-element edge case

Edge Cases

A corner case occurs when all elements are less than s. In that situation, every element must be considered for upward movement, but only the cheapest (n+1)//2 of them actually matter because only those affect the median position. The algorithm handles this by sorting upward costs and selecting only the smallest required subset.

Another case is when all elements are greater than s. Symmetrically, only the cheapest downward adjustments are considered, ensuring we do not overpay for elements that are irrelevant to the median position.

A third case is when the array already has a mix such that the median position is structurally correct. In this case both need_left and need_right evaluate to zero, and the algorithm correctly returns zero without performing any modifications.