How To solve MAXIMIZE/MINIMIZE type of problems

tutorial
1

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
2

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

What will be distribution for Both cases.

3

Please help anyone!!!

4

Unable to understand your query.

5

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

6

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