TopCoder problem "ThreeMines" used in SRM 315 (Division I Level Three)



Problem Statement

    A Company that Makes Everything (ACME) has entered the surface mining business. They bought a rectangular field which is split into cells, with each cell having a profit value. A mine is a non-empty rectangular region, and the profit of a mine is equal to the sum of the values of all its cells. ACME wants to extract ore from three different non-overlapping mines. You are to choose these mines to maximize the total profit.



You are given a String[] field where each character represents the profit value of a single cell. Characters 'a' to 'z' correspond to the numbers 0 through 25 and characters 'B' to 'Z' correspond to numbers -1 through -25. The jth char in the ith element of field is the profit value of the cell at row i, column j.
 

Definition

    
Class:ThreeMines
Method:maximumProfit
Parameters:String[]
Returns:int
Method signature:int maximumProfit(String[] field)
(be sure your method is public)
    
 

Constraints

-field will contain between 1 and 30 elements, inclusive.
-Each element of field will contain between 1 and 30 characters, inclusive.
-Each character of field will be from the set 'a'..'z' and 'B'..'Z'.
-All elements of field will contain the same number of characters.
-field must contain at least 3 cells.
 

Examples

0)
    
{
"bbbb",
"bBBB",
"BBbb",
"BBBB"}
Returns: 7
One of the optimal solutions is the following: One mine contains all cells in the first row, the second mine contains the cell (1, 0), and the third mine contains the cells (2, 2) and (2, 3).
1)
    
{"cfCBDCbcdZb"}
Returns: 14
A single row example.
2)
    
{"d", "c", "B", "m", "Z", "h", "g", "B", "z", "G", "H", "b", "Y"}

Returns: 54
A single column example.
3)
    
{
"hBhh", 
"BBBB",
"BBBB", 
"hBhh", 
"hBhh"}
Returns: 62
This test has only one solution.
4)
    
{
"BB", 
"BB"}
Returns: -3
It is possible for the maximum possible profit to be negative.
5)
    
{
"ZcabcaacacabcbbbcababacaccbZaa",
"acaaccccacbccbaaccabaccaacbZbc",
"bcbaacbcbbccbbcbabbbbaZcbcbccb",
"cccacbabccbZbcbabaacbbZcbacbab",
"cacbabbcabbabbcacbcbbcaacaabbc",
"bacZcacaaccbabbcccccabcaacbaca",
"cbcccacabcabacaccacaZbbcbcacbb",
"cZbbbcaacbaacaabZcaccbcZccbbab",
"Zcababaacbbbbccbcbbaccacacbbcc",
"cZcccaaabbcbcbccccbcbaabbbccbb",
"bbcaacacabccababacbccacccbbaba",
"cccbbcaZabccacabbccccabbabbbab",
"bbbacbccbbcaabaaabccbcaabcacaa",
"cbbababbccccbcccbaacacccaabaac",
"aaccaccaccbabbccaaaacbacccacca",
"bbbcabcabZZcabcabbaacZbaaabaZb",
"aaabbabcabaaacbcccccbbcabcccbc",
"bbbaccbacacaccbbaccabacbbbaaac",
"acaaacccbabbccbcbabbcbaaaccabb",
"bcaaaaabcbabaaabccacccbaacbbbc",
"bZcbcbcccaabccaabbccbababbbcca",
"cbbbbcccabcabcbacaaaaabbbbbcac",
"ccbbcbacacbbcacacbaabcbbacbaba",
"cbbbaabaabbbbaccabbcbcaccaaaac",
"abZcabaacbbcacbaaabccbabacacaa",
"aabccacbabaacaccccbbbbcccccaca",
"aabcbaaacbabcaccbaabbbabbabbca",
"ababcabaccaaaacccacbcbcabacbcb",
"bcaaaacabcabbbaccccccacabccacb",
"cbbabbbccaaaaacbccaabcbbccbacc"}
Returns: 671

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6625

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9995&pm=6625

Writer:

Cosmin.ro

Testers:

PabloGilberto , brett1479 , vorthys , Olexiy

Problem categories:

Dynamic Programming