Theoretical-Greedy

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

Task statement

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

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

(*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

Task statement

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

Task statement

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

3
1 1 10

Output of wrong_stollencut: 10
Correct output: 9

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 …

Comments

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)