Organizing Containers of Balls

Sort by

recency

|

612 Discussions

|

  • + 1 comment

    Here is my C# solution.

    In short, we calculate sizes of containers and count of balls of each type. And then, for each type of balls we try to find a container of appropriate size. If we can do this we succeed, otherwise we fail.

    static bool OrganizingContainersCore(List<List<int>> containers) {
        // containers: size of container -> count of that size
        Dictionary<int, int> containerInfo = new();
    
        // balls
        int[] balls = new int[containers.Count];
    
        foreach(var container in containers) {
            int containerSz = 0;
    
            for(int j = 0; j < container.Count; j++) {
                int num = container[j];
                balls[j] += num;
                containerSz += num;
            }
            containerInfo.TryGetValue(containerSz, out int count);
            containerInfo[containerSz] = count + 1;
        }
    
        // compare
        foreach(int ballCount in balls) {
            if(!containerInfo.TryGetValue(ballCount, out int b))
                return false;
    
            if(b > 1)
                containerInfo[ballCount] = b - 1;
            else
                containerInfo.Remove(ballCount);
        }
        return containerInfo.Count == 0;
    }
    
  • + 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'