Problem Statement |
| | An ancient clay tile was found during an archeological dig. It could have been an important find, but unfortunately it is broken into pieces which are shuffled and shabby, so in its current state it has hardly any importance. You have to reconstruct the original look of the tile from its pieces.
The original tile is generated as a highly symmetrical shape which fits inside of an S x S square. This is done as follows: one eighth of the tile is generated as a random polygon. Then the polygon is filled with random pattern, created as a set of lines of random orientation and width. Finally, the generated one eighth of the tile is reflected symmetrically with respect to axes x=y and the result is rotated by 90 degrees three times to fill all the tile. See the visualizer source code for more details.
The generated tile is broken into pieces using a Voronoi diagram of a random set of points within the tile. Some of these pieces are removed, and the edges of the rest are crumbled up randomly. Note that the original edges of the tile generally don't crumble: the pixels on them can crumble if they belong to the border of the S x S square and to the crack between two pieces at the same time, or if after the main crumbling process they have 1 or 0 pixels of the same piece adjacent to them.
Finally, the resulting pieces are rotated randomly and presented to you as a String[] pieces. The format of pieces is as follows: each piece is a sequence of individual Strings representing its rows, and the consecutive pieces are separated with "-" Strings. The pixels where there is no clay are represented with '.', and black and white clay pixels are represented with '1' and '0' characters, respectively. Besides, you are given S - the size of the square and N - the number of pixels in the original tile.
Your task is to restore the original tile as an S x S square, with black and white pixels represented in the same way as in the input. You have to arrange the pieces in some way and fill the spaces between them with clay pixels of any color. Note that you don't need to distinguish the parts which are covered with the actual pieces from the parts which are lost or crumbled, you only have to reconstruct the whole image as close to the original one as possible.
Your score for an individual test case will be calculated as follows: the original tile and the one you returned are compared pixel-by-pixel; for each pixel which is absent ('.') on both tiles or present on both tiles in the same color you score 1, and for each pixel which is present on both tiles but has different colors you score 0.5. Finally, the sum of scores for individual pixels is divided by S*S. Your overall score will be the sum of scores over all test cases.
A visualizer is available for visualization and offline testing. |
| |
Definition |
| | | Class: | BrokenClayTile | | Method: | reconstruct | | Parameters: | int, int, String[] | | Returns: | String[] | | Method signature: | String[] reconstruct(int S, int N, String[] pieces) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Invalid return (i.e., sized not S x S or containing characters other than '.', '0' and '1') gives you a score of 0. |
| - | Please see visualizer source for details of test case generation. |
| - | The memory limit is 1024 MB and the time limit is 20 seconds (which includes only time spent in your code). There is no explicit code size limit. |
| - | There are 10 example test cases and 100 full submission test cases. |
| |
Constraints |
| - | S will be up to 401. |
| - | Up to one fifth of the pieces will be removed. |
| |
Examples |
| 0) | |
| | | Returns:
"seed = 1<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/1_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/1_broken.png>" | S = 361
N = 44856
157 pieces generated.
140 pieces passed to the solution. |
|
|
| 1) | |
| | | Returns:
"seed = 2<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/2_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/2_broken.png>" | S = 381
N = 142348
504 pieces generated.
448 pieces passed to the solution.
|
|
|
| 2) | |
| | | Returns:
"seed = 3<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/3_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/3_broken.png>" | S = 321
N = 56800
195 pieces generated.
174 pieces passed to the solution.
|
|
|
| 3) | |
| | | Returns:
"seed = 4<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/4_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/4_broken.png>" | S = 265
N = 21168
73 pieces generated.
61 pieces passed to the solution.
|
|
|
| 4) | |
| | | Returns:
"seed = 5<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/5_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/5_broken.png>" | S = 281
N = 15457
57 pieces generated.
47 pieces passed to the solution.
|
|
|
| 5) | |
| | | Returns:
"seed = 6<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/6_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/6_broken.png>" | S = 353
N = 106368
373 pieces generated.
312 pieces passed to the solution.
|
|
|
| 6) | |
| | | Returns:
"seed = 7<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/7_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/7_broken.png>" | S = 289
N = 83521
291 pieces generated.
258 pieces passed to the solution.
|
|
|
| 7) | |
| | | Returns:
"seed = 8<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/8_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/8_broken.png>" | S = 289
N = 66204
230 pieces generated.
198 pieces passed to the solution.
|
|
|
| 8) | |
| | | Returns:
"seed = 9<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/9_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/9_broken.png>" | S = 289
N = 38628
139 pieces generated.
125 pieces passed to the solution.
|
|
|
| 9) | |
| | | Returns:
"seed = 10<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/10_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/10_broken.png>" | S = 257
N = 53505
184 pieces generated.
157 pieces passed to the solution.
|
|
|
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)2020, TopCoder, Inc. All rights reserved.