Introduction to Greedy Algorithms

Greedy Algorithms

Some USACO Bronze problems that appear to be ad hoc can actually be solved using greedy algorithms. This idea will be covered in a future module, but we'll introduce the general mindset in this section.

From the above:

A greedy algorithm constructs a solution to the problem by always making a choice that looks the best at the moment. A greedy algorithm never takes back its choices, but directly constructs the final solution. For this reason, greedy algorithms are usually very efficient.

Greedy does not refer to a single algorithm, but rather a way of thinking that is applied to problems; there's no one way to do greedy algorithms. Hence, we use a selection of well-known examples to help you understand the greedy paradigm.

Example - Mad Scientist

Try to come up with a greedy algorithm for problem above.

Correct Greedy Algorithm

In this problem, the correct greedy solution is to continually flip the longest possible ranges of mismatching cows.

Mad Scientist has an excellent editorial with a video solution and intuitive proof.

It is highly recommended you read it to gain a better understanding of the greedy algorithm.

Solution - Mad Scientist

Copy
#include <iostream>
#include <string>
using namespace std;
using ll = long long;

int main() {
	freopen("breedflip.in", "r", stdin);
	freopen("breedflip.out", "w", stdout);
	ll n;
	cin >> n;

Copy
import java.io.*;
import java.util.*;
public class Solution {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("breedflip");
		int n = io.nextInt();
		char[] a = io.next().toCharArray();
		char[] b = io.next().toCharArray();
		int ret = 0;
		while (!new String(a).equals(new String(b))) {

Copy
import sys

sys.stdin = open("breedflip.in", "r")
sys.stdout = open("breedflip.out", "w")

N, a, b = input(), input(), input()
s = [False] + [x != y for x, y in zip(a, b)]  # difference list
# now count occurrences of [False,True], as the first C++ solution does
print(sum(1 if not x and y else 0 for x, y in zip(s, s[1:])))

Note that not all greedy problems necessarily require mathematical proofs of correctness. It is often sufficent to intuitively convince yourself your algorithm is correct.

Problems

Quiz