Connection Status:
Competition Arena > ThreeMines

ThreeMines

SRM 315 · 2006-08-09 · by Cosmin.ro

SRM 315 · 2006-08-09 · by Cosmin.ro · Dynamic Programming
Class Name: ThreeMines
Return Type: int
Method Name: maximumProfit
Arg Types: (vector<string>)
Problem Statement

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.

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.

Statement by TopCoder, Inc. — view the original on the archive.

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.

18)
{"aaaaaa", "aBddBa", "adzzda", "adzHaa", "abdaaa", "aaaaaa"}
Returns: 94

greedy testcase

32)
{"hBZaBz","dhbhhB","dhbBaa","cBZaaa"}
Returns: 69

hBZaBz dhbhhB dhbBaa cBZaaa

Submissions are judged against all 75 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ThreeMines with a public method int maximumProfit(vector<string> field) · 75 test cases · 2 s / 256 MB per case

Submitting as anonymous