MAGICJAR - EDITORIAL

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Akil Vohra
Tester: Alexey Zayakin and Yash Chandnani
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Observation.

PROBLEM:

Given the number of jars required by N junior chefs for keeping ingredients which they may take in any order, find out the minimum number of jars required so as to ensure every chef can complete his recipe. It is to be noted that once a chef completes his recipe, he puts back the jars for reuse by other chefs.

QUICK EXPLANATION

  • The worst case would be when each chef has taken one less than the number of jars required to complete their dish and no jar is left. So one more than that number of jars is the required answer.
  • In the worst case, the number of jars taken is \sum x - N. So, the required answer is \sum x- N+1 as by that last extra jar, at least one chef shall complete his dish and put back jars used by him for others.

EXPLANATION

Quick Explanation said it all.

We need to think what can be the worst case, where the maximum number of jars are used and yet chefs are unable to complete their dishes. It happens when all chefs are one short of their jar requirement.

Since once any chef completes his dish, the jars are available for reuse. So, the worst case shall not have any chefā€™s dish already completed. So, now, we need to find the maximum number of jars such that each chefā€™s dish isnā€™t ready, but using a maximum number of jars.

Thatā€™s it. For chef requiring x jars, we can block x-1 jars. So, the Maximum number of jars such that no dish is complete is \sum (x-1). Now, to break this deadlock, we need one more jar. Hence, the required number of jars is \sum x - N+1.

Click to view

PS: Another one of my quick editorial xD. @vijju123, you might want to have a look here.

Time Complexity

Time complexity is O(N) per test case.

AUTHORā€™S AND TESTERā€™S SOLUTIONS:

Setterā€™s solution
Testerā€™s solution
Editorialistā€™s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

2

ā€œAt any time, if ai<Ai for each chef i that has not prepared their dish yet, the cooking session is a failure.ā€
If at any point you are giving someone Ai-1 jars then ai<Ai. Does this not make the cooking session a failure?

1 Like
3

at any time, if ai < Ai for ā€œeach iā€ =>> that is at any time if all of the cooks have less than required resources then cooking session will failā€¦check the editorial again, the current solution will make sure that even in the worst case at least one cook have the required resources always to complete its cooking.

4

Hello Sir,any order means any one of the permutation of the given N junior Chefs.please let me know if my understanding is wrong

5

where is the rest of editorials ? @taran_1407

6

I lovedddd this question a lot!!!

I cannot believe thisā€¦a few days before my operating systems sir teach me deadlock and oh great god i applied it to the problem and got an 100% points!!!

the editorial is as usual lovely <3 and this line " Now, to break this deadlock, we need one more jar." is pure love <3 :smiley:

thank you for your wonderful editorials @taran_1407 !! also, can you please tell when guessrt editorial will come? I try so hard but cannot do it :frowning:

7

Consider the following test case: 1 4
If the second chef takes all 4 jars, cooks his dish, keeps them back and then the first chef takes only one of these, does this not violate the condition that āˆ‘ai=J.

8

Scheduler will not give less resources when there are enough for one process demand
Regards
Samuel

9

I donā€™t understand this task at all.

I mean I understand the solution, I just donā€™t understand why that solution is the way it is.

Like, what dictates how many jars that the chefs need ?

I just donā€™t get it and Iā€™m really, really frustrated that I donā€™t get it.

ā€œThe junior chefs take some jars; letā€™s denote the number of jars taken by the i-th chef by ai. Any distribution of jars such that 0ā‰¤ai for each valid i and āˆ‘Ni=1ai=J is possible.
At any time, if ai<Ai for each chef i that has not prepared their dish yet, the cooking session is a failure.
Otherwise, one of the chefs who have at least as many jars as the number of required ingredients prepares their dish and returns their jars to the kitchen.
Whenever some jars are returned to the kitchen, they are immediately taken by some chefs that have not prepared their dishes yet (possibly all the jars by one chef).
This process continues with chefs taking jars, cooking their dishes and returning jars, until no chef can cook their dish anymore or all chefs have cooked their dishes.ā€

I donā€™t get this part at all ,in any single possible way, how am I supposed to conclude how many jars are the minimum ??

