determinism's blog

USACO 4.2 (IOI'96) — Job Processing
By determinism, history, 9 years ago, In English

I couldn't prove the greedy algorithm which is 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?

  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by determinism (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

One tip: use binary search when possible, so you can be sure that the solution is correct. For example, in this problem you can binary search for the ending time of A and B.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for nice tip.

    Btw, how do you use binary search for B part?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Indeed, B is trickier. One approach: for a fixed ending time x, assume that each machine B completes its last job at time x (if it processes any jobs), and a machine never waits between two jobs.

      → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I know this is sort of old, but.

    I don't understand, what can you use binary search for? Are you saying that you can write another program to test your original algorithm using binary search?

    Thanks

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think pllk is just saying that often it is difficult to prove a greedy algorithm, but proving a binary search algorithm is easier. In problems where time limit isn't a problem, it is better to go with a binary search algorithm you can prove, rather than a greedy which you aren't sure about.

      → Reply