JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 34
Problem: CircuitConstruction

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)
    
Seed = 1
W = 10
H = 10
C = 
        01000011101101111101
1)
    
Seed = 2
W = 23
H = 50
C = 
        001011011000000111111101011001100100000101100000111101000010
        1100011010111101010001010111101110010000
2)
    
Seed = 3
W = 99
H = 29
C = 
        0111101110110000011101101001110001111110110100111111011101
3)
    
Seed = 4
W = 52
H = 83
C = 
        011000100000111011100100110110111110010010011001010011011111
        000000111011101001010000101111100111010010110111001011111000
        0100111000100011010010001101010101001011011000
4)
    
Seed = 5
W = 83
H = 59
C = 
        011011110010110100111011101001001100000111011100001001010010
        1100111000111010101111111001111010110100101111010110011101
5)
    
Seed = 6
W = 34
H = 36
C = 
        100001010000010100111101001011111000110010101101010011010000
        111010101000
6)
    
Seed = 7
W = 98
H = 54
C = 
        001011010100011110100101101000010000001110000001010011110111
        000110010101110100100101110110100010110110001010
7)
    
Seed = 8
W = 49
H = 30
C = 
        110100001111010110000101110111111101011110010000111001011100
8)
    
Seed = 9
W = 55
H = 74
C = 
        111000111001100011011010011010110010010101110100000101111000
        100001000000011111011000010011100001010011000111001000001000
        0110011110011001001110001011
9)
    
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)2010, TopCoder, Inc. All rights reserved.