I have n boxes n <= 100. There are k fruits k <= 6 , which will be inserted one by one. each fruit will be putted into the different boxes. for each fruits there will array of zeros and ones where 1 represents that box contains this fruit and zero means that it doesn't contain fruit.

I have to find out how many minimum boxes do I need to uniquely identify the given fruits.

For example : lets say there are 2 fruits and 9 boxes.

Box No's: 1 2 3 4 5 6 7 8 9

Fruit A : 1 1 1 1 0 0 0 1 0

Fruit B : 1 0 0 0 1 0 1 1 1

If we choose box such as 2,3,4,5,7,9 any one of them can uniquely identify the given fruits because one exist and other don't. So answer here is 1.

Lets add another fruit here C:

0 1 0 1 1 1 1 0 1

If you choose any of the above boxes , then you will have conflict and cannot uniquely identify the given fruits.So you will need another box here. Minimum Answer would be 2 here.

So far I have done that for each box i will put it into the box. then for all boxes we will have some set , element in it say that there is fruit[i] in it.

So I would have to find out minimum boxes such that if we take subset of those and do intersection of that subset and intersection comes out to be fruit[i] then we can uniquely identify that given fruit.

But I am stuck on how would I find the minimum boxes .

Can anyone tell whether even my approach is right or wrong ?

Any help or algorithm or any other approach to solve this problem.

Thanks in advance.

You have N toffee packets, each containing different number of toffees. The number of toffees contained in the ith packet is denoted by a[i]. You need to put these toffee packets in M boxes such that each box contains at least one toffee packet, and the maximum number of toffees in a box is minimum. You can only choose consecutive toffee packets to put in a box.

N,M <= 10^5. a[i] <= 10^3. Time Limit : 1s.

Input : 4 2 10 3 5 7

Output: 13

Explanation : Below are the possible assignments of toffee packets to boxes. 10 [3 5 7] 10 3 [5 7] 10 3 5 [7] For minimizing the maximum number of toffees in a box, we choose the second assignment, and hence the output should be 13.

Can anyone can explain me the logic or data structure , algo behind it to solve it ?

Thanks In Advance.

There are n classes in which there are a1,a2,..an students in each class. You have given b cakes (b >= n) , you have to divide the cakes in each class such that the number of students per cake in each class is minimum and each class should have atleast 1 cake in it. You need to find the maximum number of students per cake in any class such that cakes are divided in each class optimally. How should I approach? First I give 1 cake to each class. Then I left with b-n cakes , how one should distribute it optimally ?? Lets say I give x1 cakes to class 1 and x2 to class 2 and so on such that x1+x2+..+xn = b and ans = find max( a1/x1 , a2/x2 ,...,an/xn) Sample Input 1 2 7 20 50 ans = 10 , I give 2 cake to class 1 and 5 cake to class 2. Sample Input 2 6 7 1 1 1 1 1 10 ans = 5 , I give 1 cake to first 5 class and then 2 to last class , so ans = 10/2 which is maximum . Thanks for any solutions.