Solution: 2237B - Annoying the Ghost
Hint 01
We are given that the final array $$$b$$$ is strictly increasing ($$$b_1 \lt b_2 \lt \dots \lt b_n$$$). We construct this final array from left to right. Since we can only add ducks, an initial pile $$$a_j$$$ can be transformed into a target pile $$$b_i$$$ if and only if $$$a_j \le b_i$$$.
Hint 02
If we decide which elements of $$$a$$$ map to which elements of $$$b$$$, the number of adjacent swaps required to reorder them into their final positions is exactly the number of inversions created by our choice.
Greedy Approach
Since $$$b$$$ is strictly increasing ($$$b_1 \lt b_2 \lt \cdots \lt b_n$$$), the condition $$$a_j \le b_i$$$ becomes easier to satisfy as $$$i$$$ increases. Therefore, it is best to process the elements of $$$b$$$ from left to right.
For each $$$b_i$$$, we choose the leftmost unused position $$$j$$$ such that $$$a_j \le b_i$$$. This greedy choice works perfectly because:
- Choosing an earlier valid element leaves later elements available for the larger values of $$$b$$$ coming up next.
- Taking the leftmost available element minimizes the distance it has to travel, which keeps the number of swaps as small as possible.
Counting Swaps
Suppose the element chosen for $$$b_i$$$ is at position $$$j$$$. To move it to its correct spot, it must swap past every element to its left that hasn't been used yet. Elements that are already matched don't count because they have already been moved out of the way.
So, the number of swaps needed for position $$$j$$$ is simply the number of unmatched positions before it:
While this can be optimized using a Fenwick Tree (Binary Indexed Tree) to query prefix sums in $$$O(\log n)$$$ time, the constraints here allow us to just use a simple loop to count unmatched elements in $$$O(n)$$$ time per step. Summing these counts up for all elements gives us our final answer. If we ever find a $$$b_i$$$ that cannot match with any available $$$a_j$$$, it's impossible, so we output -1.
int n, ans = 0;
cin >> n;
vector<int> a(n), b(n), seen(n + 1);
for (int& it : a) cin >> it;
for (int& it : b) cin >> it;
for (int i = 0; i < n; ++i) {
bool ok = false;
for (int j = 0; j < n; ++j) {
if (a[j] <= b[i] && !seen[j]) {
ok = true;
seen[j] = 1;
break;
}
if (!seen[j]) {
++ans;
}
}
if (!ok) {
cout << -1 << endl;
return;
}
}
cout << ans << endl;
Complexity Analysis
- Time Complexity: $$$\mathcal{O}(n^2)$$$ per test case. Since $$$\sum n \le 2000$$$, an $$$n^2$$$ approach easily runs well within the 1.5-second time limit.
- Space Complexity: $$$\mathcal{O}(n)$$$ to store the arrays and the tracking (
seen) array.








