Organizing Containers of Balls

Sort by

recency

|

611 Discussions

|

  • + 0 comments

    To make a container (row) of size N monochromatic, that row must retrieve N balls of the same color from a suitable source. A suitable source is any column of the container array that has at least N balls, because each column is monochromatic by the problem statement. But if all such suitable columns have more than N balls, then some other row will have to accept the surplus, making it polychromatic. Therefore, if a solution exists, it is necessary that every row have a unique counterpart column containing the same number of balls.

    Notice also that if every row has a unique counterpart column of the same size, then also every column has a unique counterpart row of the same size.

    Conversely, assuming every row has a unique counterpart column of the same size, every row can be made monochromatic. Indeed, say the counterpart of row i is column j. The balls corresponding to cell ij will not be swapped because they are already of the color of column j. The rest will be swapped with the balls from column j. But where will the balls from row i but columns other than j go? They will be in turn uptaken by the rows corresponding to these columns, by the assumprion.

    Thus, the problem has a solution if and only if each row has a corresponding column of equal size. Thus, if X is the array of row sizes, and Y of column sizes, for each i there must be a unique j such that X[i] = Y[j]. Since X and Y are arrays of the same length, this is equivalent to Y being a permuted copy of X, which in turn is equivalent to sorted array X being equal to sorted Y.

    def organizingContainers(container):
        l = len(container)
        X = [sum([container[i][j] for j in range(l)]) for i in range(l)]
        Y = [sum([container[i][j] for i in range(l)]) for j in range(l)]
        if sorted(X) == sorted(Y):
            return "Possible"
        else:
            return "Impossible"
    
  • + 0 comments
    def organizingContainers(container):
        # Write your code here
        colsum=[0]*len(container)
        rowsum=[0]*len(container)
        for i in range(len(container)):
            rowsum[i]=sum(container[i])
            for r in range(len(container)):
                colsum[r]+=container[i][r]
        if sorted(colsum) == sorted(rowsum):
            return 'Possible'
        else :
            return 'Impossible'    
            fptr.write(result + '\n')
    
        fptr.close()
    
  • + 0 comments

    Here is my Python solution!

    def organizingContainers(container):
        sizes = [sum(container[i]) for i in range(len(container))]
        types = max([len(container[i]) for i in range(len(container))])
        amounts = []
        for t in range(types):
            amounts.append(sum([container[i][t] for i in range(len(container))]))
        for amount in amounts:
            if amount in sizes:
                sizes.remove(amount)
                amounts.remove(amount)
            else:
                return "Impossible"
        return "Possible"
    
  • + 0 comments

    Python simply checking if a matching space container is there for every type of ball, worked out quite well, but I'm not sure about the complexities.

    This one doesn't require that much space so if anyone can tell me if and where I can improve heavily on time complexity:

    def organizingContainers(container):
        # Write your code here
        balls_in_container = sorted([ sum(container[i]) for i in range(len(container))])
        
        # count no of each type of ball
        n = len(container)
        freq_types = { x : 0 for x in range(n)}
     
        for i in range(n):
            for j in range(n):
                freq_types[j] += container [i][j]
        
        balls_types = sorted([freq_types[i] for i in range(n)])
        
        
        if balls_types == balls_in_container:
            return 'Possible' 
        else: 
            return 'Impossible'
    
  • + 0 comments

    For the solution I focused in the amount of spaces that each container has and the amount of balls per type that there needs to be. Because at the end of the day what is asked is that each type of ball can be in one container.

    the total capacity of a container is the sum of all the elements in the row

    the total amount of balls per type is the sum of each i'th element in each row.

    Then we would get, two lists, one that represents the amount of spaces that each container has, and the other one the amount of balls per type that we have. If we sort those lists and then check if they are equal, meaning that they have the same values on each position, is possible to swap the items between the containers and meet the requirements.