Warning!
Although the USACO website says that greedy algorithms start appearing in Silver, many Bronze problems can also be solved using greedy algorithms.
| Resources | |||||
|---|---|---|---|---|---|
| CPH | other examples are outside scope of bronze | ||||
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!
Solution - Mad Scientist
Solution
Note: it often is not obvious whether a greedy algorithm is correct or not. If it is the intended solution, problem authors are expected to be able to prove its correctness. However, as a contestant, if the algorithm is easy to implement, one option is to just code it and see whether it passes. Competitive programmers refer to this as "Proof by AC," or "Proof by Accepted."
Problems
| Status | Source | Problem Name | Difficulty | Tags | ||
|---|---|---|---|---|---|---|
| Bronze | Easy | Show TagsGreedy | ||||
| Bronze | Normal | Show TagsGreedy | ||||
| Bronze | Normal | Show TagsGreedy | ||||
| Bronze | Normal | Show TagsGreedy | ||||
| Bronze | Hard | Show TagsGreedy | ||||
| Bronze | Hard | Show TagsGreedy | ||||
| Bronze | Very Hard | Show TagsCasework, Greedy | ||||
| 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!