USACO 4.2 (IOI'96) — Job Processing

Revision en2, by determinism, 2015-07-02 16:03:09

I couldn't prove the greedy algorithm which used in the A part of this problem, so I looked it up on the internet and found this. There is a proof there, but I think that it's incomplete. Specifically, it doesn't prove subproblem needs to be solved optimally for problem to be solved optimally. Thanks for help in advance.

Also, I'm really bad at greedy algorithms. Is there any text on proof techniques for greedy algorithms, must-solve problems, or other important stuff on greedy algorithms you know?

Tags greedy, ioi

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English determinism 2015-07-02 16:31:26 3 Tiny change: 'thm which used in t' -> 'thm which is used in t'
en2 English determinism 2015-07-02 16:03:09 71
en1 English determinism 2015-07-02 16:02:37 612 Initial revision (published)