Someone mentioned in an answer that the following problem can be solved using only DFS/BFS: http://www.spoj.com/problems/PRATA/
I am not getting any idea on how to solve this problem without using Dijkstra’s algo/ MST. Binary Search is another approach. Can anyone tell how to solve this using only BFS/DFS?
Okay, I took a quick look. If there are any errors, I’ll fix them as soon as I wake up:
(Presuming different chefs can cook simultaneously.)
You’ve to pick P Pratas. Each time you’re assigning a Prata to a chef, you pick the chef which gives the next Prata earliest. Don’t view time as same for all, but store the internal time t of each chef, along with the time r to make their next Prata. With that notation, each iteration, you pick the chef with smallest value of t + r to make a Prata. Their own internal time then becomes t = t + r, and the time to make their next Prata becomes r = r + R. The maximum value of t + r that you picked becomes your answer.
I don’t know why you ask for “only BFS/DFS” if you can find an efficient solution elsewhere.
EDIT: Struck me as soon as I pressed submit, and then I also found this on the main discussion channel. The solution removes the ln(L) factor from my solution (assuming priority queue is used with mine). It’s practically the same thing with the ranks coalesced together.
Hope that helps. Cheers!