Connection Status:
Competition Arena > EllysFlags

EllysFlags

SRM 792 · 2020-10-21 · by espr1t

SRM 792 · 2020-10-21 · by espr1t · Dynamic Programming
Class Name: EllysFlags
Return Type: int
Method Name: getMax
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Elly has a white sheet of squared paper with several rows and columns. While she was mostly ignoring the teacher in a rather boring class, the girl colored random squares with green and red. At some point she realized that the paper was full of Bulgarian flags! The girl says she has drawn a "flag" if three consecutive squares going only down and to the right (each sharing a side with the next one) are, in this order, white, green and red. Thus, there are four types of flags:


Please note that several flags can share cells. For example, in the following configuration there are a total of six flags, three of which start from the white square in the top left corner:


Fascinated by what she has unconsciously done, she now wants to fill some of the remaining white squares with green and red, such that the number of "flags" in the end is as large as possible.
The current coloring of Elly's paper will be given to you in the String[] paper. paper[row][col] will be 'W' if the square at (row, col) is white, 'G', if it is green, and 'R', if it is red. Return the maximum number of flags that can be drawn if the girl fills some (possibly none) of the remaining white cells with green and red optimally.

Notes

  • The paper cannot be rotated in any way.
  • The girl can only change white squares to either green or red. No square which is already colored can become white or be re-colored.

Constraints

  • paper will contain between 1 and 10 elements, inclusive.
  • Each element of paper will contain between 1 and 10 characters, inclusive.
  • All elements of paper will have the same length.
  • Each character in paper will be 'W', 'G' or 'R'.
Examples
0)
{"WGWWR",
 "GRGRG",
 "RWGRW",
 "GGWGR"}
Returns: 9

This is the example from the problem statement. Currently, there are 6 flags already drawn. We can color the square on the first row, fourth column in green, obtaining two additional flags. Additionally, if we color the cell on the fourth row, third column in red, we lose one of the flags we had before, but we get two new ones.

1)
{"WWGRWW",
 "WWWWWW",
 "WWRGWW"}
Returns: 13
2)
{"WWGGRGWGGW",
 "WWRWRGWWRG",
 "GGWRWRRWRW",
 "WWRRWWWWGR",
 "WWGWWGRWGR",
 "WWGWRRWWWR",
 "WRGWWGWGWW",
 "WWRGWRWGGW",
 "WWRRWWGWRW",
 "WRGWRRRGWW"}
Returns: 42

The answer is 42.

3)
{"WWWWWWW",
 "WWWWWWW",
 "WWWWWWW",
 "WWWWWWW",
 "WWWWWWW",
 "WWWWWWW",
 "WWWWWWW",
 "WWWWWWW"}
Returns: 56

No restrictons on this paper - every cell can be colored in any color.

4)
{"W"}
Returns: 0

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

Coding Area

Language: C++17 · define a public class EllysFlags with a public method int getMax(vector<string> paper) · 101 test cases · 2 s / 256 MB per case

Submitting as anonymous