TopCoder problem "LinearPolyominoCovering" used in SRM 429 (Division II Level One)

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.

Definition

Class:	LinearPolyominoCovering
Method:	findCovering
Parameters:	String
Returns:	String
Method signature:	String findCovering(String region)
(be sure your method is public)

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.

"X"

Returns: "impossible"

"XX.XXXXXXXXXX..XXXXXXXX...XXXXXX"

Returns: "BB.AAAAAAAABB..AAAAAAAA...AAAABB"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10251

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13520&pm=10251

Writer:

darnley

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Greedy