# 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

greedyalgorithm 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

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.

### Solution - Mad Scientist

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

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Bronze | Normal | ## Show TagsGreedy | |||

Bronze | Normal | ## Show TagsGreedy | |||

Bronze | Hard | ## Show TagsGreedy | |||

Bronze | Hard | ## Show TagsGreedy | |||

Bronze | Easy | ## Show TagsGreedy | |||

Bronze | Very Hard | ## Show TagsGreedy |

## Quiz

What is a greedy algorithm?

### Module Progress:

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