×

# MAGICJAR - EDITORIAL

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

Easy

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$.

View Content

# Time Complexity

Time complexity is $O(N)$ per test case.

# AUTHOR'S AND TESTER'S SOLUTIONS:

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

4.0k31104
accept rate: 22%

19.8k350498541

 1 "At any time, if ai> 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. (14 Feb, 15:59) 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. (15 Feb, 13:20) golovkin2★ 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). (16 Feb, 10:47)
 1 This problem was a test of english understanding skills rather than coding answered 20 Feb, 09:25 1.2k●12 accept rate: 18%
 0 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 link This answer is marked "community wiki". answered 14 Feb, 18:04 24●1●2●7 accept rate: 0%
 0 where is the rest of editorials ? @taran_1407 answered 14 Feb, 20:54 41●3 accept rate: 0%
 0 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 :D 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 :( answered 14 Feb, 23:19 35●2 accept rate: 0%
 0 Scheduler will not give less resources when there are enough for one process demand Regards Samuel answered 15 Feb, 17:01 24●1●2●7 accept rate: 0%
 0 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
 0 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. answered 16 Feb, 08:33 2★bncdq 1 accept rate: 0% "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. (16 Feb, 12:25)
 0 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 answered 16 Feb, 10:33 24●1●2●7 accept rate: 0% I think you should give Banker's algorithm a read. This is frequently asked in exams like GATE etc. (16 Feb, 12:24)
 0 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 answered 16 Feb, 17:38 24●1●2●7 accept rate: 0% 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. (16 Feb, 19:51) 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. (16 Feb, 19:52)
 0 Sir then this is least upper bound sir,why they ave asked minumum number of jars answered 17 Feb, 14:00 24●1●2●7 accept rate: 0% Have you even read the question carefully? the kitchen initially so that the session would be successful regardless of how the junior chefs pick up the jars. MINIMUM jars such that all chefs complete cooking REGARDLESS of how they pick jars, which is equal to the least upper bound. (17 Feb, 14:36)
 0 Please confirm my understanding : The distribution of jars is random, like, we can't guarantee that who will get how much, so we choose a minimum number such that whatsoever the distribution, the session ends successfully. The max logic is faulty as it will only work if chefs cooperate among themselves, or the maxm demanding chef can obtain all those jars for himself which is not guaranteed. answered 24 Feb, 23:45 1 accept rate: 0% Yes.. Perfect. (25 Feb, 01:38)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,852
×3,820
×268
×189
×13