Editorial For ZIO-2018 Question 2
Editorialist: Akash Sharma
Prerequisite:
Basic Logical Math
Problem Description:
You are given B empty boxes each can hold at most 10 balls. You have many balls. Each ball has a colour. The colours are numbered from 1 to 12. You are given the count of balls of all 12 colours. You have to put all of the balls into B boxes, find the minimum number of boxes that contain balls of different types.
Explanation:
As we have to minimize the number of boxes that contain different balls, we try to fill the boxes with the same coloured balls first. We will put the balls which have their frequency greater than or equal to 10 first so that the number of boxes with all the balls of the same colour is maximized. In other words, for all the balls with a frequency greater than the capacity of the box i.e. greater than 10, we put 10 balls in a box and update the frequency of leftover balls and continue this until the frequency of balls of each colour becomes < 10.
Now, since all the balls have a frequency less than 10, we will put the balls in the order of maximum frequency first in an empty box (if any). Repeat this until all the boxes have some balls in them, i.e each box has now some balls in it.
This is because since all the boxes are non-empty (capacity<10), i.e. all the boxes have some balls in them, if some balls remain unused then we have to accommodate them into the used boxes. Note that, if a ball with a greater frequency is left then more boxes have to be used to accommodate that colour’s ball completely. On the other hand, if balls with lesser frequency are left then it can be accommodated is lesser number of boxes than the higher frequency one.
Also, when we try to merge/accommodate balls in used boxes, choose the box with maximum remaining capacity this is because when different types of balls are placed in a box it becomes impure, so try to fill maximum balls in that one box. By choosing the box with the maximum capacity we ensure that we can accommodate more remaining balls in it so there will be lesser or no balls left for other boxes to accommodate (in turn reducing the number of Impure boxes). If we choose some other box with smaller remaining capacity and remaining balls are to be placed in it then it will soon reach its remaining capacity and then the remaining balls need to be placed in some other box.
Lets try to understand this by an example,
[],[]
2 boxes of capacity 5 each
Frequency of balls: 1, 1, 2, 4
Increasing order of frequency:
[1],[]
[1],[1]
[1+2],[1] <= accommodating 2 in used box
[1+2+2],[1] <= 4 has now become 2 as 1 is accommodated in a used box
[1+2+2],[1+2]<=all done
Number of Impure Boxes=2
Decreasing order of frequency:
[4],[],
[4],[2]
[4],[2+1]<=Accommodating 1 in the box with the maximum remaining capacity
[4],[2+1+1]<=Accommodating 1 in the previously Impure box.
Number of Impure Boxes:1
Let us see why our algorithm is correct with the help of the below example-
Say we have 2 boxes and 3 balls-
- 9 red balls
- 7 blue balls
- 3 green balls.
If we put balls from order of least frequency to most frequency, that is, green to red, then we see we get no pure box.
However, if we put red first and green last, we can get 1 pure box with optimal placement.
So what happened?
In the first case, because we filled green balls first and then blue balls in the next box, we cannot accommodate red balls in a single box any more!
However, in the second case, we first put in red balls. Then we put in blue balls. We see that this arrangement forces green and blue balls in the same box! There is something which tells this is the right way to do it. Let’s try to prove it-
Let’s assume the method of filling the box with balls of max frequency is wrong. Meaning, I have an optimal solution where a Fi balls of colour Ci are filled in the box, instead of Fj balls of colour Cj and Fj>Fi.
Realize that if Fi balls are put in one box, we have Fj balls to put in another box, which can potentially make other pure boxes impure if I am forced to put them in non-full already pure boxes.
But since Fi and Fj are <10 (as we first make sure all freq are <10 before starting our greedy algo), we can put Fj balls instead of Fi balls in that box. Then we only need to adjust Fi balls in other boxes. Since Fj> Fi, this means we now have fewer balls to adjust which could make other boxes impure. Hence, this solution is better than the assumed optimal solution, hence a contradiction ==> Putting balls of highest frequency is optimal.
Test Case 1:
B = 11, A = [8, 22, 4, 4, 9, 18, 8, 7, 1, 5, 7, 5]
Steps:
Put balls of a single type in a single box until all boxes are full.
Fill those balls first which have number/frequency>=10
(This is done so that the number of boxes with the balls of a single type increases as if we put the balls in this order, this will ensure that the balls which can fill an entire box are selected first resulting in an increase of the number of boxes with single box type. )
Initial state of boxes:
[ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11
A = [8,22,4,4,9,18,8,7,1,5,7,5]
state of boxes:
[ 10 ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11
A = [8,12,4,4,9,18,8,7,1,5,7,5]
(Here: number inside box represent the number of balls it has of a single type)
(Here: 22 was used)
state of boxes:
[ 10 ], [ 10 ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11
A = [8,12,4,4,9,8,8,7,1,5,7,5]
(Here:18 was used)
state of boxes:
[ 10 ], [ 10 ], [ 10 ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11
A = [8,2,4,4,9,8,8,7,1,5,7,5]
(Here: 12 was used)
state of boxes:
[ 10 ], [ 10 ], [ 10 ], [ 9 ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11
A = [8,2,4,4,0,8,8,7,1,5,7,5]
(Here: highest was 9)
state of boxes:
[ 10 ], [ 10 ], [ 10 ], [ 9 ], [ 8 ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11
A = [0,2,4,4,0,8,8,7,1,5,7,5]
(Here: highest was 8)
state of boxes:
[ 10 ], [ 10 ], [ 10 ], [ 9 ], [ 8 ], [ 8 ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11
A = [0,2,4,4,0,0,8,7,1,5,7,5]
(Here: highest was 8)
state of boxes:
[ 10 ], [ 10 ], [ 10 ], [ 9 ], [ 8 ], [ 8 ], [ 8 ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11
A = [0,2,4,4,0,0,0,7,1,5,7,5]
(Here: highest was 8)
state of boxes:
[ 10 ], [ 10 ], [ 10 ], [ 9 ], [ 8 ], [ 8 ], [ 8 ], [ 7 ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11
A = [0,2,4,4,0,0,0,0,1,5,7,5]
(Here: highest was 7)
state of boxes:
[ 10 ], [ 10 ], [ 10 ], [ 9 ], [ 8 ], [ 8 ], [ 8 ], [ 7 ], [ 7 ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11
A = [0,2,4,4,0,0,0,0,1,5,0,5]
(Here: highest was 7)
state of boxes:
[ 10 ], [ 10 ], [ 10 ], [ 9 ], [ 8 ], [ 8 ], [ 8 ], [ 7 ], [ 7 ], [ 5 ], [ ]
1 2 3 4 5 6 7 8 9 10 11
A = [0,2,4,4,0,0,0,0,1,0,0,5]
(Here: highest was 5)
state of boxes:
[ 10 ], [ 10 ], [ 10 ], [ 9 ], [ 8 ], [ 8 ], [ 8 ], [ 7 ], [ 7 ], [ 5 ], [ 5 ]
1 2 3 4 5 6 7 8 9 10 11
A = [0,2,4,4,0,0,0,0,1,0,0,0]
(Here: highest was 5)
Now Put the remaining balls in any order. Once you put a ball in some box try to put remaining balls (if any) into the same box until that box is full (that is count=10).
Choose those boxes first which has more free spaces available.
(This is because as this box contain different types of balls we try to accommodate all the extra balls in that box until the max capacity is reached. This is done to minimize the number of boxes with different ball types.)
Free space can be calculated as:
Free space = 10- Occupied space
Initial state of boxes:
[ 10 ], [ 10 ], [ 10 ], [ 9 ], [ 8 ], [ 8 ], [ 8 ], [ 7 ], [ 7 ], [ 5 ], [ 5 ]
1 2 3 4 5 6 7 8 9 10 11
A = [0,2,4,4,0,0,0,0,1,0,0,0]
Space available = [0,0,0,1,2,2,2,3,3,5,5]
state of boxes:
[ 10 ], [ 10 ], [ 10 ], [ 9 ], [ 8 ], [ 8 ], [ 8 ], [ 7 ], [ 7 ], [ 5 ], [ 5+4 ]
1 2 3 4 5 6 7 8 9 10 11
A = [0,2,0,4,0,0,0,0,1,0,0,0]
Space available = [0,0,0,1,2,2,2,3,3,5,1]
(Here: maximum space available was 5)
(Here: BOLD box means the box which has more than 1 colour of balls)
state of boxes:
[ 10 ], [ 10 ], [ 10 ], [ 9 ], [ 8 ], [ 8 ], [ 8 ], [ 7 ], [ 7 ], [ 5 ], [ 5+4+1 ]
1 2 3 4 5 6 7 8 9 10 11
A = [0,2,0,3,0,0,0,0,1,0,0,0]
Space available = [0,0,0,1,2,2,2,3,3,5,0]
(Here maximum space available was 5)
(But we always choose those boxes which are already chosen, until they are full)
state of boxes:
[ 10 ], [ 10 ], [ 10 ], [ 9 ], [ 8 ], [ 8 ], [ 8 ], [ 7 ], [ 7 ], [ 5+3 ], [ 5+4+1 ]
1 2 3 4 5 6 7 8 9 10 11
A = [0,2,0,0,0,0,0,0,1,0,0,0]
Space available = [0,0,0,1,2,2,2,3,3,2,0]
(Here maximum space available was 5)
state of boxes:
[ 10 ], [ 10 ], [ 10 ], [ 9 ], [ 8 ], [ 8 ], [ 8 ], [ 7 ], [ 7 ], [ 5+3+2 ], [ 5+4+1 ]
1 2 3 4 5 6 7 8 9 10 11
A = [0,0,0,0,0,0,0,0,1,0,0,0]
Space available = [0,0,0,1,2,2,2,3,3,0,0]
(Here maximum space available was 3)
(But we always choose those boxes which are already chosen, until they are full)
state of boxes:
[ 10 ], [ 10 ], [ 10 ], [ 9 ], [ 8 ], [ 8 ], [ 8 ], [ 7 ], [ 7+1 ], [ 5+3+2 ], [ 5+4+1 ]
1 2 3 4 5 6 7 8 9 10 11
A = [0,0,0,0,0,0,0,0,0,0,0,0]
Space available = [0,0,0,1,2,2,2,3,2,0,0]
(Here maximum space available was 3)
Write the answer as the number of Bold boxes.
Here in our case, it is 3.
Answer = 3
Test Case 2:
B = 13, A = [9, 14, 11, 9, 9, 6, 7, 5, 6, 7, 16, 14]
Steps:
Initial state of boxes:
[ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A = [9, 14, 11, 9, 9, 6, 7, 5, 6, 7, 16, 14]
state of boxes:
[10 ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A = [9, 14, 11, 9, 9, 6, 7, 5, 6, 7, 6, 14]
state of boxes:
[10], [10], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A = [9, 14, 11, 9, 9, 6, 7, 5, 6, 7, 6, 4]
state of boxes:
[10], [10], [10], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A = [9, 4, 11, 9, 9, 6, 7, 5, 6, 7, 6, 4]
state of boxes:
[10], [10], [10], [10], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A = [9, 4, 1, 9, 9, 6, 7, 5, 6, 7, 6, 4]
state of boxes:
[10], [10], [10], [10], [9], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A = [0, 4, 1, 9, 9, 6, 7, 5, 6, 7, 6, 4]
state of boxes:
[10], [10], [10], [10], [9], [9], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A = [0, 4, 1, 0, 9, 6, 7, 5, 6, 7, 6, 4]
state of boxes:
[10], [10], [10], [10], [9], [9], [9], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A = [0, 4, 1, 0, 0, 6, 7, 5, 6, 7, 6, 4]
state of boxes:
[10], [10], [10], [10], [9], [9], [9], [7], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A = [0, 4, 1, 0, 0, 6, 0, 5, 6, 7, 6, 4]
state of boxes:
[10], [10], [10], [10], [9], [9], [9], [7], [7], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A = [0, 4, 1, 0, 0, 6, 0, 5, 6, 0, 6, 4]
state of boxes:
[10], [10], [10], [10], [9], [9], [9], [7], [7], [6], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A = [0, 4, 1, 0, 0, 0, 0, 5, 6, 0, 6, 4]
state of boxes:
[10], [10], [10], [10], [9], [9], [9], [7], [7], [6], [6], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A = [0, 4, 1, 0, 0, 0, 0, 5, 0, 0, 6, 4]
state of boxes:
[10], [10], [10], [10], [9], [9], [9], [7], [7], [6], [6], [6], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A = [0, 4, 1, 0, 0, 0, 0, 5, 0, 0, 0, 4]
state of boxes:
[10], [10], [10], [10], [9], [9], [9], [7], [7], [6], [6], [6], [5]
1 2 3 4 5 6 7 8 9 10 11 12 13
A = [0, 4, 1, 0, 0, 0, 0, 0, 0, 0, 0, 4]
Free space can be calculated as:
Free space = 10- Occupied space
Initial state of boxes:
[10], [10], [10], [10], [9], [9], [9], [7], [7], [6], [6], [6], [5]
1 2 3 4 5 6 7 8 9 10 11 12 13
A = [0, 4, 1, 0, 0, 0, 0, 0, 0, 0, 0, 4]
Space available = [0, 0, 0, 0, 1, 1, 1, 3, 3, 4, 4, 4, 5]
state of boxes:
[10], [10], [10], [10], [9], [9], [9], [7], [7], [6], [6], [6], [5+4]
1 2 3 4 5 6 7 8 9 10 11 12 13
A = [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 4]
Space available = [0, 0, 0, 0, 1, 1, 1, 3, 3, 4, 4, 4, 1]
state of boxes:
[10], [10], [10], [10], [9], [9], [9], [7], [7], [6], [6], [6], [5+4+1]
1 2 3 4 5 6 7 8 9 10 11 12 13
A = [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 3]
Space available = [0, 0, 0, 0, 1, 1, 1, 3, 3, 4, 4, 4, 0]
state of boxes:
[10], [10], [10], [10], [9], [9], [9], [7], [7], [6], [6], [6+3], [5+4+1]
1 2 3 4 5 6 7 8 9 10 11 12 13
A = [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Space available = [0, 0, 0, 0, 1, 1, 1, 3, 3, 4, 4, 0, 0]
state of boxes:
[10], [10], [10], [10], [9], [9], [9], [7], [7], [6], [6], [6+3+1], [5+4+1]
1 2 3 4 5 6 7 8 9 10 11 12 13
A = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Space available = [0, 0, 0, 0, 1, 1, 1, 3, 3, 4, 3, 0, 0]
Write the answer as the number of Bold boxes.
Here in our case, it is 2.
Answer = 2
Test Case 3:
B = 13, A =[15, 9, 7, 22, 7, 21, 6, 4, 11, 8, 7, 5]
Steps:
Initial state of boxes:
[ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[15, 9, 7, 22, 7, 21, 6, 4, 11, 8, 7, 5]
state of boxes:
[10 ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[15, 9, 7, 12, 7, 21, 6, 4, 11, 8, 7, 5]
state of boxes:
[10], [10], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[15, 9, 7, 12, 7, 11, 6, 4, 11, 8, 7, 5]
state of boxes:
[10], [10], [10], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[5, 9, 7, 12, 7, 11, 6, 4, 11, 8, 7, 5]
state of boxes:
[10], [10], [10], [10], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[5, 9, 7, 12, 7, 1, 6, 4, 11, 8, 7, 5]
state of boxes:
[10], [10], [10], [10], [10], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[5, 9, 7, 12, 7, 1, 6, 4, 1, 8, 7, 5]
state of boxes:
[10], [10], [10], [10], [10], [10], [ ], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[5, 9, 7, 2, 7, 1, 6, 4, 1, 8, 7, 5]
state of boxes:
[10], [10], [10], [10], [10], [10], [9], [ ], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[5, 0, 7, 2, 7, 1, 6, 4, 1, 8, 7, 5]
state of boxes:
[10], [10], [10], [10], [10], [10], [9], [8], [ ], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[5, 0, 7, 2, 7, 1, 6, 4, 1, 0, 7, 5]
state of boxes:
[10], [10], [10], [10], [10], [10], [9], [8], [7], [ ], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[5, 0, 0, 2, 7, 1, 6, 4, 1, 0, 7, 5]
state of boxes:
[10], [10], [10], [10], [10], [10], [9], [8], [7], [7], [ ], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[5, 0, 0, 2, 7, 1, 6, 4, 1, 0, 0, 5]
state of boxes:
[10], [10], [10], [10], [10], [10], [9], [8], [7], [7], [7], [ ], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[5, 0, 0, 2, 0, 1, 6, 4, 1, 0, 0, 5]
state of boxes:
[10], [10], [10], [10], [10], [10], [9], [8], [7], [7], [7], [6], [ ]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[5, 0, 0, 2, 0, 1, 0, 4, 1, 0, 0, 5]
state of boxes:
[10], [10], [10], [10], [10], [10], [9], [8], [7], [7], [7], [6], [5]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[0, 0, 0, 2, 0, 1, 0, 4, 1, 0, 0, 5]
Free space can be calculated as:
Free space = 10- Occupied space
Initial state of boxes:
[10], [10], [10], [10], [10], [10], [9], [8], [7], [7], [7], [6], [5]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[0, 0, 0, 2, 0, 1, 0, 4, 1, 0, 0, 5]
Space available = [0, 0, 0, 0, 0, 0, 1, 2, 3, 3, 3, 4, 5]
state of boxes:
[10], [10], [10], [10], [10], [10], [9], [8], [7], [7], [7], [6], [5+5]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[0, 0, 0, 2, 0, 1, 0, 4, 1, 0, 0, 0]
Space available = [0, 0, 0, 0, 0, 0, 1, 2, 3, 3, 3, 4, 0]
state of boxes:
[10], [10], [10], [10], [10], [10], [9], [8], [7], [7], [7], [6+4], [5+5]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[0, 0, 0, 2, 0, 1, 0, 0, 1, 0, 0, 0]
Space available = [0, 0, 0, 0, 0, 0, 1, 2, 3, 3, 3, 0, 0]
state of boxes:
[10], [10], [10], [10], [10], [10], [9], [8], [7], [7], [7+2], [6+4], [5+5]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0]
Space available = [0, 0, 0, 0, 0, 0, 1, 2, 3, 3, 1, 0, 0]
state of boxes:
[10], [10], [10], [10], [10], [10], [9], [8], [7], [7], [7+2+1], [6+4], [5+5]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
Space available = [0, 0, 0, 0, 0, 0, 1, 2, 3, 3, 0, 0, 0]
state of boxes:
[10], [10], [10], [10], [10], [10], [9], [8], [7], [7+1], [7+2+1], [6+4], [5+5]
1 2 3 4 5 6 7 8 9 10 11 12 13
A =[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Space available = [0, 0, 0, 0, 0, 0, 1, 2, 3, 2, 0, 0, 0]
Write the answer as the number of Bold boxes.
Here in our case, it is 4
Answer = 4