LinearPolyominoCovering

SRM 429 · 2008-12-11 · by darnley

SRM 429 · 2008-12-11 · by darnley · Greedy

Show categories

Class Name: LinearPolyominoCovering

Return Type: String

Method Name: findCovering

Arg Types: (string)

Problem Statement

You have an infinite number of the following two polyominoes: AAAA and BB.

You are given a String region, filled with characters '.' and 'X'. You need to cover (without overlapping) all the 'X' characters with the given polyominoes.

Return a String that contains the same region with cells marked '.' left untouched, and cells marked 'X' changed to 'A' or 'B', according to the polyomino that covers the cell.

If there is no solution, return the String "impossible" (quotes for clarity only).

If there are multiple solutions, return the lexicographically smallest one.

Notes

A string S is greater than a string T lexicographically if T is a proper prefix of S, or if S has a greater character at the first position where the strings differ.

Constraints

region will contain between 1 and 50 characters, inclusive.
Each character of region will be either '.' or uppercase 'X'.

Examples

"XXXXXX"
Returns: "AAAABB"

There is only room for one AAAA polyomino, so there are three possible coverings: "AAAABB", "BBAAAA", and "BBBBBB". The first one is the lexicographically smallest.

"XX.XX"
Returns: "BB.BB"

The empty cell in the middle should be left uncovered, so we can't use the AAAA polyomino here.

"XXXX....XXX.....XX"
Returns: "impossible"

The middle segment of Xs is too narrow for an AAAA polyomino, but is too wide for a BB polyomino.

"."
Returns: "."

"X"
Returns: "impossible"

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

Coding Area

Language: C++17 · define a public class LinearPolyominoCovering with a public method string findCovering(string region) · 50 test cases · 2 s / 256 MB per case