Marathon Match 34
|| 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.
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).
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.
As usual, a visualizer is available.
|Parameters:||int, int, String|
|Method signature:||int init(int W, int H, String C)|
|Method signature:||int rotateSquare(int board)|
|(be sure your methods are public)|
|-||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.|
Seed = 1
W = 10
H = 10
Seed = 2
W = 23
H = 50
Seed = 3
W = 99
H = 29
Seed = 4
W = 52
H = 83
Seed = 5
W = 83
H = 59
Seed = 6
W = 34
H = 36
Seed = 7
W = 98
H = 54
Seed = 8
W = 49
H = 30
Seed = 9
W = 55
H = 74
Seed = 10
W = 84
H = 41
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)2010, TopCoder, Inc. All rights reserved.