# Help me with this graph problem

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!

2 Likes