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.
1 Like
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.
1 Like
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.
1 Like
yeah at first it seems like what the hell is going on, the answer seem the maximum of all elements in the array of ingredients.
but the things become clear if you look at question again.
it says that junior chefs take the jars simultaneously not optimally
so if one wants the session to be successful the process shouldnât halt in any arrangement of the total number of jars.
so given no chef takes more than they required and return the jars once they had done preparing .
so the worst scenario where they could come to halt is when each chef has
one less than they require no. of jars (x-1).
so to put such a deadlock to end we need just one more jar to keep the session going.
I thought we just need to find maximum of all the elements in array
Because suppose the ingredient array is [1,4,3,2]
Then simply a2 takes 4 jars ,uses it and returns it .
Now again the available jars are 4 so a3 can use it and then return it.
Similary at every point number of jars available would be enough for everyone to cook their dishes. Plus 4< 7(actual answer).
Tell me if I have misinterpreted the question or if anything is wrong?
As a reminder of the deadlock concept, it is a great problem.
I disliked so much the example.
While I was reading the problem, I was building up the the solution, I was pretty sure it was related to the deadlock issueâŚ, but the example nuked it all.
All of the explanation of the juniors competing then switched to âOne of the junior chefs always picks up the only jar, cooks their dish and returns the jar back to the kitchen. Then, another junior chef picks up that jar, cooks their dish and returns the jar. This procedure can be repeated by each junior chef so that they can cook their recipeâ.
Although it does not contradict the deadlock procedure, the way it was described can be easily interpreted as a harmonious process too, nuking the prior guesses at worst or being a futile example at best.
I fully understand that this type of problem needs to be analyzed, but this example seemed pernicious to me. Examples are meant to illustrate, not to confuse.
Yes, you got it wrong, but donât worry, that was the catch.
The key statements were when, in the description of the problem, chaef had to cancel the session because juniors picked up the jars chaotically. You need a quantity âregardless of how the juniors pick up the jarsâ.
According to your interpretation, you assume that a2 picked up 4 jars. So your solution works only for that only scenario: everyone else lets a2 pick up the jars and waits.
You needed to think of a solution that avoids they locking each other. On that example you say, for all the amounts between 0 and 6 jars has a RISK of locking, i.e.:
If 1, a2 takes it and blocks others.
If 2, a2 takes one and a3 takes the another.
If 3, a2 takes them again
If 4, a2 takes 3 and a3 takes 2
If 5, a2 takes 2, a3 takes 2 and a4 takes 1
If 6, a2 takes 3, a3 takes 2 and a4 takes 1
You MOST avoid those risks.
But if you have 7, no matter how they take the jars, at least one will have all they need. If they end, they release which they were using, and let others complete their dishes.
The thing sum(Ai-1) points out the maximum number of jars that has risk to fail and block each other. But from sum(Ai-1)+1, all the risks are eliminated.