 # How To solve MAXIMIZE/MINIMIZE type of problems

I would like to understand the flow for solving 2 types of distribution :

1. Maximize the Minimum distribution of items ‘K’ among members ‘N’.

2. Minimize the Maximum Distribution of items ‘K’ among members ‘N’.

if available provide the link for Tutorial/editorial for this type of problems

1 Like

For Example :
Candies (K) - 313
Students (N) - 3

What will be distribution for Both cases.

Suppose there are 313 choclates (say - K) items. I want to distribute K items among 3 ( say - N) childrens. Such that :

1. The task is to minimize the maximum number of chocolate gifted to a child.
print - the minimum number of maximum chocolate a child get.

2. The task is to maximize the minimum number of chocolate given to a child.
print- the maximum number of minimum chocolate a child get

I don’t know proper proofs for these but I have some intuition.

1. To minimize the maximum number if chocolates given to a child you can first give each child \displaystyle \left \lfloor \frac{k}{n} \right \rfloor chocolates and give at most one of the remaining k \% n chocolates to any k \% n children.
Reasoning: If the child that has maximum number of chocolates has 2 or more chocolates more than the second maximum, that child can give some chocolates to someone else to get a better solution.
Answer: displaystyle \left \lceil \frac{k}{n} \right \rceil
2. To maximise the minimum number of chocolates, again, give each child \displaystyle \left \lfloor \frac{k}{n} \right \rfloor chocolates and the distribution of remaining chocolates does not matter.
Reasoning: Similar to previous one. If the second minimum child has 2 or more chocolates more than the minimum, that child with minimum chocolates can get some chocolates from someone else to get a better solution.
Answer: \displaystyle \left \lfloor \frac{k}{n} \right \rfloor