Connection Status:
Competition Arena > TwoStamps

TwoStamps

SRM 822 · 2022-01-16 · by misof

SRM 822 · 2022-01-16 · by misof · Brute Force, Simulation
Class Name: TwoStamps
Return Type: int
Method Name: minCircles
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Alesha has two stamps.

  • One stamp (called the "circle" stamp) is two characters wide and produces an approximation of a circle: "()".
  • The other stamp (called the "eraser" stamp) is one character wide and produces a space. (When used on an area that already contains some characters, both stamps overwrite those old characters completely.)

Alesha has a page. The page is divided into a rectangular grid, with each cell of the grid exactly the dimensions of one character. Initially, the grid was all-white. Alesha then produced a picture by repeatedly using her two stamps. Each stamp was always placed completely inside the page and aligned with the grid. Alesha could have used each stamp arbitrarily many times, and alternate between the two stamps arbitrarily many times.

You are given the contents of a page in the String[] page. Determine whether Alesha could have produced this page. If no, return -1. If yes, return the smallest number of times she had to have used the two-character-wide stamp.

Constraints

  • page will have between 1 and 50 elements, inclusive.
  • Each element of page will have between 1 and 50 characters, inclusive.
  • All elements of page will have the same number of characters.
  • Each character in page will be '(', ')', or ' '.
Examples
0)
{"    ",
 " () ",
 "    "}
Returns: 1

This page could have been produced by using the "circle" stamp once, so that is clearly the optimal number of times.

1)
{"    ",
 "(())",
 "    "}
Returns: 3

This page could have been produced by using the "circle" stamp three times. One possible way is shown below: +----+ | | | | | | +----+ +----+ | | | ()| | | +----+ +----+ | | |()()| | | +----+ +----+ | | |(())| | | +----+ Note that the third stamp partially overwrote each of the previous two.

2)
{"(   ",
 "(   ",
 "(   "}
Returns: 3

The optimal way to produce this page is to use the "circle" stamp three times (once in each row, always aligned with the left edge) and then the "eraser" stamp three times (to erase the right half of each of the stamps).

3)
{"(   ",
 ")   ",
 ")   "}
Returns: -1

It's impossible to produce this page. (Remember that each stamp must always be placed completely inside the page.)

4)
{"( ) ",
 "    ",
 "    "}
Returns: 2

These two parentheses cannot be produced by using the "circle" stamp just once, they are too far from each other. It is possible to produce this page by using the "circle" stamp twice and then the "eraser" stamp (at least) once.

5)
{"( ( ( (  ) ) ) )"}
Returns: 8

One way to produce this page is to do eight rounds of first using the "circle" stamp and then the "eraser" stamp to remove half of it. There is no way to produce this page in fewer than 8 uses of the "circle" stamp.

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

Coding Area

Language: C++17 · define a public class TwoStamps with a public method int minCircles(vector<string> page) · 67 test cases · 2 s / 256 MB per case

Submitting as anonymous