First subtask was very easy and for second substask all chef were able to prepare same number of dishes per minute so problems becomes same as finding minimum number of chefs required to finish orders. if x chefs can complete task then answer is sum of x-minimum salaries from salary of chef array. So I sorted all tasks by their deadlines and scheduled them for x=1 to k number of chefs. In second subtask one test case gave AC and second test case gave WA. Here is my Solution. Can anyone find error in solution or give counter test case.
1
4
10 1
10 2
10 3
10 4
3
10 1
10 2
40 4
Your output : 6
Correct output : 3 (1+2)
2 Likes
My scheduling method is wrong. Thanks.
I made the same error mate. 
1 Like
@ashutosh450 could u plz tell how to solve this for 40 points.
My approach was that i find the the dish which is given max time,then iterate time from 0 to maxtime with incr=1/P[0]. Then first assign cooks to orders which compulsarily requires cooks,if any remaining cooks then assign them any dish.
A friend of mine solved it for 40 points. He analysed and computed for one dish at a time and after every dish he sorted the array with respect to remaining time.
His solution : https://www.codechef.com/viewsolution/16464574
Can anyone please suggest any test case where my code was failing for 40 points?
For the above mentioned case by @ashutosh450 it works as expected.
Approach: Checked for 1 to k number of cooks one by one if they can complete the orders or not.
First sorted the dishes in order which requires highest efforts come first (BTW sorting won’t affect my approach to my understanding) then for each job one by one, started assigning the time (max 1.0) to dish starting from the max time dish for the particular dish and decrementing by one unit of time until either dish is completed otherwise deciding that order can’t be completed with current number of cooks.
INPUT:
1
3
3 1
3 1
3 1
3
3 1
4 2
7 3
YOUR OP
2
BUT it is 3…
EDIT:
oh…sorry, the answer is 2 only…
@arun_001, I am glad that you put your efforts for finding such test case but for the test case mentioned by you only 2 cook can also complete the order (ever order (3,1),(8,3),(4,2)). For your convenience check out below link for pictorial representation of scheduling for your case. I will be thankful if you can report other one also.
@quamruzz44
I think your program is not correct for the following input:
1
3
32 1
32 1
32 1
5
35 2
36 2
33 2
20 2
1 1
your output:
3
correct output:
2
Schedule
cook 1:
0…1/32 Task5
1/32…36/32 Task 1
36/32…64/32 Task 2 (incomplete 28 done, 8 remaining)
cook 2:
0…8/32 Task 2 (now complete - not overlapping with cook 1)
8/32…41/32 Task 3
41/32…61/32 Task 4
2 Likes
The idea to solve WESTAND (100pt) is quite simple (although implementation is not that easy):
Iterate through all subsets of cooks and check whether it is possible. For each subset do the following:
Iterate through tasks from latest beginning to earliest beginning.
Until the next (earlier) deadline comes into play the fastest cook cooks the order with the most dishes.
If two or more orders share the same number of dishes each dish can be proceeded with the average of the related cooks. It is possible if each order has remaining dishes=0 at time 0.
For example:
cooks with speeds 20 10
orders [time,dishes]: [54,5], [44,5], [49,3]
in the end there are orders 54,44 from time 5 down to 3.
The last second (4 - 5) the fastest is assigned to 54 dishes and second fastest is assigned to 44 dishes.
Now both have 34 dishes remaining. Then they are assigned both cooks half the time. From time 3-4 (1 second) both orders are reduced by 1*(20+10)/2 =15 dishes.
Therefore at 3 seconds we have remaining orders of 19 19 and 49.
Now the fastest is assigned to 49 dishes (speed 20) and there is only a single remaining cook for the other orders and this cook is split over them (speed 10/2). This proceeds for seconds 1-3. At time 1 all orders have 9 dishes left over. Therefore all three orders share the two cooks (speed (10+20)/3) and they finally finish at time 0.1 which is greater or equal zero. So we have a possible schedule!
In this solution all cut points where orders share same remaining dishes are eagerly calculated with Fractions of BigInteger.
After a little rethinking the solution can be formulated much easier by delayed merging of orders that share the same cooks: solution
5 Likes
my code is working for the above mentioned testcases .can anyone please provide any other testcase .Thanks in advamce
Link to my code https://www.codechef.com/viewsolution/16549372
INPUT:
1
3
3 1
3 1
3 1
4
9 3
6 2
6 2
3 1
YOUR OUTPUT :
3
BUT it is -1 ,
as
1st order by chef 1,
2nd by chef 2,
and 3rd by chef 3,
So 4th can not be completed in time…as no two chefs work on a dish simultaneously