Connection Status:
Competition Arena > ElephantDrinking

ElephantDrinking

SRM 611 · 2013-12-22 · by cgy4ever

SRM 611 · 2013-12-22 · by cgy4ever · Dynamic Programming
Class Name: ElephantDrinking
Return Type: int
Method Name: maxSum
Arg Types: (vector<string>)
Problem Statement

Problem Statement

There is an n times n field. Some of the cells of the field contain water springs. You are given a map of the field encoded as a String[] field. There are n elements in field and each of them has n characters. Each character in field is a digit. The digit 0 represents a cell with no water. The digits 1 through 9 represent springs, and the digit is the rate at which the spring gives water. For example, the digit 5 is a spring that produces 5 units of water per unit of time.


There are 4n elephants around the field: one per each cell boundary, as shown in the pictures below. The elephants can use their trunks to drink water. Each elephant can only extend its trunk straight into the field. So, for example, the elephants that are on the left side of the field can only extend their noses towards the right. The trunks are long enough to reach the opposite end of the field. Each elephant can drink water at any rate. All water not consumed by elephants is lost.




There are two additional restrictions: The trunks of elephants are not allowed to intersect. For each cell with water, there can be at most one elephant drinking from that cell.


For example, figure (a) below shows a valid configuration. Cells with water springs are blue, elephants are green, and their trunks are red. In the figure there are four elephants that drink. Figures (b) and (c) show invalid configurations. In both of them the trunks intersect.


Your task is to return the maximal total number of units of water per unit time the elephants can drink.

Constraints

  • n will be between 2 and 50, inclusive.
  • field will contain exactly n elements.
  • Each element in field will contain exactly n characters.
  • Each character in field will be a digit ('0'-'9').
Examples
0)
{"00000",
 "00110",
 "01000",
 "00100",
 "00000"}
Returns: 4

This is the field shown in the figure in the problem statement. All springs have rate 1. As shown in figure (a), four elephants can drink at the same time. And as we only have four cells with water, this is clearly optimal.

1)
{"111",
 "191",
 "111"}
Returns: 16

In the optimal solution there will be seven elephants drinking from springs with rate 1, and one elephant drinking from the central spring with rate 9. The total rate at which these elephants will consume water is 7*1 + 1*9 = 16 units per unit of time.

2)
{"1010",
 "0011",
 "1100",
 "1111"}
Returns: 10
3)
{"0011",
 "1110",
 "0111",
 "0101"}
Returns: 10
4)
{"11100",
 "00100",
 "11111",
 "00100",
 "10111"}
Returns: 13

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

Coding Area

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

Submitting as anonymous