Statistics

Problem Statement for "LinearPolyominoCovering"

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

  1. "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.

  2. "XX.XX"

    Returns: "BB.BB"

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

  3. "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.

  4. "."

    Returns: "."

  5. "X"

    Returns: "impossible"

  6. "XX"

    Returns: "BB"

  7. "XXXX"

    Returns: "AAAA"

  8. "XXXXXXXX"

    Returns: "AAAAAAAA"

  9. "X.XXXX"

    Returns: "impossible"

  10. "XXXX.X"

    Returns: "impossible"

  11. "XX.XXXX.XXXXXX.XXXXXXXX.XXXXXXXXXX"

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

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

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

  13. "..........XXXXXX........XXXX........XX.........."

    Returns: "..........AAAABB........AAAA........BB.........."

  14. "...XXXXXXXXXXXX.....XXXXXXXXXXXXXX......."

    Returns: "...AAAAAAAAAAAA.....AAAAAAAAAAAABB......."

  15. "XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX"

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

  16. ".XX.XXXX.XX.XX.XXXX.XX.XX.XXXX.XX.XX.XXXX.XX.XX.XX"

    Returns: ".BB.AAAA.BB.BB.AAAA.BB.BB.AAAA.BB.BB.AAAA.BB.BB.BB"

  17. "....XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...."

    Returns: "....AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABB...."

  18. "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"

    Returns: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABB"

  19. ".XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"

    Returns: "impossible"

  20. "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX."

    Returns: "impossible"

  21. ".XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX."

    Returns: ".AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA."

  22. "...XXXXXXXXXXXXXXXXXXXXXX.....XXXXXXXXXXXXXXXXXX.."

    Returns: "...AAAAAAAAAAAAAAAAAAAABB.....AAAAAAAAAAAAAAAABB.."

  23. "...XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"

    Returns: "impossible"

  24. ".........................................XXXX"

    Returns: ".........................................AAAA"

  25. "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"

    Returns: "impossible"

  26. ".XX...XXXX.....XXXXXX.......XXXXXXXX........."

    Returns: ".BB...AAAA.....AAAABB.......AAAAAAAA........."

  27. "..XXX....XXXXX......XXXXXXX........XXXXXXXXX"

    Returns: "impossible"

  28. ".........XXXXXXXX.......XXXXXX.....XXXX...XX."

    Returns: ".........AAAAAAAA.......AAAABB.....AAAA...BB."

  29. "XXXXXXXXXXXXXXXXXXXXXX......XXXXXXXXXXX..XXXX"

    Returns: "impossible"

  30. "XXXXXX........XXXX..XXXXXX....XXXXXX..XXXXXXX."

    Returns: "impossible"

  31. "........XXXX..XXXXXX....XXXXXX..X...."

    Returns: "impossible"

  32. "..X..XXXXXX....XXXXXX..XXXXXX...."

    Returns: "impossible"

  33. "........XXXXXXXX..XXXXXX....X..XXXXXX...."

    Returns: "impossible"

  34. "XX.XXXXXXXXXX..XXXXXXXX.XX.XXX.XXXXXX"

    Returns: "impossible"

  35. "XXXXX"

    Returns: "impossible"

  36. "XXX"

    Returns: "impossible"

  37. "X.X."

    Returns: "impossible"

  38. "....."

    Returns: "....."

  39. "..."

    Returns: "..."

  40. ".."

    Returns: ".."

  41. "XXXX....XX..XXXX"

    Returns: "AAAA....BB..AAAA"

  42. "...."

    Returns: "...."

  43. "........"

    Returns: "........"

  44. "XX.XXXXXXXXXX..XXXXXXXX...XXX"

    Returns: "impossible"

  45. ".XXX.XXX.XX.XXX.XXX.XX"

    Returns: "impossible"

  46. "X.X"

    Returns: "impossible"

  47. "...XX..."

    Returns: "...BB..."

  48. ".........."

    Returns: ".........."

  49. "......"

    Returns: "......"

  50. ".XXXX.XXXX.XX.XXXX."

    Returns: ".AAAA.AAAA.BB.AAAA."

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: