Cubes on a Table

By in Community Stories September 5, 2018

The August 25, 2018 Single Round Match (SRM) lived up to being marketed as a fun round.  The Single Round Match’s first problem, CubesonaTable, required the knowledge of division, modulus, and the array container to return an optimal solution.  

The problem’s premise is that one has 150 unit cubes and a table that is a square.  The square is divided into grids that are 10×10 unit cubes in area. As long as there is at least one cube in each of the cells, the cube is placed in the stablest position (i.e. at (x,y,z+1) if (x,y,z) is filled.  0<x,y,z<9), and the cubes placed together create a surface, the solution is considered viable.

The class for the problem is CubesonaTable with the method placeCubes.  The problem takes an integer and returns an array of integers. For this portion of the code, the class can be written as such:

class CubesonaTable{
	public:
	vector<int>placeCubes(int);
}

vector <int> placeCubes(int surface){
	vector<int>table;
	return table;
}

Ok, now the code to solve the problem.  The problem is fairly simple. The modulus of the surface by can be 0, 1, 2 or 3.  If the surface modulus is 0 and the surface is greater than or equal to 8, the vector  has 0, 0, and i added to it. The integer i is incremented from 0 as long as it is less than the remainder of the surface and 4 with 1 subtracted from it.  0, 1, and 0 are also added to the vector.

if (surface % 4 == 0 && surface >= 8){
	for (int i = 0; i < surface/4 -1; i++){
	table.push_back(0);
	table.pusb_back(0);
	table.push_back(i);
}
table.push_back(0);
table.push_back(1);
table.push_back(0);
}

If the surface modulus is 1, the surface size is checked to be greater than or equal to 5. The vector has 0, 0, and i added to it. The integer i is incremented from 0 as long as it is less than the remainder of the surface and 4.

if (surface % 4 == 1 && surface >= 5){
	for (int i = 0; i < surface/4; i++){
    table.push_back(0);
    table.pusb_back(0);
    table.push_back(i);
  }
}

If the surface modulus is 2 and the surface is greater than or equal to 10, the vector has 0, 0, and i added to it. The integer i is incremented from 0 as long as it is less than the remainder of the surface and 4 with 1 subtracted from it. 0, 2, and 0 are also added to the vector.

if (surface % 4 == 2 && surface >= 10){
	for (int i = 0; i < surface/4-1; i++){
    table.push_back(0);
    table.pusb_back(0);
    table.push_back(i);
  }
  table.push_back(0);
  table.push_back(2);
  table.push_back(0);
}

If the surface modulus is 3 and the surface is greater than or equal to 11, the vector has 0, 0, and i added to it. The integer i is incremented from 0 as long as it is less than the remainder of the surface and 4 with 1 subtracted from it. 0, 1, 0, 0, 2, and 0 are also added to the vector.

if (surface % 4 == 3 && surface >= 11){
	for (int i = 0; i < surface/4-1; i++){
    table.push_back(0);
    table.pusb_back(0);
    table.push_back(i);
  }
  table.push_back(0);
  table.push_back(1);
  table.push_back(0);
  table.push_back(0);
  table.push_back(2);
  table.push_back(0);
}

Full solution:

class CubesonaTable{
	public:
	vector<int>placeCubes(int);
}

vector <int> CubesonaTable::placeCubes(int surface){
	vector<int>table;
	if (surface % 4 == 0 && surface >= 8){
    for (int i = 0; i < surface/4 -1; i++){
      table.push_back(0);
      table.pusb_back(0);
      table.push_back(i);
    }
    table.push_back(0);
    table.push_back(1);
    table.push_back(0);
  }
  if (surface % 4 == 1 && surface >= 5){
	  for (int i = 0; i < surface/4; i++){
      table.push_back(0);
      table.pusb_back(0);
      table.push_back(i);
    }
  }
  if (surface % 4 == 2 && surface >= 10){
	  for (int i = 0; i < surface/4-1; i++){
      table.push_back(0);
      table.pusb_back(0);
      table.push_back(i);
    }
    table.push_back(0);
    table.push_back(2);
    table.push_back(0);
  }
  if (surface % 4 == 3 && surface >= 11){
    for (int i = 0; i < surface/4-1; i++){
      table.push_back(0);
      table.pusb_back(0);
      table.push_back(i);
    }
    table.push_back(0);
    table.push_back(1);
    table.push_back(0);
    table.push_back(0);
    table.push_back(2);
    table.push_back(0);
  }
  return table;
}

The original problem can be found at Topcoder’s SRM archive. The solution is tourist’s winning solution for the problem. Please stay tuned for the next Topcoder SRM.