TopCoder problem "BinaryBoard" used in TCO05 Semi 1 (Division I Level Two)



Problem Statement

    

We have a 6 x 6 square board, and we place in each square one of the digits 0 and 1. On this board we can then read 12 binary numbers, 6 horizontal and 6 vertical. We call the horizontal numbers "H1" (the number in the first row) to "H6" (the number in the last row) and the vertical numbers "V1" (the number in the first column) to "V6" (the number in the last column). We will fill in the board so that the 12 numbers are distinct and we can sort them in strictly increasing order.

You will be given order, a String[] containing the names of the 12 numbers in order of increasing values, and are to return a String[] representing the digits in the board. The ith element of the return value shall represent the ith row. The constraints will guarantee that there is exactly one way to place the digits 0 and 1 in the board so that the given order is created. See the first example for more details.

 

Definition

    
Class:BinaryBoard
Method:board
Parameters:String[]
Returns:String[]
Method signature:String[] board(String[] order)
(be sure your method is public)
    
 

Constraints

-order will contain exactly 12 elements.
-Each element of order will contain exactly 2 characters. The first character will be 'H' or 'V', the second character will be a digit between '1' and '6', inclusive.
-All elements of order will be different.
-The input values will be such that there is exactly one board satisfying the given order.
 

Examples

0)
    
{"V2", "V5", "H4", "V6", "H5", "H3", "V4", "H1", "V3", "V1", "H6", "H2"}
Returns: {"101100", "111011", "100011", "011101", "011111", "111010" }

The 12 numbers in the rows and columns of the returned board are:

H1 = 101100     V1 = 111001
H2 = 111011     V2 = 010111
H3 = 100011     V3 = 110111
H4 = 011101     V4 = 100110
H5 = 011111     V5 = 011011
H6 = 111010     V6 = 011110

It is easy to verify that this conforms to the given order: V2 < V5 < H4 < ... < H2.

1)
    
{"V4", "H4", "H2", "V1", "H5", "V6", "H6", "H3", "V3", "H1", "V2", "V5"}
Returns: {"111011", "011110", "110011", "011011", "101100", "101111" }
2)
    
{"V4", "H6", "H3", "V1", "H2", "H1", "H4", "V3", "V6", "H5", "V5", "V2"}
Returns: {"011011", "010000", "000011", "100000", "101010", "000010" }
3)
    
{"H1", "H6", "V1", "H5", "H3", "V2", "V4", "H2", "V3", "V5", "V6", "H4"}
Returns: {"001111", "111011", "011011", "111111", "010101", "010010" }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4820

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8098&pm=4820

Writer:

gepa

Testers:

PabloGilberto , lbackstrom , Yarin , vorthys , Olexiy

Problem categories:

Simple Search, Iteration