Mastering the Greedy strategy for Competitive Programming. These problems are selected from Codeforces to help you build intuition from level 800 to 1600.
Problem: 959A - Even-Odd Game
The game logic is simple: Mahmoud wins if $n$ is even, and Ehab wins if $n$ is odd. Why? If $n$ is even, Mahmoud can choose $a = n$ (since $n$ is even and $1 \le a \le n$). After this move, $n$ becomes $0$, and Ehab cannot make any move because there's no odd number $a$ such that $1 \le a \le 0$. If $n$ is odd, any even number Mahmoud picks will leave an odd number for Ehab. Ehab can then pick that entire odd number to win.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
// If n is even, Mahmoud wins by taking the whole number
if (n % 2 == 0) {
cout << "Mahmoud" << endl;
} else {
cout << "Ehab" << endl;
}
return 0;
}Problem: 230A - Dragons
This is a classic Sorting Greedy problem. To win, you need to gain as much strength as possible. The only way to gain strength is by defeating a dragon. If you have a choice between two dragons, you should always pick the one with the lower strength first, provided your current strength is greater than its strength. By defeating weaker dragons first, your strength increases, making it easier to defeat stronger ones later.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int s, n;
cin >> s >> n;
vector<pair<int, int>> dragons(n);
for (int i = 0; i < n; ++i) {
cin >> dragons[i].first >> dragons[i].second;
}
// Greedy Strategy: Sort by dragon strength (x_i)
sort(dragons.begin(), dragons.end());
bool possible = true;
for (int i = 0; i < n; ++i) {
if (s > dragons[i].first) {
s += dragons[i].second;
} else {
possible = false;
break;
}
}
if (possible) cout << "YES" << endl;
else cout << "NO" << endl;
return 0;
}Problem: 158B - Taxi
The greedy strategy here is to fill each taxi as much as possible. 1. Groups of 4 always need their own taxi. 2. Groups of 3 should be paired with a group of 1 if available. 3. Two groups of 2 can share a taxi. 4. If one group of 2 is left, it can be paired with up to two groups of 1. 5. Any remaining groups of 1 fill taxis in sets of 4.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, x;
cin >> n;
vector<int> count(5, 0);
for (int i = 0; i < n; ++i) {
cin >> x;
count[x]++;
}
int taxis = count[4];
// Pair 3s with 1s
taxis += count[3];
count[1] = max(0, count[1] - count[3]);
// Pair 2s with 2s
taxis += count[2] / 2;
if (count[2] % 2 == 1) {
taxis++;
count[1] = max(0, count[1] - 2);
}
// Remaining 1s
taxis += (count[1] + 3) / 4;
cout << taxis << endl;
return 0;
}Problem: 545C - Woodcutters
The greedy approach works because falling a tree to the left is always better than falling it to the right, and falling it to the right is better than not falling it at all. Why? If a tree can fall left, it doesn't occupy any space to its right, leaving more room for future trees. If it can't fall left but can fall right, we take it because it's a guaranteed point, and it only potentially blocks the immediate next tree.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
if (n == 1) { cout << 1 << endl; return 0; }
vector<long long> x(n), h(n);
for (int i = 0; i < n; ++i) cin >> x[i] >> h[i];
int count = 2; // First and last always fall
long long last_pos = x[0];
for (int i = 1; i < n - 1; ++i) {
if (x[i] - h[i] > last_pos) {
count++;
last_pos = x[i];
} else if (x[i] + h[i] < x[i+1]) {
count++;
last_pos = x[i] + h[i];
} else {
last_pos = x[i];
}
}
cout << count << endl;
return 0;
}Problem: 1622C - Set or Decrease
The strategy is to sort the array and always use $a_1$ (the minimum) to replace the largest elements. Let $k$ be the number of elements we replace ($0 \le k \le n-1$). If we replace $k$ elements, we replace $a_n, a_{n-1}, \dots, a_{n-k+1}$ with $a_1 - x$, where $x$ is the number of times we decreased $a_1$. The total sum becomes: $(a_1 - x) \cdot (k + 1) + \sum_{i=2}^{n-k} a_i \le k$. We iterate through all possible values of $k$ and find the minimum $x+k$.
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
void solve() {
long long n, k;
cin >> n >> k;
vector<long long> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
sort(a.begin(), a.end());
vector<long long> pref(n + 1, 0);
for (int i = 0; i < n; ++i) pref[i+1] = pref[i] + a[i];
long long ans = 2e18;
for (int y = 0; y < n; ++y) {
// y is number of elements to set to a[0]-x
long long current_sum = pref[n-y] + y * a[0];
long long diff = current_sum - k;
long long x = 0;
if (diff > 0) {
x = (diff + y) / (y + 1);
}
ans = min(ans, x + y);
}
cout << ans << endl;
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}