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 …

Cheers to codechef …