Another Puzzle from Papyrus

Key Observation

Each element of $a$ can only go down. So if some value $x$ from $a$ is assigned to become some value $y$ in $b$, we need $x \ge y$, and the cost for that pair is $x-y$.

The reorder operation lets us choose which original elements of $a$ go to which positions of $b$. Since one reorder can produce any permutation, using more than one reorder is never useful. Two arbitrary shuffles still just mean “some final shuffle,” except now you paid extra for the privilege. Brutal deal.

So the whole problem has only two real possibilities:

1. Keep the original order.
2. Pay $c$ once and use the best possible permutation.

Case 1: No Reorder

If we do not reorder, position $i$ in $a$ must become position $i$ in $b$.

That is possible exactly when

$a_i \ge b_i$

for every $i$.

If it is possible, the cost is

$\sum_{i=1}^{n} (a_i-b_i).$

Call this value $D$.

Case 2: Use One Reorder

Now we may match elements of $a$ to elements of $b$ however we want. A matching is valid if every chosen source value is at least its target value.

Here is the sneaky part: if a valid matching exists, the decrement cost does not depend on which matching we picked.

Every element of $a$ is used exactly once, and every element of $b$ is produced exactly once, so the total number of decrements is always

$\sum a_i - \sum b_i.$

So optimization is not about minimizing decrements. That part is fixed. The only question is whether a valid matching exists.

To test that, sort both arrays increasingly:

$A_1 \le A_2 \le \dots \le A_n$

$B_1 \le B_2 \le \dots \le B_n$

Then a valid matching exists exactly when

$A_i \ge B_i$

for every $i$.

Why? Match the smallest available target with the smallest available source. If the smallest source cannot cover the smallest target, it cannot cover anything, so the whole thing is impossible. If it can, pairing them is safe, and the same logic repeats. This greedy matching is the classic sorted-pairing check.

If this sorted check passes, the cost with reorder is

$c + \sum a_i - \sum b_i.$

Putting It Together

Let

$D = \sum a_i - \sum b_i.$

• If the original order already works, answer is $D$.
• Otherwise, if the sorted arrays satisfy $A_i \ge B_i$ for all $i$, answer is $c+D$.
• Otherwise, answer is $-1$.

Technically, you can compute both candidates and take the minimum, but since $c>0$, if the original order works, it is always better than paying for a reorder.

Complexity

Sorting dominates:

$O(n \log n)$

per test case.

With $n \le 100$, this is basically instant. The CPU barely wakes up.