Connection Status:
Competition Arena > RestoreDrawing

RestoreDrawing

TCO19 SRM 754 · 2019-03-25 · by misof

TCO19 SRM 754 · 2019-03-25 · by misof · Dynamic Programming, Greedy
Class Name: RestoreDrawing
Return Type: String[]
Method Name: restore
Arg Types: (vector<int>, vector<int>)
Problem Statement

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.

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
0)
{1, 1, 1, 1, 1}
{5}
Returns: {"#.#", ".#.", "#.#" }

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

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

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

2)
{2, 2, 2}
{3, 3}
Returns: { }
3)
{42}
{47}
Returns: { }
4)
{1, 2, 3, 5}
{7, 4}
Returns: {"##.##", "..##.", "#..#.", "##...", "..#.." }

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

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

Coding Area

Language: C++17 · define a public class RestoreDrawing with a public method vector<string> restore(vector<int> sizes4, vector<int> sizes8) · 163 test cases · 2 s / 256 MB per case

Submitting as anonymous