×

# Help me with this graph problem

 0 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? asked 31 Dec '14, 21:54 6★ketanhwr 1.9k●3●18●44 accept rate: 15%

 2 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! answered 01 Jan '15, 00:25 0★idraumr 246●3 accept rate: 45%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,228
×727
×506
×165
×72

question asked: 31 Dec '14, 21:54

question was seen: 746 times

last updated: 01 Jan '15, 00:37