The test cases donā€™t provide that, from a blind perspective, you need as many jars as the guy that requires the most jars, I donā€™t get how, letā€™s say 10 chefs need 28 jars, but 19 is somehow the solution, when if we follow the logic of ā€œChefs will return their jars when they finishā€ then the answer should be the amount of jars that the most demanding chef needs, for example if my most demanding chef needs 8 jars, then the answer should be 8, but itā€™s notā€¦ Why ?
If all the chefs return their jars, then if 10 chefs needs jars in this order : 2,4,6,8,2,2,1,1,1,1

Then the answer through some stupid logic should be 8, since all of the chefs will just return the jars when they finish, and the most demanding chef needs 8 of them, but the answer here is 19. Why would any chef need 19 jars ?

Also your solution links donā€™t work so I canā€™t even solve whatā€™s wrong with my problem.

10

You might want to search for the concept of deadlock. Deadlock concept is frequently discussed in OS course. The basic funda is that, say each of N checks need A_i jars. Now, if we have \sum (A_i-1) jars, then there exists a configuration (or deadlock) where none of the chefs can proceed. However, if we add 1 more jar, we can prove that at least 1 of the chef will have his requirement fulfilled and will proceed (Hint: (A_i-1)!!). This frees more jars for other Chefs to use and hence is the minimum number of jars to guarantee avoiding a deadlock.

11 
Why would any chef need 19 jars ?

The basic idea is, ā€œIf there exists a configuration where NO CHEF can proceed, then you need to increase jars.ā€

With 8 jars, there is such a deadlock.

12

Scofield11
I exactly did the same thing as you did, i.e just gave the max number of jars as the answer which is wrong and Iā€™m very much frustrated as you did and you did a great job in asking your viewā€¦Thanks for that.

VIJJU123
But after reading your solution i found my mistake, ā€œthe chefs are not willing to share their jars among themselvesā€ so if there are just the number of jars needed by the chef with most demand that now doesnā€™t make senseā€¦ so just like no process can proceed in the OS ,no chef can cook their dish and this brings to the worst case where at least one of the chef could complete their tasks which is just one more than sum(ai)-N.
THANK you very much sir.

13

Hello VIJJU123 sir ,may i know the book name where the scheduler allaocates the less resources when there are enough resources,please help me i want to learn

14

Sum(ai) == J is only valid for initial distribution. In the given example req: 1 4 and the initial distribution will be 0 4 which is equal to J(4).

15

I think you should give Bankerā€™s algorithm a read. This is frequently asked in exams like GATE etc.

16 
"the chefs are not willing to share their jars among themselves

Take it as, as long as the process is running (i.e. Chef is cooking), he will not give his jar to some other Chef. Once he is done and jars are returned to common shelf, other Chefs can take it.

 just one more than sum(ai)-N

I also said that this is the answer. Read my first comment from second line.

17

Hello VIJJU123 sir ,thanks for your guidence, Bankers is for Dead Lock Avoidance,in our problem we are not considering ingrediants(sugar,saltā€¦) so NO resource type.If i take the MAX value in the set of request ,that satisfies allocation condition for the First request,in any order
example:-2,4,6,8,2,2,1,1,1,1 ;MAX=8

18

Read this of the problem statement-

the kitchen initially so that the session would be successful regardless of how the junior chefs pick up the jars.

If you take just max number of jars, there will exist a configuration where a deadlock happens. In fact, such a question has also came in GATE exam, where it said that 3 processes required 4,5,4 tapes respectively - then what is the minimum number of tapes needed to avoid deadlock regardless of distribution of resources.

Ans was (4-1)+(5-1)+(4-1)+1=11 with same logic as in editorial.

19

Hence, the basic concept is that, there exists a worst case configuration where each chef takes A_i-1 jars (where he needs A_i jars to complete cooking) and now a deadlock happens. However, if we add 1 more jar, then at least one of the Chef can now proceed with cooking, finish it, and thus freeing more jars for other Chefs to use. Hence \sum(A_i-1)+1 is the minimum jars needed so that deadlock never happens no matter how the jars are picked by the junior Chefs.

20

Sir then this is least upper bound sir,why they ave asked minumum number of jars