Problem Statement |
| | The board consists of WxH squares. Each square has several lines of wire on it,
each line connecting the center of the square with the middle of one of the sides of the square.
Left and right sides of the board have H contacts each, positioned at the middles of squares'
sides. Each contact can be either active or not, and it will stay in the same state throughout the simulation.
Your goal is to connect some active contacts at the left and right sides using the wire on the squares
(see "Scoring" for clarification).
To get the desired wire configuration, you can rotate squares 90 degrees clockwise or counterclockwise,
one rotation of one square per step.
Implementation
Your code should implement two methods, as described below:
-
init (int W, int H, String C). This method is called once per test case, giving you width
of the board W, height of the board H and a list of activity states of contacts C.
Elements 0..H-1 of C describe contacts 0..H-1 on the left side,
and elements H..2*H-1 describe contacts 0..H-1 on the right side
(contacts on each side are numbered top-down).
Each element of C will be '1' for active contact or '0' for inactive one.
-
rotateSquare (int[] board). This method is called once per step, to define the square you want
to rotate. board describes the current state of the board, square at row i and
column j being described with board[i*W+j] (row 0 is the topmost, column 0 is the leftmost). The wires' placement on the square is encoded as an integer using one bit per square's side, ordered top-right-bottom-left starting with the lowest bit, bit value of 1 meaning that there is a wire between the center of the square and the middle of this side.
You can decode the values as top=sq&1, right=(sq>>1)&1, bottom=(sq>>2)&1, left=(sq>>3)&1.
You must return a int[] with three elements, i, j and s,
indicating the row index and the column index of the square to be rotated
and its sign of rotation (1 for clockwise and -1 for counterclockwise).
Scoring
After each call of rotateSquare it is checked whether there exists an active contact on the left connected with an active contact on the right. If such pair of contacts is found, the simulation stops, and the score for a test case is
(number of active contacts on the left which are connected with at least one active contact on the right)
+ (number of active contacts on the right which are connected with at least one active contact on the left)
divided by the number of moves made.
Your overall score will be the sum of your individual scores, divided by the greatest score achieved by anyone for that test case.
If after 2*W*H steps you fail to connect active contacts, the simulation stops, and your absolute score for a test case is 0.
Test Case Generation
W and H are chosen between 10 and 100.
Each character of C chosen as '0' or '1', both values having equal probability.
To generate one square of board, first its type is chosen of the five possible types (no wire, two wires top-bottom, two wires top-right, three wires, four wires), and then its orientation is chosen. If the resulting board already has a connected pair of active contacts on the left and on the right, board (but not W, H or C) is regenerated.
Tools
As usual, a visualizer is available.
|
| |
Definition |
| | | Class: | CircuitConstruction | | Method: | init | | Parameters: | int, int, String | | Returns: | int | | Method signature: | int init(int W, int H, String C) | | | | Method: | rotateSquare | | Parameters: | int[] | | Returns: | int[] | | Method signature: | int[] rotateSquare(int[] board) | | (be sure your methods are public) |
|
| |
|
| |
Notes |
| - | A square can have no wire on it. |
| - | You may return any integer from init, it will be ignored. |
| - | The memory limit is 1 GB and the time limit is 20 seconds (which includes only time spent in your code). |
| - | Invalid return from rotateSquare or time limit results in absolute score 0. |
| - | There are 10 example test cases and 100 full submission test cases. |
| |
Examples |
| 0) | |
| | | Returns: "Seed = 1
W = 10
H = 10
C =
01000011101101111101" | |
|
| 1) | |
| | | Returns:
"Seed = 2
W = 23
H = 50
C =
001011011000000111111101011001100100000101100000111101000010
1100011010111101010001010111101110010000" | |
|
| 2) | |
| | | Returns:
"Seed = 3
W = 99
H = 29
C =
0111101110110000011101101001110001111110110100111111011101" | |
|
| 3) | |
| | | Returns:
"Seed = 4
W = 52
H = 83
C =
011000100000111011100100110110111110010010011001010011011111
000000111011101001010000101111100111010010110111001011111000
0100111000100011010010001101010101001011011000" | |
|
| 4) | |
| | | Returns:
"Seed = 5
W = 83
H = 59
C =
011011110010110100111011101001001100000111011100001001010010
1100111000111010101111111001111010110100101111010110011101" | |
|
| 5) | |
| | | Returns:
"Seed = 6
W = 34
H = 36
C =
100001010000010100111101001011111000110010101101010011010000
111010101000" | |
|
| 6) | |
| | | Returns:
"Seed = 7
W = 98
H = 54
C =
001011010100011110100101101000010000001110000001010011110111
000110010101110100100101110110100010110110001010" | |
|
| 7) | |
| | | Returns:
"Seed = 8
W = 49
H = 30
C =
110100001111010110000101110111111101011110010000111001011100" | |
|
| 8) | |
| | | Returns:
"Seed = 9
W = 55
H = 74
C =
111000111001100011011010011010110010010101110100000101111000
100001000000011111011000010011100001010011000111001000001000
0110011110011001001110001011" | |
|
| 9) | |
| | | Returns:
"Seed = 10
W = 84
H = 41
C =
011011110110001000100001100000110100001101100001101011110000
0000010010011100101001" | |
|
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.