CoinFlipping2
SRM 827 · 2022-04-04 · by misof
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
Your goal is to have exactly desiredCount 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 can select each row and column arbitrarily many times and in any order you like.
If the goal cannot be achieved, return {-1}.
Otherwise, find and return any sequence of at most 100 moves that produces one configuration with the desired number of heads.
Return the sequence of moves formatted as a
If layout has R elements with C characters each, use the value x to denote the move that flips layout[x], and use the value R+y to denote the move that flips layout[r][y] for all r.
Notes
- You may assume that whenever a solution exists, a solution with at most 100 moves exists.
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 '.'.
- desiredCount will be between 0 and the number of coins on the table, inclusive.
{"H.T.H",
"TTTTT",
"HHTHH"}
12
Returns: {1, 5 }
In our solution we flip the middle row (denoted 1) and then we flip the middle column (denoted 5). Below we show the intermediate state, the final state, and the numbers that correspond to individual rows and columns. initial: intermediate: final: 34567 34567 34567 0 H.T.H 0 H.T.H 0 H.H.H 1 TTTTT 1 HHHHH 1 HHTHH 2 HHTHH 2 HHTHH 2 HHHHH
{"HT",
"HH"}
2
Returns: {-1 }
Regardless of how you make the flips, there will always be three coins of one type and one of the other. It's not possible to have exactly two heads.
{"HT",
"HH"}
3
Returns: { }
One easy way to produce exactly three heads is to do nothing :) Other valid return values include {1, 1, 2, 1, 2, 1} and {1, 3}. The first of these produces the initial configuration, the second a configuration in which only the coin in the bottom left corner is tails.
{"T....",
"...T.",
"..T..",
"....T",
".T..."}
4
Returns: {0, 9, 2, 6 }
Each of these coins can be toggled independently of the others, either by selecting its row or by selecting its column. In order to have four heads we can simply toggle any four of them.
{ "HTHTHTHTHTHTTTHTHTHTHTHTHTTTHTHTHTHTHTHTHTHHHTHTHT", "TTTHTHTHTTHHHHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTH", "HTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHT", "THTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHHHTTTHTHTHTHTHTH", "HTHHHTHTHTHTHTHTHHHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHT", "THTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTTTTTHTHTH", "HTHTHTHTHTHTHTHTHTHTHTHHHTHTHTHTHTHTHTHTHTHTHTHTHT", "THTHTHTHTHTHTHTHTHTHTHTTTHTHTHTHTHTHTHTHTHTHTHTTTH", "HTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHT", "THTHTHTHTHTHTHTHTHHHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTH", "HTHTHTHTHTTHHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHT", "THTHTHTHTHTHTHTHTHTHTHTHTHHHTHTHTHTHTHTHTHTHTHTHTH" }
554
Returns: {0, 2, 4, 6, 8, 10, 60, 58, 56, 54, 52, 50, 48, 44, 42, 40, 36, 34, 32, 30, 28, 26, 22, 20, 18, 16, 14, 12 }
Submissions are judged against all 108 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CoinFlipping2 with a public method vector<int> correctHeads(vector<string> layout, int desiredCount) · 108 test cases · 2 s / 256 MB per case