You are not logged in. Please login at www.codechef.com to post your questions!

×

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?

asked 31 Dec '14, 21:54

ketanhwr's gravatar image

6★ketanhwr
1.9k31844
accept rate: 15%


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!

link

answered 01 Jan '15, 00:25

idraumr's gravatar image

0★idraumr
2463
accept rate: 45%

edited 01 Jan '15, 00:37

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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