T-Shirts ──────── N 🐭, M 👕: s₀ s₁ s₂ s₃ s₄ 👕 👕 👕 👕 👕 |─────────| |──| |───────| l₀ 🐭 r₀ l₂🐭r₂ l₃ 🐭 r₃ |─────────────| l₁ 🐭 r₁ Want to give as many t-shirts to mice that can wear them as possible. (Each mouse gets at most one t-shirt, each t-shirt is given to at most one mouse.) Subtask 1: One Mouse ──────────────────── Case 1: t-shirt too small s 👕 |─────| l 🐭 r Case 2: t-shirt too large s 👕 |─────| l 🐭 r Case 3: t-shirt fits s 👕 |─────| l 🐭 r Solution: if (l <= s && s <= r) { cout << "Yes\n"; } else { cout <<"No\n"; } Subtask 2: Same Size ──────────────────── All shirts have the same size: s 👕 👕 👕 👕 |─────────| |──| |───────| l₀ 🐭 r₀ l₂🐭r₂ l₃ 🐭 r₃ |─────────────| l₁ 🐭 r₁ Solution: int result = 0; for (int i = 0; i < n; i++) { if (l[i] <= s && s <= r[i]) { result++; } } cout << result << "\n"; Subtask 3: Only Lower Bounds ──────────────────────────── Mice can wear arbitrarily large t-shirts: s₀ s₁ s₂ s₃ s₄ 👕 👕 👕 👕 👕 |────⋯ |─⋯ |──⋯ l₀ 🐭 l₂🐭 l₃ 🐭 |──────⋯ |──⋯ l₁ 🐭 l₄ 🐭 Solution: Sort t-shirts by size and mice by lower bound: s₀ s₁ s₂ s₃ s₄ 👕 👕 👕 👕 👕 |────⋯ l₀ 🐭 |──────⋯ l₁ 🐭 |─⋯ l₂🐭 |──⋯ l₃ 🐭 |──⋯ l₄ 🐭 Solution: Assign t-shirts in order s₀ 👕 |────⋯ l₀ 🐭 s₁ 👕 |──────⋯ s₂ s₃ l₁ 🐭 👕 👕 |─⋯ ↓ l₂🐭 🗑️ s₄ 👕 |──⋯ l₃ 🐭 |──⋯ l₄ 🐭:( Why correct? - Potential problem: We give a t-shirt to a mouse or throw it into the trash (🗑️ ), but none of the optimal solutions does so. → We have to prove that whenever we give a t-shirt to a mouse or throw it into the trash, there is some optimal solution that does the same. We will just prove that the first step taken by our algorithm is correct. The remaining shirts and mice form another instance to which we can apply the same algorithm again. Case 1: Trash s₀ … 👕 ↓ |────⋯ 🗑️ l₀ 🐭 There is no mouse that can wear shirt 0, so any optimal solution will throw it away too. Case 2: Same as optimal solution: Our solution: s₀ … 👕 |────────⋯ l₀ 🐭 Optimal solution: s₀ … 👕 |────────⋯ l₀ 🐭 ✓ Case 3: Different from optimal solution: Our solution gives shirt 0 to mouse 0: s₀ … 👕 |────────⋯ l₀ 🐭 Optimal solution gives shirt 0 to mouse k: |────────⋯ l₀ 🐭 s₀ … 👕 |─────⋯ lₖ🐭 Multiple cases: - Case 3a: Optimal solution gives no shirt to mouse 0: Our solution: s₀ … 👕 |────────⋯ l₀ 🐭 Optimal solution: |────────⋯ l₀ 🐭 s₀ … 👕 |─────⋯ lₖ🐭 Can just take shirt from mouse k and give it to mouse 0 instead, to obtain an optimal solution that matches our solution: Our solution: s₀ … 👕 |────────⋯ l₀ 🐭 Optimal solution: s₀ … 👕 |────────⋯ l₀ 🐭:) |─────⋯ lₖ🐭:( - Case 3b: Optimal solution gives another shirt sⱼ to mouse 0: Our solution: s₀ … 👕 |────────⋯ l₀ 🐭 Optimal solution: sⱼ 👕 |────────⋯ l₀ 🐭 s₀ … 👕 |─────⋯ lₖ🐭 We can just swap the two shirts (s₀≤sⱼ as shirts are sorted, so they fit). Therefore, there is an optimal solution that gives shirt 0 to mouse 0. We have shown that when our algorithm makes the first step, the result can still be extended to an optimal solution. The same reasoning works for all later steps. Subtask 4: Lower- and Upper Bounds ────────────────────────────────── Now there are upper bounds too: s₀ s₁ s₂ s₃ s₄ 👕 👕 👕 👕 👕 |─────────| |──| |───────| l₀ 🐭 r₀ l₂🐭r₂ l₃ 🐭 r₃ |─────────────| l₁ 🐭 r₁ The algorithm from before no longer works: s₀ s₁ 👕 👕 |────────────────────| l₀ 🐭 r₁ |─────| l₁ 🐭 r₁ It does this: s₀ 👕 |────────────────────| l₀ 🐭 r₁ s₁ 👕 |─────| ↓ l₁ 🐭 r₁ 🗑️ But this is optimal: s₁ 👕 |────────────────────| l₀ 🐭 r₁ s₀ 👕 |─────| l₁ 🐭 r₁ What is the problem? Case 3b fails: - Case 3b: Optimal solution gives another shirt sⱼ to mouse 0: Optimal solution: sⱼ 👕 |───────────| l₀ 🐭 r₀ s₀ … 👕 |────| lₖ🐭 rₖ Why does it fail? rₖ mice(n); iota(mice.begin(), mice.end(), 0); // fill with values 0,1,...,n-1 // sort mice according to lower bound: sort(mice.begin(), mice.end(), [&](int i, int j){ return l[i] < l[j]; }); // create a priority queue of mice sorted according to upper bound: auto cmp = [&](int i, int j){ return r[j] < r[i]; }; priority_queue, decltype(cmp)> q(cmp); int result = 0; for (int cur = 0, int j = 0; j < m;) { // add mice for which t-shirt j is now large enough: while (cur < n && l[mice[cur]] <= s[j]) { q.push(mice[cur++]); } // remove mice for which t-shirt j is now too large: while (!q.empty() && r[q.top()] < s[j]) { q.pop(); } if (!q.empty()) { result++; // give t-shirt j to mouse i q.pop(); // remove mouse i (i is q.top()) j++; // remove t-shirt j } else { // t-shirt j does not fit any remaining mouse j++; // remove t-shirt j } } return result; cout << result << "\n";