Help me with this graph problem.

general
, , , , ,
1

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?

1 Like
2

Are you sure there is a way to use MST in this problem?

3

There are only 8 ranks and chefs with the same rank are indistinguishable. So instead of L chefs, we can just say we have count[i] chefs of rank i.

For each rank i, we will get count[i] pratas at times i, 3i, 6i, etc.

So, we can just simulate the cooking with a Breadth First Search until we cook P pratas.

First initialize next_cooking_time[rank i] = i.
Number of pratas cooked = 0
while we are not done
   Find minimum next_cooking_time[i for in 1..8]
   number_cooked += count[best_rank]
   if number_cooked >= P
       Answer is next_cooking_time[best_rank]
   Update next_cooking_time[best_rank]

Since there is a constant number (8) of ranks, this algorithm works in O§.

PS: Note that with such a small number of ranks, using something like a priority queue is slower due to the constant factors.

2 Likes
4

Hello ketanhwr,

I read the problem and find that this problem can be solved using binary search …Submit it and Got AC. I will pasting link to my accepted solution at the end of this post .

How does this idea comes to my mind…

Think this way … Let us assume that T is the minimum time required to make P parathas . So , We can also make P parathas in T+1 minutes , T+2 minutes and so on but it is gurantee that we cannot make P parathas in T-1 minutes because otherwise T is not the minimum time in which we can make P parathas…

So what does this signifies … We can binary search over the time … and can check whether we can make P parathas in X minutes and cannot make P parathas in T-1 minutes then break this is the minimum time …else if we cannot make P parathas in given time then move to right side and else move to the left side …

Here is my code which does the following …

Look at this code fragment. high = 100000000 is set as an upper bound only …
Assuming that P >= 1.
Consider for now that you have a function check which only tells you whether you can make P parathas in given time X .

Hope you got the idea of binary search.

            int low,high,mid ;
			low = 1;
			high = 100000000 ;
			while(low<=high){

				mid = (low+high)/2 ;
				if(check(mid) && (mid == 1 || !check(mid-1)))
					break ;
				else if(check(mid))
					high = mid-1;
				else
					low = mid+1;
			}
			ans = mid ;

Let us discuss check function for now …

Here is my check function for the above code …

I have done thing but just check each cook can produce how many parathas in the given time and calculate the total count and compare it with P.

May be it seems complex as i used upper_bound function but it is very simple function .

bool check(int x){

	int total = 0;
	for(int i=1;i<=N;i++){
		total += (upper_bound(AP[A[i]]+1,AP[A[i]]+1+1000,x)-(AP[A[i]]+1));
	}
	return (total>=P) ;
}

Considering you are already familiar with this upper_bound function if you are not it is a variation of a binary search which always given iterator to the values which is strictly greater than the search value if present …

you can learn about this function here link

AP is nothing but a 2-D array which stores AP[i][j] stores how much does a cook having rank i takes to prepare j parathas only …

Hope you got the idea about the solution of this problem using binary search …

Here is my code link to the above problem code

Cheers coding and wishing you a very happy new year … :smiley:

Cheers to codechef …

3 Likes
5

He mentioned he already knew this approach…

6

I am so sorry i have not read that …

7

Thanx for this great solution i have not thought that way …

8

glad you enjoyed it :slight_smile:

9

Thanks a lot!

10

Thanks for this approach too (: