Not Frequent
0/7

# Introduction to Greedy Algorithms

Authors: Darren Yao, Benjamin Qi

Contributor: Ryan Chou

Problems that can be solved by selecting the choice that seems to be the best at the moment at every step.

## 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.

Resources
CPH

other examples are outside scope of bronze

### Warning!

True "greedy" problems start to show up in silver, though the greedy mindset can be very helpful for bronze problems.

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.

Focus Problem – try your best to solve this problem before continuing!

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.

C++

From the official analysis:

#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;

Java

From the official analysis (with Kattio added):

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))) {

Python

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 doesprint(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.

### Pro Tip

Sometimes, if the algorithm is easy enough to implement, you don't even need to convince yourself it's correct; just code it and see if it passes. Competitive programmers refer to this as "Proof by AC," or "Proof by Accepted."

## Problems

StatusSourceProblem NameDifficultyTags
BronzeEasy
Show TagsGreedy
BronzeNormal
Show TagsGreedy
BronzeNormal
Show TagsGreedy
BronzeHard
Show TagsGreedy
BronzeHard
Show TagsGreedy
BronzeVery Hard
Show TagsGreedy

## Quiz

What is a greedy algorithm?

Question 1 of 3

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!