Solution logic to Organizing Containers of Balls question on Hackerrank

Question

I was solving this problem called Organizing container of balls on Hackerrank:

David has several containers, each with a number of balls in it. He has just enough containers to sort each type of ball he has into its own container. David wants to sort the balls using his sort method.

As an example, David has n = 2 containers and 2 different types of balls, both of which are numbered from 0 to n - 1 = 1. The distribution of ball types per container are described by an n x n matrix of integers, M[container][type]. For example, consider the following diagram for `M = [[1,4],[2,3]]:

[...]

David wants to perform some number of swap operations such that:

• Each container contains only balls of the same type.
• No two balls of the same type are located in different containers.

You must perform q queries where each query is in the form of a matrix, M. For each query, print Possible on a new line if David can satisfy the conditions above for the given matrix. Otherwise, print Impossible.

I tried various approaches to the solution and could not find one. Then I went to the discussion section of the problem and I found this approach -

1. Make a table of box totals (capacity of each box)
2. Make a table of ball totals (total quantity of each ball type)
3. Sort both tables
4. If they are identical print Possible, otherwise print Impossible.

I tried this and it works and passes all test cases. I just didn't understand the logic behind this algorithm that another user has mentioned. I just wanted someone to help me out with the logic for solving this problem and better solutions would also be very beneficial as I'm a beginner to this kind of problems.

The code I wrote for this is

def organizingContainers(container):
    print(container)
    
    countByType=[0]* len(container[0])
    countByContainer=[sum(x) for x in container]
    for Ci in container: 
        print ("Ci=", Ci)
        for j in range(len(Ci)):
            print(" j=",j)
            countByType[j]+=Ci[j]

    countByContainer.sort()
    countByType.sort()
    print('Count By Types:',countByType)
    print('Count By Container:',countByContainer)
    return "Possible" if countByContainer==countByType else "Impossible"

Answer 1

It is maybe not so evident from the description of the challenge that the containers can have different capacities. All the examples that were given had same-sized containers. To better grasp the problem, I find it useful to work with an example that has different sized containers:

         \ball types | red | blue | green
containers\          |     |      |    
---------------------+-----+------+-------
           A         |  2  |   3  |   1
           B         |  4  |   0  |   1
           C         |  1  |   3  |   3

So we have 3 containers (named A, B and C), and 3 types of balls (red, blue, green). Note that container B is the smallest: apparently it can contain 5 balls. A can contain 6 balls, and C can contain 7 balls.

A key observation is that if we first empty the containers and then freely distribute the balls over the containers, filling them again, there is always a way to achieve that same transition through mere swapping. You may need a moment to let this sink in and to verify this is indeed the case. But once you get this principle, you can just forget about the swapping part, and approach the problem from an angle where you first remove all the balls and then distribute them again.

So let's empty the containers. We then have the following balls "in our hands":

 red | blue | green
-----+------+-------
  7  |   6  |   5

Now ask yourself: if container B has a capacity of 5, which kind of balls would you put in there? Obviously the green balls. It wouldn't work with any other type of ball, since you would then have to put one or more of them in another container, which violates the requirements.

The general rule is thus: put the balls of which you have the least in the container that has the smallest capacity. If that number of balls doesn't match the capacity, then there is just no way to get to a solution. If it does match, then you can repeat this with the next kind of balls (in increasing order) and next container (in increasing capacity). And so you see that actually sorting the containers and balls like that is a way to find a solution.