13 September 2018: Greedy Algorithms

From UMCPC Wiki
Jump to navigation Jump to search

Elements of a Greedy Strategy

  1. Greedy-choice property: There is always an optimal solution that makes the greedy choice.
  2. Optimal substructure: Making the greedy choice leaves us with a sub-problem, and solving the sub-problem optimally gives us an optimal solution to the original problem.

Proving Greedy-Choice Property

The greedy problem-solving strategy often leads to very efficient algorithms, but proving the correctness of a greedy solution can be challenging. You should never waste time coding a solution that you haven't proved to be correct.

Proving the greedy choice is safe can usually be done with a greedy-substitution proof:

  1. Assume there is an optimal solution that does not include the greedy choice.
  2. Show that you can substitute in the greedy choice without making it any worse.

Planting Trees

https://vjudge.net/problem/Kattis-plantingtrees

N = int(input())
T = [int(t) for t in input().split()]

T.sort()
T.reverse()

ans = 1

for i, t in enumerate(T):
    ans = max(ans, i + t + 2)

print(ans)

Watering Grass

https://vjudge.net/problem/Kattis-grass

from math import sqrt

while True:
    try:
        n, l, w = map(int, input().split())
    except:
        break

    S = []

    for _ in range(n):
        x, r = map(int, input().split())
        if 2*r > w:
            x0 = max([0, x - sqrt(r*r - (w/2)*(w/2))])
            x1 = min([l, x + sqrt(r*r - (w/2)*(w/2))])
            S.append((x0, x1))

    S.sort()

    ans, R, i = 0, 0, 0

    while i < len(S) and S[i][0] <= R:
        nextR = 0
        while i < len(S) and S[i][0] <= R:
            nextR = max(nextR, S[i][1])
            i += 1
        if nextR > R:
            R = nextR
            ans += 1

    print(ans if R == l else -1)

Bank Queue

https://vjudge.net/problem/Kattis-bank

import heapq

N, T = map(int, input().split())

C = []

for _ in range(N):
    c, t = map(int, input().split())
    C.append((t, c))

C.sort()
C.reverse()

pq = []

ans = 0
i = 0

for t in reversed(range(T+1)):
    while i < N and C[i][0] >= t:
        heapq.heappush(pq, -C[i][1])
        i += 1
    if pq:
        ans -= heapq.heappop(pq)
    T -= 1

print(ans)