Connection Status:
Competition Arena > CoinFlipping

CoinFlipping

SRM 827 · 2022-04-04 · by misof

SRM 827 · 2022-04-04 · by misof · Brute Force, Greedy
Class Name: CoinFlipping
Return Type: int
Method Name: mostHeads
Arg Types: (vector<string>)
Problem Statement

Problem Statement

There is a table with a rectangular top surface. The surface is divided into a grid of square cells. Some cells are empty, others contain exactly one coin each. Each coin is showing either heads or tails.

You are given the String[] layout describing the current configuration. Each letter represents one cell: 'H' is a cell with a coin that shows heads, 'T' a coin that shows tails, and '.' is an empty cell.


Your goal is to maximize the number of coins that show heads.

You can modify the current configuration in a series of steps. In each step you can choose any row or column of cells and flip all coins that are in the selected region. You may perform as many steps as you like, you can select each row and column arbitrarily many times and in any order you like.

Return the maximum number of simultaneously visible heads you can produce.

Constraints

  • layout will contain between 1 and 12 elements, inclusive.
  • Each element in layout will contain the same number of characters.
  • That number will be between 1 and 50, inclusive.
  • Each character in layout will be 'H', 'T', or '.'.
Examples
0)
{"H.T.H",
 "TTTTT",
 "HHTHH"}
Returns: 12

We can flip column 2 and then flip row 1 to get 12 coins that show heads and one (in the middle) that shows tails. There are other sequences of moves that also produce 12 coins heads, but there is no sequence of moves that would turn all 13 coins heads simultaneously.

1)
{"TT",
 "HT"}
Returns: 3

Regardless of what we do, we'll always have three coins of one type and one coin of the other type. Thus, the best solution we can get is to have three heads. This can be achieved by (for example) flipping row 0.

2)
{"T....",
 "...T.",
 "..T..",
 "....T",
 ".T..."}
Returns: 5

We can (for example) flip all colums to get five heads.

3)
{"HT.HT.HT.HT.",
 ".HT.HT.HT.HT",
 "T.HT.HT.HT.H"}
Returns: 20
4)
{ "HTHTHTHTHTHTTTHTHTHTHTHTHTTTHTHTHTHTHTHTHTHHHTHTHT", "TTTHTHTHTTHHHHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTH", "HTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHT", "THTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHHHTTTHTHTHTHTHTH", "HTHHHTHTHTHTHTHTHHHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHT", "THTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTTTTTHTHTH", "HTHTHTHTHTHTHTHTHTHTHTHHHTHTHTHTHTHTHTHTHTHTHTHTHT", "THTHTHTHTHTHTHTHTHTHTHTTTHTHTHTHTHTHTHTHTHTHTHTTTH", "HTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHT", "THTHTHTHTHTHTHTHTHHHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTH", "HTHTHTHTHTTHHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHT", "THTHTHTHTHTHTHTHTHTHTHTHTHHHTHTHTHTHTHTHTHTHTHTHTH" }
Returns: 580

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

Coding Area

Language: C++17 · define a public class CoinFlipping with a public method int mostHeads(vector<string> layout) · 106 test cases · 2 s / 256 MB per case

Submitting as anonymous