Combinatorics Algorithm

Question

I've come across an interesting programming problem that I can't seem to formulate a solution to. Suppose you have K balls of N different colors. You must partition all of the balls into as many groups as possible such that no two groups are the same. (Two groups are considered the same if they have the same number of balls of each color.) What is the maximum number of groups you can make?

constraints: 1<=K<=50, 1<=N<=14

To clarify: We would like an algorithm that takes in an array of integers >= 1. The size of the array is N and the sum of the values it contains is K. The algorithm should return the maximum number of groups.

Any ideas on an algorithmic approach to this problem?

Answer 1

After speaking with my professor again, I learned that this was an adaptation of an open.kattis.com problem.

The two are nearly identical, as any instance of the original problem can be solved by taking the prime factorization of N and treating each prime factor as a ball. For instance, 900 = 2^2*3^2*5*2, so the equivalent balls problem would be 2 2 2.

The given bounds were found using the max bound of 10^15. 2^50 > 10^15, so there can never be more than 50 factors, and multiplying the first 15 primes by each other also exceed 10^15, meaning there can be at most 14 groups.

The tradeoff between number of balls and number of groups was overlooked however, and that in my opinion makes the problem much easier to solve. For instance, if there are 14 groups, there will only be 1 ball in each group, while if there are 50 balls then they will all belong to the same group (this is due to the 10^15 constraints of the original problem)

With this new information I was able to solve the problem. I factorized N into a list of Primes as well as a list of all factors, and then used a multiple dimensional knapsack algorithm(if N has X unique prime factors, then the knapsack DP will be X+1 dimensional, where the first dimension is which item you are considering and each other dimension represents your remaining supply of a certain prime factor). Each factor of N would represent a potential item to take in the knapsack, with it's prime factorization being it's cost vector.

After doing this, the problem was still too slow on maximum cases, and one additional optimization was required. I found that an optimal solution always exists that uses as many single ball groups as possible. By creating as many 1 ball groups as possible in the beginning and solving the remaining subproblem, I was able to complete the problem in Kattis's time constraints.

My algorithm depends on two assumptions that I have proven:

1. If you can make X groups without using all of the balls, you can also make X groups using all of the balls. This makes knapsack solutions where you don't use 100% of the capacity valid. This assumption can be proven by taking all unused balls and adding them all to the largest group. This will create a group larger than any other, and hence it must be unique. This leaves you with the same number of groups, but all balls utilized.

2. there always exists an optimal solution using as many 1-ball groups as possible. This makes it possible to reduce the original problem into a subproblem solvable in the time constraint. This can be proven as well. Take any optimal solution. For any 1 ball grouping that does not exist, take a group containing that 1 ball, and move every other ball in that group to the largest group. This creates a solution with the same (optimal) number of groups, that also has as many 1 ball groups as possible.

My solution has a runtime of O(F(N)^2), where F(N) is the total number of factors of N.