RestoreDrawing | Topcoder Archive

Problem Statement

Basha and Misof want to decorate a rectangular wall of their flat by painting some black-and-white bitmap onto it. They now have to choose some bitmap that matches their desires.

Basha wants to have a bitmap such that the sizes of the 4-connected components of black cells are the numbers given in sizes4. Misof wants to have a bitmap such that the sizes of the 8-connected components of black cells are the numbers given in sizes8.

Determine whether such a bitmap exists. If no, return an empty String[]. If yes, return any one such bitmap. Your bitmap must be rectangular and it must contain at most 100 rows and at most 100 columns. Use '.' to represent white cells and '#' to represent black cells.

Definition

Class:: RestoreDrawing
Method:: restore
Parameters:: int[], int[]
Returns:: String[]
Method signature:: String[] restore(int[] sizes4, int[] sizes8)
(be sure your method is public)

Notes

Two black cells are 4-neighbors if we can move from one to the other by making a single step in one of the 4 cardinal directions. The 4-connected components of black cells are equivalence classes of the transitive closure of the 4-neighbor relation.
The 8-connected components are defined the same way, but now diagonal movements are allowed as well.

Constraints

sizes4 will contain between 1 and 20 elements, inclusive.
sizes8 will contain between 1 and 20 elements, inclusive.
Each element of sizes4 will be a positive integer.
Each element of sizes8 will be a positive integer.
The sum of sizes4 will be at most 1500.
The sum of sizes8 will be at most 1500.

Examples

{1, 1, 1, 1, 1}

{5}

Returns: {"#.#", ".#.", "#.#" }

Nicely formatted output: #.# .#. #.#

{1, 1, 1, 1, 1}

{1, 1, 1, 1, 1}

Returns: {"#....", "..#.#", ".....", "#..#." }

Nicely formatted output: #.... ..#.# ..... #..#.

```
{2, 2, 2}
```
```
{3, 3}
```
```
Returns: { }
```
```
{42}
```
```
{47}
```
```
Returns: { }
```

{1, 2, 3, 5}

{7, 4}

Returns: {"##.##", "..##.", "#..#.", "##...", "..#.." }

Nicely formatted output: ##.## ..##. #..#. ##... ..#..

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.