2016-S4 Combining Rice Balls - Solution

# 2016-S4 Combining Rice Balls - Solution

The inputs are extremely simple to read:

``````int totalBalls;
int riceBalls;

{
std::cin >> totalBalls;
for (int i=0;i<totalBalls;i++)
std::cin >> riceBalls[i];
}
``````

## Initializing the Dynamic Programming Container

We are using a 2D array for the DP container that simply needs to be initialized to -1 at all locations.

``````int counts;

void init_dp()
{
for (int start=0;start<totalBalls;start++)
for (int end=0;end<totalBalls;end++)
counts[start][end] = -1;
}
``````

When a match is found we will call a method to set the total count of the range into the array:

``````void add_solution(int startIndex, int endIndex, int ballCount)
{
counts[startIndex][endIndex] = ballCount;
}
``````

We also have a method to see if a solution has been found for a specific range. If the start and end range index locations are the same we always return TRUE.

``````bool can_range_be_combined(int startIndex, int endIndex)
{
if (startIndex == endIndex)
return true;
else
return counts[startIndex][endIndex] != -1;
}
``````

A final method simply returns the total rice balls contained in a range (this functions assumes a combination is possible):

``````int get_range_count(int startIndex, int endIndex)
{
if (startIndex == endIndex)
return riceBalls[startIndex];
else
return counts[startIndex][endIndex];
}
``````

## Simple Search Method

We have to have a search method that search for matches with only two blocks (first and last) and no middle block. This is the simplest search method and it returns TRUE or FALSE if it finds a match:

``````// Looks for two blocks that can be combined and contain equal number of rice_balls
bool search_range_for_two_blocks(int firstStartIndex, int lastEndIndex)
{
for (int lastStartIndex = firstStartIndex+1; lastStartIndex <= lastEndIndex; lastStartIndex++)
{
// Define the first range
int firstEndIndex = lastStartIndex-1;

// Skip starting ranges that cannot be combined
if (can_range_be_combined(firstStartIndex,firstEndIndex) == false)
continue;

// Skip ending ranges that cannot be combined
if (can_range_be_combined(lastStartIndex,lastEndIndex) == false)
continue;

// We need to know the first range count
int firstCount = get_range_count(firstStartIndex,firstEndIndex);

// We need to know the last range count
int lastCount = get_range_count(lastStartIndex,lastEndIndex);

// We can only combine if the first range count is the same as the last range count
if (firstCount != lastCount)
continue;

// Compute the combined number of rice balls
int rangeCount = firstCount + lastCount;

// We have found a solution - lets add it to the our DP container

// Only one solution is important - we don't have to keep looking for another
return true;
}

// We did not find a solution
return false;
}
``````

The second solver is more complex and needs to find matches with three blocks (first, middle, last):

``````// Looks for solutions with a middle block that can be combined
void search_range_for_three_blocks(int firstStartIndex, int lastEndIndex)
{
for (int middleStartIndex = firstStartIndex+1; middleStartIndex < lastEndIndex; middleStartIndex++)
{
// Define the end of the first block
int firstEndIndex = middleStartIndex-1;

// Skip first range if it cannot be combined
if (can_range_be_combined(firstStartIndex,firstEndIndex) == false)
continue;

// We need to know the starting range count
int firstCount = get_range_count(firstStartIndex,firstEndIndex);

for (int lastStartIndex = middleStartIndex+1; lastStartIndex <= lastEndIndex; lastStartIndex++)
{
// Define the end of them middle block
int middleEndIndex = lastStartIndex -1;

// Skip middle range that cannot be combined
if (can_range_be_combined(middleStartIndex,middleEndIndex) == false)
continue;

// Skip last range that cannot be combined
if (can_range_be_combined(lastStartIndex,lastEndIndex) == false)
continue;

// We need to know the last range count
int lastCount = get_range_count(lastStartIndex,lastEndIndex);

// We can only combine if the first range count is the same as the last range count
if (firstCount != lastCount)
continue;

// We need the middle range count so we can compute the full range count
int middleCount = get_range_count(middleStartIndex,middleEndIndex);
int rangeCount = firstCount + middleCount + lastCount;

// We have found a solution - lets add it to the our DP container

// Only one solution is important - we don't have to keep looking for another
return;
}
}
}
``````

The final solver puts the entire solution together by search for solutions first with 2 rice balls, then 3, until it tries to combine all the balls together: Search

``````// Solve for ranges of 2 and all the way to the totalBalls
for (int range=2;range<=totalBalls;range++)
{
int maxStart = totalBalls-range+1;
for (int firstStartIndex=0;firstStartIndex<maxStart;firstStartIndex++)
{
int lastEndIndex = firstStartIndex + range - 1;

// Search for two block solutions (first,last)
bool found = search_range_for_two_blocks(firstStartIndex,lastEndIndex);

// If we found a solution with the simple solver don't do any more work
if (found) continue;

// Search for solutions with three blocks (first, middle, last) when we have at least 3 balls
if (range > 2)
search_range_for_three_blocks(firstStartIndex,lastEndIndex);
}
}
``````

## Final Step

The final step is to find the largest ball in our solution set. This is a simple 2D search:

``````// Quick search through all solutions for the one with the largest number of riceBalls
int find_largest_combination()
{
int max = 0;

for (int start=0;start<totalBalls;start++)
for (int end=start;end<totalBalls;end++)
max = std::max( max, get_range_count(start,end) );

return max;
}
``````