Subrectangle
SRM 727 · 2018-01-10 · by Errichto
Problem Statement
Limak had an empty grid, divided into square cells. He chose some non-empty rectangle (with sides parallel to sides of the grid) and marked all cells inside the rectangle.
A grid with H rows and W columns can be encoded into a string of length H*W as follows: examine the cells of the grid in row major order, and write down '#' for each marked cell and '.' for each empty cell. In other words, write down the first (topmost) row from the left to the right, then the second row from the left to the right, and so on.
Limak wanted to write down a string representing his grid. Unfortunately, he is easily distracted and thus he missed some cells (maybe zero or all of them). In other words, he got a subsequence of the string representing his grid.
You are given a
You may choose any positive dimensions for the grid. All missed cells count: both empty and marked ones.
Notes
- It can be proved that for any valid input string S there is some valid grid such that S is a subsequence of the string that encodes the grid.
Constraints
- S will contain between 0 and 300 characters, inclusive.
- Each character in S will be either '.' or '#'.
"..###.##" Returns: 2
It's possible that Limak's grid looked like this: ..### ..### This grid is represented by the string "..###..###". Limak missed 2 cells in this case: ..###.(.)##(#). Here, we denote missed cells by putting them in brackets. It's the minimum possible number of missed cells, so the answer is 2.
"#.##.#.#.." Returns: 2
The following grid is represented by the string #.#(.)#.#.#.(#). #. #. #. #. #. #. The second-to-last character could also be a dot (meaning that the last row in the grid is empty).
"####" Returns: 0
It's possible that Limak had a grid of size 1x4 or 2x2 or 4x1 and he marked the whole grid. The grid would be then represented by the given string "####".
"" Returns: 1
"........................................" Returns: 1
Submissions are judged against all 124 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Subrectangle with a public method int minMissed(string S) · 124 test cases · 2 s / 256 MB per case