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:

1 Like
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

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

4

where is the rest of editorials ? @taran_1407

5

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:

6

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

7

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.

2 Likes
8

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.

9

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

10

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

11

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

12

This problem was a test of english understanding skills rather than coding

1 Like
13

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.

2 Likes
14

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.

15

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.

16

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.

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

2 Likes
18

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

19

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

20 
"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.