CF 106443B - Balatro

CF 106443B - Balatro

Rating: -
Tags: -
Solve time: 54s
Verified: yes

Solution

Problem Understanding

We are given two sequences of integers of equal length. One sequence belongs to Drex, the other to a boss. Before any interaction happens, Drex is allowed to permute his own sequence freely. After that arrangement is fixed, the two sequences are aligned index by index, and the total damage is computed as the sum of absolute differences between paired elements.

The task is to choose an ordering of Drex’s sequence so that this sum is as small as possible.

The key structural detail is that only Drex’s array is reorderable. The boss’s array is fixed, so the problem is fundamentally about pairing elements of two multisets in an optimal way.

The constraint n up to 2 × 10^5 immediately rules out any quadratic pairing strategy. Any solution that tries all matchings or even greedily tries local swaps without structure will fail in worst cases because the number of possible permutations grows factorially.

A common failure mode appears when one assumes that pairing equal indices or doing a naive greedy scan is sufficient. For example, if Drex has [10, 1, 100] and the boss has [2, 50, 60], pairing in original order gives a large cost, and local swaps without sorting insight may still miss the globally optimal pairing.

Another subtle edge case is when values are heavily skewed: a naive greedy that always matches closest remaining values without global ordering can get trapped in suboptimal early choices. For instance, Drex [1, 100, 101] and boss [2, 3, 200] requires a globally consistent ordering rather than locally optimal pairing decisions.

These issues suggest that the problem is not about local matching, but about global alignment of sorted structure.

Approaches

The brute-force idea is straightforward: try every permutation of Drex’s array, compute the resulting sum of absolute differences with the boss array, and take the minimum. This is correct because it explicitly evaluates all possible pairings induced by permutations. However, the number of permutations is n!, and each evaluation costs O(n), giving O(n · n!) operations, which becomes infeasible even for n around 10.

To improve this, we observe that the boss array is fixed, and we only control how Drex’s values are assigned to positions. The absolute value cost suggests a geometric interpretation: we are trying to match two point sets on a number line with minimum L1 matching cost in one dimension.

In one dimension, the optimal strategy for minimizing total absolute difference is to pair sorted elements with sorted elements. This works because any inversion in pairing can be shown to be improvable: if two pairs are crossed in sorted order, swapping them never increases cost and often decreases it. This is the classical exchange argument for optimal matching on a line.

So instead of trying permutations, we sort both arrays and match element i with element i.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n · n!)	O(n)	Too slow
Optimal (sorting + pairing)	O(n log n)	O(1) or O(n)	Accepted

Algorithm Walkthrough

We rely on the fact that pairing becomes optimal when both sequences are ordered consistently.

Steps

1. Read n, the size of both arrays.
2. Read Drex’s array and the boss’s array.
3. Sort both arrays in non-decreasing order.

Sorting enforces a global structure so that small values align with small values and large with large. 4. Initialize an accumulator for the total damage as zero. 5. Iterate i from 0 to n − 1. 6. For each index i, add the absolute difference between the i-th smallest Drex value and the i-th smallest boss value. 7. Output the accumulated sum.

The key decision is step 3. Without sorting both arrays, any greedy pairing is operating in a space where local decisions do not reflect global optimality. Sorting transforms the problem into a monotone matching problem.

Why it works

After sorting, both sequences are ordered on the same axis. If there exists a pair of indices i < j such that Drex[i] is paired with boss[j] and Drex[j] is paired with boss[i], then swapping these pairings cannot increase the total cost. This is because the absolute value distance on a line satisfies the property that crossing edges in a matching can always be uncrossed without worsening the total length. Repeatedly applying this argument removes all inversions between pairings, forcing the identity pairing on sorted arrays as an optimal solution.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    d = list(map(int, input().split()))
    b = list(map(int, input().split()))
    
    d.sort()
    b.sort()
    
    ans = 0
    for i in range(n):
        ans += abs(d[i] - b[i])
    
    print(ans)

if __name__ == "__main__":
    solve()

The implementation is direct once the sorting principle is understood. The main subtlety is ensuring both arrays are sorted independently before pairing. A common mistake is sorting only Drex’s array or attempting partial alignment without full sorting, which breaks the monotonic structure required for correctness.

The accumulation uses a standard loop because n can be large, but Python’s integer arithmetic comfortably handles the potential sum size since values can reach up to 2 × 10^14 in magnitude.

Worked Examples

Example 1

Input:

n = 3
d = [3, 1, 2]
b = [3, 1, 2]

Sorted arrays:

| i | d[i] | b[i] | |d[i] - b[i]| |

|---|------|------|--------------|

| 0 | 1 | 1 | 0 |

| 1 | 2 | 2 | 0 |

| 2 | 3 | 3 | 0 |

Total = 0

This demonstrates the ideal case where both multisets are identical. Sorting aligns identical values perfectly, producing zero cost.

Example 2

Input:

n = 4
d = [10, 1, 100, 50]
b = [2, 3, 60, 80]

Sorted arrays:

d = [1, 10, 50, 100]

b = [2, 3, 60, 80]

i	d[i]	b[i]	diff
0	1	2	1
1	10	3	7
2	50	60	10
3	100	80	20

Total = 38

This shows how global sorting enforces stable pairing between similarly scaled values, avoiding mismatches like pairing 100 with 2 or 1 with 80.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	dominated by sorting both arrays
Space	O(1) or O(n)	depending on sorting implementation and storage of arrays

The constraints allow up to 2 × 10^5 elements, and sorting at this scale is standard. The linear scan afterward is negligible, ensuring the solution comfortably fits within both time and memory limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from contextlib import redirect_stdout
    out = io.StringIO()
    with redirect_stdout(out):
        solve()
    return out.getvalue().strip()

# provided sample
assert run("3\n3 1 2\n3 1 2\n") == "0"

# all equal values
assert run("4\n5 5 5 5\n5 5 5 5\n") == "0"

# reverse order stress
assert run("5\n1 2 3 4 5\n10 9 8 7 6\n") == "25"

# minimum size
assert run("1\n-5\n10\n") == "15"

# mixed values
assert run("3\n-1 4 2\n3 0 5\n") == "5"

Test input	Expected output	What it validates
all equal	0	identical multisets give zero cost
reverse order	25	sorting prevents worst mismatches
n = 1	15	boundary correctness
mixed values	5	handling negatives and ordering

Edge Cases

A critical edge case is when both arrays contain identical multisets but in different orders. For example:

n = 5
d = [4, 1, 3, 2, 5]
b = [1, 2, 3, 4, 5]

Sorting both gives identical arrays, and the algorithm produces zero cost. A naive greedy without sorting might pair 4 with 1 early and never recover optimal alignment, leading to unnecessary cost accumulation.

Another case is extreme spread:

n = 3
d = [-100, 0, 100]
b = [-50, -49, 200]

After sorting:

d = [-100, 0, 100]

b = [-50, -49, 200]

Pairing index-wise produces:

50 + 49 + 100 = 199

If instead one tries to locally match closest values without global ordering, one may incorrectly pair 100 with -50 early, leaving -100 to be paired with 200, producing a much larger total. The sorted pairing avoids this by enforcing global monotonic alignment, ensuring no crossing pairings exist in the final matching.