FoldThePaper
SRM 406 · 2008-06-18 · by eleusive
SRM 406 · 2008-06-18 · by eleusive · Brute Force, Dynamic Programming
Problem Statement
Problem Statement
You have a rectangular piece of paper that's divided into 1x1 cells, each of which has an integer value. The paper will be described by a String[] paper. The ith element of paper will be a space delimited list of integers, where the jth integer of the ith element of paper represents the value of the jth cell of the ith row of the paper.
You want to perform a sequence of folds on the paper, where you may fold anywhere along an axis that is in between two rows or columns of the paper. After performing a fold, we wish to model the folded paper as a new, flat piece of paper. We will do this by considering two overlapping cells as a single cell, with a value that is the sum of the individual cells.
You wish to perform a sequence of folds such that the value of some single cell in the resulting piece of paper is as large as possible. Return this value.
You want to perform a sequence of folds on the paper, where you may fold anywhere along an axis that is in between two rows or columns of the paper. After performing a fold, we wish to model the folded paper as a new, flat piece of paper. We will do this by considering two overlapping cells as a single cell, with a value that is the sum of the individual cells.
You wish to perform a sequence of folds such that the value of some single cell in the resulting piece of paper is as large as possible. Return this value.
Constraints
- paper will contain between 1 and 12 elements, inclusive.
- Each element of paper will be a single-space delimited list of integers with no leading or trailing spaces.
- Each element of paper will contain between 1 and 12 integers, inclusive.
- Each element of paper will contain the same number of integers.
- Each element of paper will contain between 1 and 50 characters, inclusive.
- Each integer in paper will be between -100 and 100, inclusive.
- Each integer in paper will have no leading zeros.
- An integer in paper equal to zero will not have a preceding negative sign.
Examples
0)
{
"1 1 1",
"1 1 1"
}
Returns: 6
We can collapse every cell onto the upper-left cell.
1)
{
"1 -1",
"1 -1"
}
Returns: 2
We should perform only the fold between the two rows, and take the resulting left column.
2)
{
"1"
}
Returns: 1
3)
{
"1 -1 -1 1",
"-1 -1 -1 -1",
"-1 -1 -1 -1",
"1 -1 -1 1"
}
Returns: 4
Folding between the middle rows then the middle columns allows us to combine the four corner cells.
4)
{
"-1"
}
Returns: -1
82)
{
"1 -1 -1 1",
"-1 -1 -1 -1",
"-1 2 -1 -1",
"1 1 -1 1"
}
Returns: 4
Bad greedy: Take the fold that maximizes the largest resulting cell
83)
{"2 -1 -1 -1 -1 1 1 1 1 2"}
Returns: 8
Bad Greedy 2
84)
{"2 -1 -1 -1 -1 1 1 1 2"}
Returns: 7
bad greedy 3
85)
{
"2",
"-1",
"-1",
"-1",
"-1",
"1",
"1",
"1",
"1",
"2"
}
Returns: 8
bad greedy 4
86)
{
"2",
"-1",
"-1",
"-1",
"-1",
"1",
"1",
"1",
"2"
}
Returns: 7
bad greedy 5
87)
{
"1 -1 -1 1",
"-1 -1 2 1",
"-1 -1 -1 -1",
"1 -1 -1 1"
}
Returns: 4
bad greedy 6
Submissions are judged against all 167 archived test cases, of which 11 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FoldThePaper with a public method int getValue(vector<string> paper) · 167 test cases · 2 s / 256 MB per case