## Intuition The problem requires us to assign students to fix bugs such that all bugs are fixed in the minimum number of days, while also ensuring that the total number of passes given to students does not exceed a specified limit. The key insight is to use a greedy approach combined with binary search to efficiently assign students to bugs based on their abilities and the passes they demand. ## Approach 1. **Sorting and Preparation**: - First, sort the bugs by their complexity. - Sort the students by their abilities. For each student, also keep track of the passes they demand. 2. **Binary Search on Days**: - Use binary search to determine the minimum number of days required to fix all bugs. The idea is to check if it's possible to fix all bugs in `d` days. 3. **Feasibility Check for `d` Days**: - For a given number of days `d`, check if it's possible to assign students to bugs such that: - Each student can fix at most `d` bugs. - The total passes given do not exceed the limit `s`. - Use a priority queue (or multiset) to efficiently manage and assign students to bugs based on their ability to fix a bug and the passes they demand. 4. **Greedy Assignment**: - Iterate over the sorted bugs and try to assign the most suitable student (one who can fix the bug and demands the least passes) to each bug. - If a student can fix a bug, assign it and update the total passes used. 5. **Output**: - If a valid assignment is found within the pass limit, output "YES" and the assignment. Otherwise, output "NO". ## Complexity - **Time Complexity**: O(n log n + m log m + m log n), where `n` is the number of students and `m` is the number of bugs. This accounts for sorting and the binary search feasibility check. - **Space Complexity**: O(n + m), for storing students and bugs. ## Solution (C++) ```cpp #include using namespace std; struct Student { int ability, passes, index; }; bool canFixAllBugs(int days, vector& bugs, vector& students, int s, vector& assignment) { int m = bugs.size(); int n = students.size(); vector studentIndex(n); iota(studentIndex.begin(), studentIndex.end(), 0); sort(studentIndex.begin(), studentIndex.end(), [&](int i, int j) { return students[i].passes < students[j].passes; }); multiset> availableStudents; // (ability, index) int j = 0; int totalPasses = 0; for (int i = m - 1; i >= 0; --i) { while (j < n && students[studentIndex[j]].ability >= bugs[i]) { availableStudents.insert({students[studentIndex[j]].ability, studentIndex[j]}); ++j; } if (availableStudents.empty()) return false; auto it = availableStudents.begin(); totalPasses += students[it->second].passes; if (totalPasses > s) return false; assignment[i] = students[it->second].index + 1; availableStudents.erase(it); } return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, s; cin >> n >> m >> s; vector bugs(m); for (int i = 0; i < m; ++i) { cin >> bugs[i]; } vector students(n); for (int i = 0; i < n; ++i) { cin >> students[i].ability; } for (int i = 0; i < n; ++i) { cin >> students[i].passes; students[i].index = i; } sort(bugs.begin(), bugs.end()); sort(students.begin(), students.end(), [](const Student& a, const Student& b) { return a.ability > b.ability; }); int left = 1, right = m, answer = -1; vector assignment(m); while (left <= right) { int mid = (left + right) / 2; if (canFixAllBugs(mid, bugs, students, s, assignment)) { answer = mid; right = mid - 1; } else { left = mid + 1; } } if (answer == -1) { cout << "NO\n"; } else { cout << "YES\n"; for (int i = 0; i < m; ++i) { cout << assignment[i] << " "; } cout << "\n"; } return 0; } ``` This solution efficiently finds the minimum number of days required to fix all bugs while respecting the pass constraints. The use of sorting and binary search ensures that the solution is both optimal and efficient.

Preparing for the Contest

Problem Details