*Written by Bibin Muttappillil.*

Contents

*What is greedy?*
The greedy approach is used to solve optimization problems by choosing the *locally* best option. *Best* is often defined by the problem statement (e.g. maximizing a sum or minimizing a cost).
*Locally* means that at each decision point (e.g taking, disregarding or choosing) we only consider the current state and choose the option which would give us the best result immediately after this decision.

This approach often makes sense intuitively and can work on small cases, but there are problems in which this approach doesn’t work. So if it works then the argumentation that we have the optimal solution just because we took the best option at each step doesn’t suffice. Usually the idea of the greedy algorithm is simple, but to reason about its correctness is not.

## Why greedy doesn’t work

## Why greedy could work

Strategy a) assume greedy approach is wrong b) look where the optimal solution would differ c) show that we can ‘exchange’ some things to make the greedy algorithm better or equally good as the optimal solution

We will look at three examples to see how we can use this strategy to reason the correctness of the greedy approach.

## Task: concierge

// solves the task with `a_i` as an input array void solve_concierge(int[] a): int N = a.size() // the rooms that are available set<int> rooms = {1, 2, ..., N} // participant i will have room room_assignment[i] int[] room_assignment = {0, ..., 0} // with size = N for i in {0, 1, ..., N-2}: // the time we have until the next participant int time = a[i+1] - a[i] /* * We assume that we already proved * find_room_in_time (basically a binary search). * find_room_in_time returns the farthest away (available) room * where the round trip is <= time * meaning 2*r <= time */ int r = find_room_in_time(time/2, room) // when there is no reachable room available if r == -1: print("IMPOSSIBLE") exit() assignment[i] = r rooms.remove(r) // set of rooms has only one element left room_assignment[N-1] = rooms[0] for r in room_assignment: print(r + " ")

The crucial observation here is to see that we should always take the room with as high of a number as possible but which still allows the concierge to reach the next participant. The intuition is that having rooms with faster access is always better.

`"POSSIBLE"`while correctly it would be impossible or

`"IMPOSSIBLE"`while there actually exist a solution.

`find_room_in_time()`in the code, where we definitely take a room to still reach the next participant or we say

`"IMPOSSIBLE"`in which we are in the other case.

`"POSSIBLE"`then it actually is possible.

- either we reach the last room and then our assumption that a optimal solution and the greedy differs is wrong \(\Rightarrow\)
*contradiction* - or we reach a point where our greedy solution didn’t find a room, but then an optimal solution also can’t find a room (as we have the same set of rooms left) \(\Rightarrow\)
*contradiction*.

`"IMPOSSIBLE"`then it actually is impossible.

(*Note: ‘Repeating the same argument’ is a bit fuzzy. To be more precise we would have to do induction. We left it out for clarity and to be more concise)

This would be a sufficient reasoning for the SOI. QED

## Task: binge

// solves the task with `a_i, b_i` as an input array of pairs solve_binge( (int, int)[] shows ): int N = a.size() sortByEndingTime(shows) int result = 0 int currentTime = 0 for (start, end) in shows: // if the show doesn't overlap with the last if start >= currentTime: // select (greedily) the current show currentTime = end result++ print(result)

## Task: stollencut subtask 6 (2P 2019)

There are several ways to attack this problem, one of them is greedy. Be careful though some greedy approaches are right and some are not.

A wrong greedy solution:

// tries to solves the task // with `d_i` as an input array and K = 2 wrong_stollencut(int[] d): int sum = sum(d) // try to cut the stollen in perfect thirds // keep rounded up and down solutions int (a_l, a_r, c_l, c_r) = partition(d) // calculate all 4 cases: int case1 = max_diff(a_l, sum - a_l - c_l, c_l) int case2 = max_diff(a_l, sum - a_l - c_r, c_r) int case3 = max_diff(a_r, sum - a_r - c_l, c_l) int case4 = max_diff(a_r, sum - a_r - c_r, c_r) // take the smallest case int result = min(case1, case2, case3, case4) return result partition(int[] d): int i = 0 int a_l = 0 int a_r = 0 // a_l <= sum*1/3 < a_r while a_r <= sum/3: a_r += d[i] i++ a_l = a_r-d[i] int c_l = 0 int c_r = 0 // check c_l <= 2/3*sum < c_r while 3*c_r <= 2*sum: c_r += d[i] i++ c_l = c_r-1 return (a_l, a_r, c_l, c_r) int max_diff(int a, int b, int c): return max(a, b, c) - min(a, b, c)

This seems like a reasonable idea but it would solve this example wrong

Input:

3 1 1 10

Output:

Output of wrong_stollencut: 10 Correct output: 9

Comment:

Such a thing is called a counter example. A correct algorithm doesn’t allow for a counter example. A good reasoning makes it clear why such a counter example is impossible.

A correct greedy solution:

// solves the task // with `d_i` as an input array and K = 2 solve_stollencut(int[] d): int (a_l, x_l, a_r, c_l, c_r) = partition(d) int case1 = solve_right_bound(d, a_l) int case2 = solve_right_bounf(d, a_r) int case3 = solve_left_bound(d, c_l) int case4 = solve_left_bound(d, c_r) int result = min(case1, case2, case3, case4) print(result) // find the best second bound // if the first is given // by iterating through every possibility int solve_right_bound(int d[], int left): int N = a.size() int sum = sum(d) int a = 0 int i = 0 while a != left a += d[i] i++ int result = inf while i < N b += d[i] c = sum - b - a result = min(result, max_diff(a, b, c)) i++ return result // solving from right to left // is the same as reversing it // and then from left to right int solve_left_bound(int d[], int right): int[] reversed_d = reverse(d) return solve_left_bound(d, d.size()-1-right)

*comming soon: a correct reasoning …*

## Practice

Here are some problems where you can try to solve them on your own. You can find these problems in our Task Archive.

- Allotment (2T 2018)
- Sushi (First round 2018)
- Cheese Recommendation (2T 2019)