We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Organizing Containers of Balls
  5. Discussions

Organizing Containers of Balls

Sort by

recency

|

624 Discussions

|

  • Panzer_Rank
     + 0 comments

    Solution in C#, first thing I did was realize that there is very little sorting necessary in this problem. What we have to do is find the sums of the x rows and the sums of the y columns. Once we've done that we sort both arrays and compare the arrays to ensure they match 1-to-1. If they do not, they are impossible to sort otherwise they are possible. I left my debugging code for brevity.

    Essentially this swap sort method only works if each bucket has enough storage in it to hold the maximum count of a given item. (i.e. if there are two items of type A, there must be a corresponding bucket with two slots) this must be true for each item. 

     public static string organizingContainers(List<List<int>> container)
{
    List<int> xSum = new List<int>();
    List<int> ySum = new List<int>();
    int localXSum = 0;
    int localYSum = 0;

    for(int i = 0; i < container.Count; i++){
        localXSum = 0;
        localYSum = 0;           
        for(int j = 0; j < container[i].Count; j++){
            localXSum +=  container[i][j];
            localYSum += container [j][i];
        }
        xSum.Add(localXSum);
        ySum.Add(localYSum);
    }

    xSum.Sort();
    ySum.Sort();

    foreach(int pos in xSum){
        Console.Write(pos + " ");
    }

    Console.WriteLine();

    foreach(int pos in ySum){
        Console.Write(pos + " ");
    }

    Console.WriteLine();

    for(int i = 0; i < xSum.Count; i++){
        if(xSum[i] != ySum[i]){
            return "Impossible";
        }
    }

    return "Possible";
}

  • petru_braha
     + 0 comments

    c++ solution:

    string organizingContainers(vector<vector<int>> container) {
    int sizeRow = container.size();
    
    multiset<int> columnSums;
    multiset<int> rowSums;

    vector<int> partialColumnSums(sizeRow, 0);
    for (int i = 0; i < sizeRow; i++) {
        
        int currentRowSum = 0;
        for (int j = 0; j < sizeRow; j++) {
            currentRowSum += container.at(i).at(j);
            partialColumnSums[j] += container.at(i).at(j);
        }
        
        rowSums.insert(currentRowSum);
    }
    
    for (int partialColumnSum : partialColumnSums) {
        columnSums.insert(partialColumnSum);
    }
    
    if (columnSums == rowSums) {
        return "Possible";
    }
    
    return "Impossible";
}

  • saminazubair93
     + 0 comments

    here is my solution

    $total = count($container);
	
	$capacityArray = array();
	$indexArray = array();

	for ($i=0; $i < $total; $i++) { 
		$sum = array_sum($container[$i]);
		$capacityArray[] = $sum;
		$indexSum = 0;
		for ($j=0; $j < $total ; $j++) { 
			$indexSum+= $container[$j][$i];
		}
		$indexArray[] = $indexSum;
	}

sort($capacityArray);
sort($indexArray);

$result = '';
if ($capacityArray == $indexArray) {
	$result = 'Possible';
}
else
{
	$result = 'Impossible';
}
echo $result;

  • xavi_aclm
     + 0 comments

    for the love of god can you get into the habit of clarifying which indexes mean what in the input? every single problem on this site involving a matrix i have to comb through the example input to figure out which axes mean what because nobody bothered to clarify whether container[i][j] is the amount of i-color balls in container j or the amount of j-color balls in container i

  • pjt727
     + 0 comments
    def organizingContainers(container) -> str:
    '''returns Impossible | Possible for whether the balls can be split'''
    # this problem is very easy with two containers
    # the count of balls in one container must be equal to the counts of one type
    
    # this logic can be extended to the fact that for every count of a ball type there needs to be a container that fits it
    # in other words the sum of the columns must be equal to the sum of some other row (and that row cannot already be filled with a different ball type)
    
    # if you are wondering why zip(*container) gives a list of a ball type's count in each container here is the breakdown
    # container = [
    #      [1,4],
    #      [2,3],
    # ]
    # the * operator unpacks the container matrix 
    # zip(*container) = zip([1,4], [2,3])
    #
    # zip then joins equal indices together
    # list(zip(*container)) = [(1,2), (4,3)]
    sums_of_balls = [sum(b) for b in zip(*container)]
    sums_of_containers = [sum(c) for c in container]
    sums_of_balls.sort()
    sums_of_containers.sort()
    return "Possible" if sums_of_balls == sums_of_containers else "Impossible"