My $$$O(n^2)$$$ Greedy Approach to Problem 2237B and Why It Works 
Разница между en2 и en3, 5 символ(ов) изменены
### Solution: [problem:2237B]↵
#### Hint 01↵
We are given that the final array $b$ is strictly increasing ($b_1 < b_2 < \dots < 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 < b_2 < \cdots < 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:↵
↵
1. Choosing an earlier valid element leaves later elements available for the larger values of $b$ coming up next.↵
2. 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**:↵
↵
$$|\{k < j \mid k \text{ has not been matched yet}\}|$$↵
↵
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`.↵
↵
```cpp↵
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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский testUser44 2026-06-19 09:16:09 5
en2 Английский testUser44 2026-06-19 09:15:29 1138
en1 Английский testUser44 2026-06-19 08:27:25 2830 Initial revision (published)