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?
Auto comment: topic has been updated by determinism (previous revision, new revision, compare).
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.
Thanks for nice tip.
Btw, how do you use binary search for B part?
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.
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
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.