chef and magic jars

This problem is just referring to the same concept as that of the Deadlock Prevention Questions of Operating System. Here the Chefs can be understood as the Processes and the Jars can be considered as the Resources, that's it. This whole calculation can be done with the help of the function.

That is, R(no. of resources) > Total Demand - n( No. of Processes) --- For No Deadlock

and the opposite for a deadlock to occur, here deadlock means that the Cooking won't be successful.

I think the idea should be  thought of without considering the formula for the first time, and after a satisfactory amount of thinking you can consider the form. cause then things will be more clear.

The idea is just based on the corner case where everything bad happens and all the processes make decisions that lead to a Deadlock. That's it!

                                                 Also when my code Fails ... after decades of thinking ;(

Problem Statement:-

Chef decided to teach some advanced recipes to junior chefs. On the very first day of their cooking sessions, to identify the cooking abilities of each junior chef, Chef instructed them to make their premier dishes. The junior chefs were very excited and they all went into the kitchen to cook their dishes.

Chef has a limited number of jars in the kitchen. The jars are magical ― if a chef that is cooking a dish requiring $�$ ingredients takes $�$ jars, each of these jars fills itself with one of the required ingredients, and after this chef finishes cooking and returns the jars to the kitchen, they empty themselves (and are ready for other chefs to take some or all of them). Of course, this means it is impossible to cook a dish requiring $�$ ingredients with less than $�$ jars.

Since Chef did not tell the junior chefs in which order they should prepare their dishes, they started picking up jars simultaneously and in the end, no junior chef was able to acquire enough jars to prepare their premier dish. Also, none of the junior chefs are willing to lend their jars to others. Chef was unable to handle the situation and decided to call off the cooking session for that day, so that he could get more jars and try it again later.

You know that there are $�$ junior chefs (numbered $1$ through $�$) and for each valid $�$, the number of ingredients required for the dish of the $�$-th chef is ${�}_{�}$. If there are $�$ jars, then formally, the following process happens:

• The junior chefs take some jars; let's denote the number of jars taken by the $�$-th chef by ${�}_{�}$. Any distribution of jars such that $0\le {�}_{�}$ for each valid $�$ and ${\sum }_{�=1}^{�}{�}_{�}=�$ is possible.
• At any time, if ${�}_{�}<{�}_{�}$ for each chef $�$ 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.
• When all junior chefs have successfully cooked their dishes, the cooking session ends successfully.

Chef wants to know the minimum number of magical jars that should be present in the kitchen initially so that the session would be successful regardless of how the junior chefs pick up the jars. Chef is a legendary cook, but he is not very good at mathematics, so he asks you to find that number.

Input

• The first line of the input contains a single integer $�$ denoting the number of test cases. The description of $�$ test cases follows.
• The first line of each test case contains a single integer $�$.
• The second line contains $�$ space-separated integers ${�}_1,{�}_2,\dots ,{�}_{�}$.

Output

For each test case, print a single line containing one integer ― the minimum required number of jars.

Constraints

• $1\le �\le 1,000$
• $1\le �\le 10^5$
• $1\le {�}_{�}\le 10^9$ for each valid $�$
• the sum of $�$ over all test cases does not exceed $10^6$

Subtasks

Subtask #1 (100 points): original constraints

Sample 1:

Input

Output

2   
4   
1 1 1 1   
2   
1 4

1   
4

Explanation:

Example case 1: 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.

Code Implementation:-

for _ in range(int(input())):

    n=int(input())

    nums=list(map(int,input().split()))

   

    # We can comment the below 4 lines if we use the last Line of the Code

    ans=0

    for num in nums:

        ans+=num-1

    print(ans+1)

   

    # But the below line, uses 0.01s more than the above approach

    # print(sum(nums)-n+1)

Explanation:-

Simply, this problem can be understood if we consider the scenario of the processes in Operating System. In the Topic of Deadlock very similar requirement is there in which we usually have to find out the minimum number of resources that will be required so that we don't have a deadlock. So, the very simple idea here is that, we consider a simple example of 3 processes each requiring 2 resources, now we can say that we will just require 2 resources, like each process will use them and then give the resources to the other processes, there's a big but here, what if these 2 resources are taken by 2 processes, means each process takes 1 resource and so we come across a Deadlock, we just have to consider this corner case and remove the Deadlock. Now let's assume we take 3 resources, but still if each process takes 1 resource so all have 1 each, again a Deadlock, now let's take 4, here there can never be a Deadlock bcz even if we divide 1 among each then also there's a resource left which will make a process execute for sure and thus there won't be any Deadlock. The key takeway is that we give each process (whatever it requires -1) and then the (summation of this for all the process+1) is the minimum number of resources required for Deadlock to be avoided at all costs. The last line just subtracts the ones in the form of n at once from the total demand. And so for Deadlock to be avoided the R(no. of resources required) should be just greater than this (means just +1).