Register Now
Member Count: 627,697 - April 23, 2014  [Get Time]
Login
long_comps_intel  Problem Statement
Contest: Intel Multi-Threading Competition 2
Problem: Sudoku

Problem Statement

    Sudoku is a Japanese game which has become extremely popular recently. In the game, we try to fill an N2 x N2 grid with integers from 1 to N2. The rules state that each row and column must contain exactly one occurrence of each of the N2 integers. Additionally, each of the N2 aligned N x N subsquares must also contain exactly one occurrence of each integer. The following is a valid Sudoku grid with N = 3.



The game is to figure out how the whole grid is filled in, given the numbers from just a few of the cells in the grid. Obviously, the more information you have, the easier the problem becomes. In this problem, you will start with an empty grid. You will then make a sequence of queries, and the contents of the cell that you query will be revealed to you. Eventually, you will have enough information that you should be able to uniquely determine the values of all the cells. You will be scored based on the number of queries that you make, combined with the total amount of time from start to finish for a particular test case. Your score for a particular test case will be proportional to 2-queries/(0.1+total execution time). Naturally, if your answer is incorrect for any reason, you will get a 0 for that test case. Additionally, if you repeat the same query more than once, you will get a 0. Your total score will be proportional to the sum over i of SCOREi/OPTi, where OPTi is the highest score for a test case i, and SCOREi is your score for that case.



You will be allowed a total processing time of 1 minute per test case over all queries, but only 5 seconds processing time from one query to the next.



Your class should have a method initialize, which takes an int, 3<=N<=8, corresponding to the size of the grid (3 above). The initialize method should return your first query as a int[] with two elements: the row and column of your query, respectively (1-based). The results of each query will be passed to a method queryResults, which takes a int[] (the query you submitted), and a int the result of the query. This method should either returns the next query (as a int[] with two elements), or else the solution to the puzzle, as a int[] with N4 elements, in row major order. Thus, the solution to the above puzzle would be:
{8,2,5,4,7,1,3,9,6,1,9,4,3,2,6,5,7,8,3,7,6,9,8,5,2,4,1,
 5,1,9,7,4,3,8,6,2,6,3,2,5,9,8,4,1,7,4,8,7,6,1,2,9,3,5,
 2,6,3,1,5,9,7,8,4,9,4,8,2,6,7,1,5,3,7,5,1,8,3,4,6,2,9}
 

Definition

    
Class:Sudoku
Method:queryResults
Parameters:int, int[]
Returns:int[]
Method signature:int[] queryResults(int x, int[] query)
 
Method:initialize
Parameters:int
Returns:int[]
Method signature:int[] initialize(int N)
(be sure your methods are public)
    
 

Notes

-The thread limit is 32, including the main thread. Note that you are allowed to have threads running during the time that you make one query and the time that the results of that query are returned to you (though this time will be quite short).
-The memory limit is 1024 megabytes.
-Total execution time starts when the initialize method is called, and ends when your solution returns a solution. It includes the time spent between your issuance of a query and its result.
-When testing examples, your score for a particular test will be the number of queries you made, plus the fraction of the 60 seconds that you used. For instance, a score of 130.5 indicates you spent 30 seconds and made 130 queries before returning the correct answer. A score of 0 indicates that your solution did not return a correct answer.
-For each value of N, there are 2N test cases with that N (not including the examples). The maximum possible score is 6600 (100 per test case).
-Queries are 1-based.
-When computing the time used by your solution, the time between your queries and their answers is included. For large grids this may be significant. For instance, querying all 4096 locations when N = 8 takes roughly 2.5 seconds.
 

Examples

0)
    
8 2 5 4 7 1 3 9 6 
1 9 4 3 2 6 5 7 8 
3 7 6 9 8 5 2 4 1 
5 1 9 7 4 3 8 6 2 
6 3 2 5 9 8 4 1 7 
4 8 7 6 1 2 9 3 5 
2 6 3 1 5 9 7 8 4 
9 4 8 2 6 7 1 5 3 
7 5 1 8 3 4 6 2 9 
1)
    
10 5 8 7 2 13 9 6 14 1 16 12 3 15 4 11 
1 4 15 13 14 8 7 3 10 11 9 5 6 16 12 2 
11 6 3 14 10 16 4 12 13 15 2 8 5 1 7 9 
2 12 9 16 11 1 5 15 7 4 6 3 13 8 10 14 
4 11 7 3 8 2 14 5 15 16 1 10 9 12 6 13 
8 13 14 2 3 4 6 16 12 7 5 9 10 11 1 15 
16 1 6 9 12 15 10 13 3 2 14 11 8 4 5 7 
12 15 5 10 1 9 11 7 6 8 4 13 16 2 14 3 
14 9 2 1 13 7 15 8 16 10 11 6 12 5 3 4 
7 3 12 4 6 11 16 9 8 5 13 1 15 14 2 10 
15 8 13 11 5 14 2 10 4 3 12 7 1 6 9 16 
6 10 16 5 4 12 3 1 9 14 15 2 7 13 11 8 
3 14 11 8 7 5 12 4 1 13 10 16 2 9 15 6 
13 2 4 6 9 10 8 14 5 12 3 15 11 7 16 1 
9 16 1 12 15 3 13 11 2 6 7 14 4 10 8 5 
5 7 10 15 16 6 1 2 11 9 8 4 14 3 13 12 
2)
    
12 20 18 3 24 16 2 15 19 5 7 11 25 21 14 13 10 1 23 9 17 6 22 8 4 
5 16 1 15 23 10 24 13 8 9 6 20 12 4 17 2 22 18 7 19 25 3 11 14 21 
25 7 6 13 9 20 17 3 18 4 23 22 8 19 10 21 15 11 14 5 16 1 2 24 12 
22 10 2 19 21 11 1 7 14 6 13 3 18 16 24 12 8 25 17 4 20 15 5 23 9 
11 8 17 4 14 23 25 12 22 21 15 2 9 5 1 6 24 16 20 3 19 18 13 10 7 
23 13 5 2 20 19 21 11 6 16 3 10 1 7 9 15 17 12 22 18 14 25 24 4 8 
15 24 3 22 10 7 4 2 13 14 21 8 16 12 19 23 1 6 5 25 11 9 20 18 17 
1 21 7 11 18 25 9 17 20 8 22 14 5 23 2 4 16 19 24 10 6 13 3 12 15 
14 17 19 9 6 12 3 18 23 22 24 13 4 25 15 11 21 7 8 20 2 16 10 5 1 
4 12 25 16 8 24 10 5 1 15 17 6 11 20 18 3 2 13 9 14 21 19 23 7 22 
24 6 16 23 5 21 20 9 15 17 11 25 10 14 13 22 12 3 19 8 18 4 7 1 2 
13 19 12 18 17 22 23 8 24 10 1 4 6 9 3 16 7 2 21 11 15 5 14 25 20 
20 11 4 7 25 5 19 6 12 3 8 16 2 22 23 14 18 15 1 24 9 10 17 21 13 
3 14 15 8 22 2 7 4 25 1 18 19 21 24 5 17 9 20 10 13 12 23 6 11 16 
10 9 21 1 2 18 14 16 11 13 12 15 20 17 7 25 6 5 4 23 3 22 8 19 24 
19 1 13 6 7 3 16 24 9 12 4 17 14 10 20 8 25 23 18 2 5 21 15 22 11 
18 25 24 5 11 6 22 1 2 19 16 7 13 8 12 10 4 21 3 15 23 20 9 17 14 
21 22 14 17 3 4 11 23 10 7 5 18 15 2 6 20 19 9 13 1 24 8 12 16 25 
2 4 8 10 15 13 5 25 21 20 9 23 22 3 11 24 14 17 16 12 1 7 19 6 18 
16 23 9 20 12 8 15 14 17 18 19 21 24 1 25 7 5 22 11 6 10 2 4 13 3 
17 3 10 25 13 9 8 21 7 23 20 12 19 15 16 18 11 24 6 22 4 14 1 2 5 
9 2 11 21 19 17 18 10 16 24 14 5 23 13 8 1 3 4 15 7 22 12 25 20 6 
6 15 20 24 4 1 12 22 5 2 10 9 7 11 21 19 13 14 25 16 8 17 18 3 23 
8 18 22 14 1 15 13 20 3 25 2 24 17 6 4 5 23 10 12 21 7 11 16 9 19 
7 5 23 12 16 14 6 19 4 11 25 1 3 18 22 9 20 8 2 17 13 24 21 15 10 
3)
    
22 27 32 19 9 26 3 17 28 2 24 6 18 33 29 7 14 31 5 16 36 20 8 34 12 10 15 30 23 35 13 11 21 25 4 1 
29 5 13 11 25 18 14 26 12 30 33 31 20 21 28 16 35 15 4 2 10 1 9 6 27 19 17 22 34 36 8 7 23 24 32 3 
17 1 34 3 14 12 29 11 25 4 19 16 32 24 36 5 8 6 23 33 22 27 28 21 31 20 7 18 9 13 10 26 2 30 15 35 
28 4 23 31 36 20 21 32 9 22 15 18 3 10 25 30 2 1 13 29 24 7 19 35 16 33 26 6 8 11 34 12 14 17 5 27 
8 10 7 15 33 21 23 36 5 1 35 13 12 34 9 27 11 19 30 31 32 25 26 17 24 3 29 14 4 2 20 28 6 22 18 16 
16 6 35 24 30 2 34 8 20 7 27 10 17 4 13 23 22 26 15 3 12 14 11 18 1 5 32 28 21 25 29 33 9 19 31 36 
19 23 14 30 16 27 5 18 31 35 12 21 24 28 22 25 36 4 26 34 13 32 7 29 10 15 2 9 3 17 6 1 8 20 33 11 
15 32 4 21 13 31 17 16 11 24 6 19 2 20 14 1 3 8 28 10 5 18 30 12 25 34 35 36 22 33 27 23 7 26 29 9 
20 24 33 6 34 3 28 29 4 27 2 15 23 19 17 21 16 9 22 35 25 11 14 8 30 31 1 5 26 7 32 36 13 18 12 10 
10 7 11 36 12 29 22 33 30 9 8 25 26 5 31 18 34 35 17 23 21 6 1 24 32 13 27 20 19 16 14 15 4 2 3 28 
26 35 8 25 17 5 32 14 1 3 13 36 6 7 27 12 10 11 33 20 15 19 2 9 18 23 24 29 28 4 31 30 16 34 22 21 
2 18 9 22 1 28 26 34 10 20 7 23 15 29 33 32 30 13 27 4 16 36 3 31 11 8 12 21 6 14 24 17 35 5 19 25 
24 20 6 34 29 32 18 15 3 14 5 8 31 27 10 17 25 2 36 13 1 35 12 11 22 16 28 26 33 19 21 4 30 7 9 23 
5 19 1 35 27 7 25 31 26 29 22 28 9 16 6 14 24 36 10 32 8 4 15 23 34 17 30 2 12 21 11 3 33 13 20 18 
9 26 22 12 31 25 33 35 6 13 16 11 8 32 3 15 19 21 7 30 18 17 24 5 36 4 14 10 20 23 28 34 1 29 27 2 
30 13 36 33 11 4 2 24 32 23 17 27 22 1 18 35 20 12 9 21 26 28 34 19 3 25 8 7 29 15 5 6 10 31 16 14 
21 16 2 18 15 17 7 12 19 34 10 9 28 30 4 13 33 23 6 14 29 22 20 3 5 11 31 1 27 32 25 8 36 35 24 26 
14 8 28 23 3 10 30 4 36 21 20 1 7 11 34 26 29 5 31 27 2 33 25 16 6 35 9 24 13 18 15 19 32 12 17 22 
7 29 21 28 6 11 4 9 24 15 26 32 1 35 23 31 18 33 3 19 17 34 22 10 8 36 13 27 2 12 16 25 20 14 30 5 
18 15 20 14 4 13 12 5 35 36 11 34 10 2 32 8 7 25 16 9 6 29 21 30 33 26 22 17 24 3 19 27 28 23 1 31 
25 34 17 8 2 30 13 3 33 19 31 22 16 12 26 24 21 27 35 7 28 15 5 1 14 6 11 23 10 20 4 18 29 9 36 32 
33 36 27 5 35 9 10 2 8 16 1 30 11 15 19 3 28 14 20 24 23 26 18 32 7 29 4 25 31 34 12 22 17 6 21 13 
1 12 10 32 19 16 20 25 17 6 23 7 4 9 5 22 13 29 11 8 27 31 36 14 35 28 21 15 18 30 33 24 26 3 2 34 
23 3 31 26 24 22 27 21 29 18 28 14 34 17 20 36 6 30 12 25 4 13 33 2 19 1 5 32 16 9 7 10 11 8 35 15 
6 14 15 4 10 1 24 28 22 11 3 5 29 8 35 33 32 34 21 17 31 16 23 13 2 7 19 12 30 26 18 9 27 36 25 20 
27 25 19 29 21 34 15 13 2 31 30 17 14 3 7 11 26 22 18 12 33 5 6 20 23 9 36 4 35 10 1 32 24 16 28 8 
31 11 12 2 28 24 8 6 18 26 4 29 36 23 21 20 15 17 19 1 3 9 32 7 13 27 25 16 5 22 35 14 34 33 10 30 
13 33 3 16 7 23 19 20 27 32 9 12 5 25 24 2 4 28 34 22 30 10 35 36 17 14 18 8 11 1 26 21 31 15 6 29 
32 17 30 20 18 36 16 23 21 25 14 35 13 6 12 9 1 10 2 26 11 8 29 27 28 24 33 34 15 31 22 5 3 4 7 19 
35 22 5 9 26 8 1 7 34 10 36 33 30 31 16 19 27 18 25 15 14 24 4 28 20 21 6 3 32 29 23 2 12 11 13 17 
11 31 25 7 23 6 9 10 14 5 34 2 21 13 1 29 12 24 32 18 20 30 27 4 15 22 3 35 17 8 36 16 19 28 26 33 
4 21 29 13 8 19 6 22 15 33 32 26 27 36 30 34 17 3 24 5 35 23 16 25 9 12 10 31 14 28 2 20 18 1 11 7 
34 2 24 10 20 15 11 27 7 28 25 3 35 26 8 4 31 16 1 6 9 21 17 33 29 18 23 19 36 5 30 13 22 32 14 12 
12 9 18 27 5 33 35 19 13 8 29 20 25 22 2 28 23 32 14 36 7 3 10 26 4 30 16 11 1 24 17 31 15 21 34 6 
36 30 16 17 22 14 31 1 23 12 21 24 19 18 11 10 9 7 29 28 34 2 13 15 26 32 20 33 25 6 3 35 5 27 8 4 
3 28 26 1 32 35 36 30 16 17 18 4 33 14 15 6 5 20 8 11 19 12 31 22 21 2 34 13 7 27 9 29 25 10 23 24 
4)
    
39 10 40 5 31 18 49 26 27 45 22 15 21 8 34 17 32 1 43 2 12 7 20 6 25 19 44 29 13 46 24 3 16 47 9 41 11 4 28 38 37 14 23 35 33 48 42 36 30 
48 41 32 2 11 13 29 28 33 36 46 10 25 7 3 38 44 30 20 47 23 4 42 8 17 45 43 27 49 37 40 35 22 34 26 6 39 21 18 16 31 5 9 15 14 24 12 19 1 
38 43 4 24 7 8 1 6 37 35 18 20 42 3 9 36 41 15 5 14 31 34 2 26 22 10 33 23 12 25 28 48 30 21 29 27 45 46 17 32 19 49 44 13 39 47 40 11 16 
30 26 3 19 22 45 42 34 17 29 11 24 16 14 40 10 33 46 37 8 35 49 18 47 5 13 9 15 39 23 32 6 38 2 4 25 44 48 12 43 36 1 27 31 7 21 28 20 41 
36 17 34 27 44 47 9 32 12 40 19 5 1 4 24 11 21 25 28 39 22 16 31 46 37 30 48 41 7 15 33 14 45 10 20 29 35 3 26 23 13 42 8 38 43 6 2 49 18 
28 12 37 21 14 25 6 23 9 2 30 47 48 49 19 18 27 26 16 45 13 36 11 35 24 3 39 38 44 42 31 43 5 41 1 7 20 33 40 15 10 8 29 17 46 22 32 34 4 
15 46 35 23 33 20 16 43 41 39 38 44 31 13 29 4 7 48 49 42 6 12 28 1 21 14 40 32 17 19 27 8 11 36 18 30 22 2 47 9 24 34 37 3 26 5 25 10 45 
46 5 25 38 20 40 14 33 7 34 28 3 6 37 18 30 22 29 39 12 48 43 49 23 2 17 32 10 26 47 19 4 1 35 41 36 42 15 27 21 11 31 13 8 16 44 9 45 24 
41 19 11 48 34 27 2 40 22 18 13 43 12 15 33 35 23 45 3 21 26 37 8 7 16 39 31 25 10 36 9 17 14 29 49 44 46 24 1 5 47 32 20 6 30 28 4 42 38 
12 6 42 28 35 33 21 48 29 16 36 49 46 47 5 41 1 43 11 37 19 20 27 4 9 24 26 22 8 32 45 44 15 38 31 3 34 30 39 13 23 40 25 14 2 7 18 17 10 
32 18 23 37 4 3 7 8 5 24 45 30 14 1 49 47 34 38 17 31 25 44 46 28 29 48 15 11 16 40 13 21 20 42 12 2 9 6 10 26 33 35 39 19 36 41 22 43 27 
9 45 26 43 1 24 8 44 19 38 42 39 17 2 36 13 14 27 10 46 32 47 40 30 6 41 5 33 28 34 7 37 25 11 3 12 18 22 16 49 20 4 21 23 48 15 35 31 29 
47 15 13 16 39 29 44 41 23 21 20 4 10 31 7 24 6 9 2 40 28 1 3 18 42 38 35 36 46 43 22 27 48 30 5 17 8 19 14 45 25 37 12 32 49 11 34 33 26 
49 31 10 36 30 17 22 35 11 26 9 25 27 32 44 16 15 8 4 20 42 13 14 21 19 34 12 45 18 39 6 33 23 24 2 28 48 41 38 29 7 43 5 47 40 37 46 1 3 
33 11 1 9 15 39 26 46 49 48 34 29 3 23 28 45 10 41 22 27 18 31 7 38 20 37 4 14 2 12 17 47 44 6 32 24 30 43 19 36 42 21 35 25 5 16 13 40 8 
2 21 30 12 25 5 41 18 40 1 7 13 32 22 48 34 20 11 23 4 14 9 17 42 10 36 24 43 29 49 37 28 46 45 27 35 33 47 3 8 6 16 26 39 15 31 19 38 44 
43 36 44 4 42 38 32 17 8 31 39 21 20 45 35 7 29 33 26 9 30 3 12 16 1 15 34 6 24 11 18 41 19 25 13 23 14 40 5 2 49 28 22 48 47 10 27 46 37 
37 13 19 6 48 31 28 9 24 43 10 14 4 35 16 1 3 2 12 5 15 40 47 45 26 32 30 44 36 38 21 20 33 8 42 22 27 39 34 11 46 25 7 18 29 17 41 23 49 
8 24 14 34 17 23 35 12 42 11 25 41 28 5 31 39 46 13 38 19 47 21 22 33 27 18 49 48 40 9 16 7 4 3 15 45 29 44 37 10 32 26 43 1 6 36 30 2 20 
22 47 45 10 16 46 40 15 26 6 33 19 44 27 25 21 49 36 42 32 37 11 13 29 8 23 41 2 30 5 1 39 34 43 35 18 31 17 20 7 38 48 4 28 3 14 24 9 12 
18 27 20 29 49 7 3 2 36 47 37 16 38 30 8 40 24 17 6 44 43 35 19 39 28 46 25 5 22 14 10 26 31 23 48 9 1 13 41 4 12 15 11 45 42 34 21 32 33 
5 14 29 31 2 26 18 10 21 37 47 38 24 48 43 9 30 20 27 49 45 23 39 34 41 25 19 13 1 22 35 11 36 28 33 8 6 12 15 40 16 7 17 4 32 46 44 3 42 
11 25 46 44 43 35 38 4 39 32 23 12 8 6 13 5 19 14 40 17 41 27 16 48 49 1 36 7 15 30 47 24 26 20 37 42 21 29 33 3 18 9 45 10 34 2 31 22 28 
10 32 47 1 23 34 30 31 20 14 40 33 41 28 2 3 48 39 35 6 7 5 45 44 38 8 11 24 9 4 42 16 21 12 19 46 43 27 22 37 17 13 36 29 25 26 49 18 15 
7 42 8 13 36 12 4 27 43 3 44 11 34 29 38 23 31 22 32 28 24 30 15 2 47 21 17 9 41 18 25 46 40 48 6 10 5 26 49 1 39 45 33 37 35 20 16 14 19 
40 22 17 39 45 9 48 19 18 42 49 35 15 36 11 33 37 16 25 29 21 10 26 12 4 43 28 46 14 3 44 13 27 5 8 20 32 31 2 24 34 38 30 7 23 1 47 41 6 
6 3 33 49 19 21 15 22 46 7 16 17 5 25 12 26 47 4 1 36 34 42 35 31 32 20 37 18 23 10 2 29 43 39 45 11 28 14 44 48 41 30 24 40 8 13 38 27 9 
16 28 27 20 41 37 24 13 2 30 1 45 26 9 10 42 18 44 46 15 8 6 33 22 14 40 29 3 38 7 34 31 49 32 17 19 25 36 35 47 4 23 48 5 12 43 11 21 39 
29 9 36 35 13 11 12 20 6 5 14 23 39 42 46 15 2 28 7 16 10 24 32 19 30 22 27 4 47 48 49 25 3 1 21 38 26 34 8 41 40 44 18 33 17 45 43 37 31 
45 44 39 47 24 6 34 3 10 28 2 31 7 17 21 48 35 49 14 13 27 46 43 41 12 9 8 16 5 26 29 38 37 19 23 33 4 18 30 42 22 11 40 36 1 32 20 15 25 
42 30 49 18 21 14 37 38 32 15 4 1 35 19 20 43 45 31 24 3 11 33 23 17 36 2 6 26 34 8 46 22 12 40 44 47 10 9 7 25 28 39 41 16 13 27 5 29 48 
20 7 5 25 3 41 19 37 16 46 21 27 9 11 6 12 26 34 36 30 4 18 44 13 15 29 10 40 35 17 43 32 42 33 14 1 23 49 48 31 45 2 38 22 28 8 39 24 47 
23 1 15 32 8 16 33 30 48 13 43 36 49 26 17 22 38 40 44 25 29 28 34 5 31 11 47 42 4 45 41 10 24 18 39 37 3 20 21 35 14 27 6 46 19 9 7 12 2 
4 2 48 26 27 43 31 29 45 25 12 22 33 40 23 8 42 47 41 18 5 39 38 3 35 7 1 37 11 6 20 36 9 13 28 32 19 16 24 46 15 17 14 44 21 49 10 30 34 
17 40 38 22 10 28 46 24 34 44 41 8 47 18 1 37 39 32 19 33 9 48 25 14 45 49 20 21 31 2 30 15 7 27 16 13 36 5 43 6 29 12 42 26 4 3 23 35 11 
13 33 2 30 18 4 47 25 31 49 35 28 23 12 37 32 17 6 48 43 44 29 24 20 39 26 7 34 27 16 11 42 10 9 38 5 40 45 36 22 1 46 15 21 41 19 3 8 14 
25 38 41 11 40 19 17 16 30 10 24 2 29 46 39 28 5 12 21 22 49 15 37 36 33 47 3 31 48 13 4 1 8 14 43 26 7 42 23 44 35 20 34 9 27 18 45 6 32 
1 23 24 7 37 32 27 42 15 9 8 40 11 44 14 46 4 18 33 26 36 45 41 49 48 5 16 12 19 31 3 30 35 17 22 39 2 28 6 34 21 10 47 20 38 25 29 13 43 
3 20 22 14 26 36 45 47 1 41 17 32 37 39 15 2 11 35 30 7 16 38 4 43 13 6 21 19 33 29 5 34 18 44 25 49 12 8 31 27 9 24 46 42 10 23 48 28 40 
21 48 12 8 28 44 10 5 38 22 27 26 18 34 47 29 9 3 31 41 20 25 1 40 23 42 2 35 32 24 15 45 6 46 7 14 13 37 4 33 43 19 16 49 11 30 36 39 17 
34 16 9 46 29 42 43 21 14 33 6 7 19 20 45 27 8 23 13 10 1 32 30 11 18 44 22 28 37 41 36 12 39 49 40 15 47 38 25 17 48 3 31 2 24 4 26 5 35 
35 39 31 15 6 49 5 36 13 4 3 48 45 43 42 19 25 24 34 38 40 8 10 9 46 27 14 17 21 20 23 2 28 26 47 16 41 11 32 18 30 29 1 12 22 33 37 44 7 
19 49 16 17 32 1 13 11 47 20 48 42 22 41 26 31 40 37 15 23 2 14 36 27 34 4 45 39 3 33 8 9 29 7 24 43 38 10 46 12 5 18 28 30 44 35 6 25 21 
14 35 43 33 12 15 11 45 4 27 29 37 13 10 30 25 28 42 8 24 3 17 48 32 44 31 46 20 6 21 39 5 47 16 36 40 49 23 9 19 26 41 2 34 18 38 1 7 22 
44 4 7 42 9 30 23 1 3 8 26 6 36 24 32 14 43 19 29 34 39 22 5 10 40 35 38 47 20 27 48 18 41 37 46 21 15 25 45 28 2 33 49 11 31 12 17 16 13 
26 8 28 3 38 2 36 39 35 23 31 9 43 21 27 6 16 10 45 48 46 19 29 24 11 12 18 30 25 1 14 49 13 15 34 4 17 7 42 20 44 22 32 41 37 40 33 47 5 
24 29 18 40 46 48 25 14 28 19 5 34 2 38 4 20 13 21 47 35 17 41 9 37 7 33 42 49 43 44 12 23 32 22 10 31 16 1 11 30 8 6 3 27 45 39 15 26 36 
31 37 6 41 47 10 20 7 44 17 15 46 30 16 22 49 12 5 18 1 33 26 21 25 3 28 13 8 45 35 38 40 2 4 11 34 24 32 29 39 27 36 19 43 9 42 14 48 23 
27 34 21 45 5 22 39 49 25 12 32 18 40 33 41 44 36 7 9 11 38 2 6 15 43 16 23 1 42 28 26 19 17 31 30 48 37 35 13 14 3 47 10 24 20 29 8 4 46 
5)
    
57 44 59 10 25 14 3 16 39 21 18 1 37 58 8 40 35 42 6 26 54 20 43 51 9 49 12 29 4 48 33 22 46 13 62 47 31 64 19 34 50 23 55 2 53 30 24 63 52 15 28 60 36 61 5 41 45 7 27 38 11 17 56 32 
55 63 28 30 53 52 2 61 31 46 24 62 64 36 15 5 32 45 50 16 21 25 44 9 27 56 42 38 34 23 59 13 37 57 17 39 11 3 22 41 29 26 35 54 19 47 43 60 7 10 4 51 20 48 12 33 40 18 58 8 14 6 49 1 
4 43 33 29 39 24 19 5 59 17 13 32 20 49 51 60 10 38 41 47 48 22 55 36 7 25 26 16 15 28 3 46 8 18 27 21 56 44 45 2 6 37 9 40 12 34 52 61 14 11 58 62 31 42 64 1 54 63 30 53 57 50 23 35 
46 22 31 9 1 62 13 64 26 7 12 38 23 4 43 34 11 14 2 40 37 8 29 19 44 10 54 17 47 35 18 58 50 63 6 33 48 32 53 30 16 20 21 42 51 49 41 36 39 3 57 59 25 45 56 27 5 52 28 61 60 55 24 15 
58 42 12 6 35 51 26 49 25 27 48 10 29 22 56 2 33 4 61 53 13 52 30 5 11 39 19 45 41 63 32 50 15 36 40 55 54 1 28 60 57 44 38 14 59 3 8 7 21 18 37 23 24 9 16 17 43 46 62 20 64 31 47 34 
32 27 56 38 45 15 18 41 14 11 54 35 19 52 42 61 58 1 60 17 7 57 24 28 51 37 20 8 36 5 6 40 12 26 4 43 23 49 29 9 46 22 62 33 48 13 31 64 55 63 47 30 2 50 53 34 16 3 10 21 59 25 44 39 
37 40 50 47 8 34 20 60 6 57 9 53 55 63 30 28 39 3 31 46 49 27 23 15 64 2 62 21 52 61 1 24 42 38 7 14 25 59 16 5 10 45 11 18 32 17 58 56 35 44 19 54 26 13 43 29 48 41 4 51 36 33 22 12 
11 17 48 54 7 23 21 36 16 45 50 3 33 47 44 41 59 56 34 62 12 18 64 63 53 31 43 14 30 60 57 55 51 24 35 20 10 58 52 61 4 27 25 1 39 15 28 5 38 32 22 40 49 46 6 8 37 9 2 26 29 13 19 42 
18 48 21 7 59 12 50 44 1 4 40 20 8 27 45 13 52 47 55 29 56 37 6 30 49 26 41 11 39 57 10 25 5 23 64 53 9 36 38 63 22 14 28 62 60 46 16 31 61 51 2 32 17 54 3 58 19 34 24 35 43 15 42 33 
6 15 42 16 20 29 22 45 51 24 44 60 14 48 35 50 64 46 7 34 25 39 40 54 2 23 28 30 33 13 21 8 17 3 31 59 37 43 11 10 61 57 52 49 58 32 38 12 63 26 53 56 1 19 27 18 62 47 5 36 4 41 9 55 
34 5 25 13 2 9 57 8 46 62 32 61 22 18 10 63 41 28 16 23 3 60 11 27 37 1 58 47 59 17 4 38 48 20 56 49 6 54 35 21 7 36 19 24 40 43 26 33 30 42 52 55 50 64 15 31 12 45 29 44 51 53 39 14 
35 39 49 26 32 56 38 3 36 53 43 41 47 33 9 55 31 15 17 24 45 62 2 59 5 19 61 52 63 29 48 51 60 46 14 28 34 30 57 12 11 50 64 4 42 27 20 18 44 16 13 25 21 10 40 6 22 23 7 58 37 54 1 8 
62 47 37 40 54 33 63 23 21 19 17 39 2 56 25 12 57 49 35 18 8 26 9 44 55 53 15 34 24 31 27 14 16 4 42 51 58 50 32 29 1 6 48 10 3 59 5 45 36 38 20 22 43 41 7 11 64 60 61 52 30 28 46 13 
64 60 11 14 17 30 28 27 58 37 57 59 42 6 54 29 5 61 63 36 22 4 10 12 45 44 32 56 16 7 43 3 40 8 18 19 52 24 26 1 15 53 13 41 35 9 51 55 23 49 34 39 46 33 47 62 31 38 50 25 20 2 21 48 
24 36 4 1 10 46 53 58 23 34 64 5 52 28 38 31 51 50 33 19 43 48 21 32 40 42 18 6 35 20 62 54 22 61 2 41 13 15 7 55 56 47 30 25 44 39 17 29 9 14 60 8 12 37 45 57 49 27 11 59 26 63 16 3 
52 41 43 51 19 31 61 55 15 3 7 30 11 16 26 49 14 53 1 13 58 42 20 38 46 50 60 36 9 64 22 12 25 62 47 44 39 45 27 33 2 54 34 8 21 63 37 23 28 4 5 24 35 29 48 59 6 17 56 57 40 32 18 10 
15 12 45 24 11 35 48 7 54 22 38 58 3 10 49 32 2 63 64 4 52 19 53 50 41 57 23 59 6 44 30 29 14 37 26 31 51 33 13 46 18 40 5 61 28 36 27 34 16 39 25 17 56 8 1 21 42 62 55 60 9 47 43 20 
49 20 55 23 58 64 47 1 19 14 2 12 27 7 37 18 40 31 32 30 16 10 17 6 3 51 56 4 21 45 38 53 59 5 52 25 44 29 39 57 35 42 54 48 22 60 11 26 41 61 43 33 34 62 9 36 8 15 63 28 13 24 50 46 
63 56 39 22 62 6 59 25 60 42 29 16 35 50 21 48 8 9 44 7 47 49 14 46 15 24 34 26 28 40 55 31 10 58 43 11 17 4 18 27 32 1 45 38 37 33 3 13 19 12 54 57 64 51 20 23 53 30 41 5 52 36 2 61 
28 3 36 50 43 32 5 37 41 47 8 56 15 34 11 23 20 33 51 48 39 54 18 26 58 7 63 13 46 42 14 1 49 35 61 12 38 6 21 64 19 29 59 17 9 62 10 2 22 60 30 53 52 55 31 24 44 4 45 27 25 40 57 16 
16 31 52 4 38 54 30 46 28 63 55 57 53 9 1 62 60 5 27 11 61 43 37 34 17 35 48 18 64 10 39 36 20 50 24 40 32 42 47 23 25 58 49 56 41 8 14 6 3 45 15 29 13 59 44 2 21 33 12 7 19 22 26 51 
40 10 29 33 44 26 14 9 4 51 36 17 31 43 59 46 13 24 12 25 35 3 45 56 61 20 22 5 62 2 8 52 19 30 28 60 15 41 63 53 55 16 57 39 47 21 7 50 27 6 48 37 42 32 38 49 18 64 34 11 1 23 58 54 
51 61 41 53 27 2 8 34 5 39 25 44 45 13 6 20 42 22 21 38 57 59 1 29 60 33 11 12 50 19 16 43 56 54 36 9 7 55 3 62 63 15 4 52 24 64 23 30 40 28 35 46 47 18 58 26 17 31 49 32 10 48 14 37 
17 21 13 60 57 19 42 18 61 52 26 40 24 30 33 64 28 36 62 58 41 55 15 23 47 32 49 54 27 37 25 9 1 34 8 45 22 16 2 48 20 43 12 51 31 44 46 53 10 5 14 11 63 7 4 50 3 29 38 56 35 39 59 6 
20 64 63 49 30 47 55 24 48 60 52 28 36 15 16 25 1 6 5 39 14 53 12 7 18 11 10 35 45 38 40 37 3 27 44 32 59 56 34 17 26 33 29 23 13 19 62 4 8 2 46 21 41 31 57 43 50 61 51 42 22 9 54 58 
22 29 57 59 21 16 15 12 10 26 49 14 18 45 32 1 9 60 47 64 46 34 50 48 63 41 5 61 53 24 52 28 7 43 30 8 42 40 51 58 38 11 56 31 17 37 25 27 54 23 44 3 6 39 35 13 2 36 20 55 33 19 62 4 
31 2 46 25 50 53 60 39 20 55 22 33 40 21 27 9 56 54 29 59 30 63 8 35 32 14 4 43 3 51 19 44 47 15 5 52 61 28 36 24 42 7 58 34 64 41 1 57 49 17 62 45 16 11 10 38 23 13 26 6 48 37 12 18 
27 62 32 42 18 45 54 10 8 41 3 63 38 37 58 44 49 23 40 31 55 2 13 16 56 59 7 15 17 25 26 6 11 1 57 4 21 39 9 14 36 48 61 60 5 28 35 24 12 19 33 50 51 20 30 22 47 53 43 34 46 52 64 29 
36 33 1 11 37 40 6 35 64 2 4 50 43 23 39 59 61 26 28 45 17 44 52 57 54 30 27 55 29 9 12 34 38 22 13 62 63 19 46 16 51 8 10 47 20 14 32 3 42 48 56 58 53 25 18 5 7 24 21 41 15 60 31 49 
44 13 17 58 3 7 56 14 62 30 19 51 12 29 57 42 37 25 43 10 4 32 38 11 31 60 64 2 48 22 50 23 18 49 33 26 41 35 20 45 21 9 39 53 55 54 6 46 47 34 36 52 61 15 24 28 63 5 16 1 27 8 40 59 
19 9 61 48 52 4 43 38 56 5 11 34 46 54 13 24 27 58 20 51 18 41 33 21 16 8 57 39 42 62 36 47 6 60 23 29 55 53 31 25 49 12 50 30 63 2 22 15 64 40 26 1 37 14 59 7 32 28 3 45 17 35 10 44 
41 34 5 28 51 8 23 26 53 61 6 7 17 31 47 35 3 62 24 42 19 15 36 22 33 21 46 20 1 58 13 49 54 64 48 50 2 10 12 37 45 18 40 59 43 52 44 16 29 55 9 4 60 27 63 32 38 11 14 39 56 30 25 57 
30 55 20 36 49 3 9 57 32 58 34 6 28 11 64 17 48 27 14 41 38 23 59 1 42 47 40 7 19 21 51 33 29 56 46 16 18 12 25 26 37 24 53 63 50 22 54 62 15 52 61 31 5 35 13 60 10 8 39 43 2 44 4 45 
26 4 64 63 14 38 35 19 50 49 47 2 16 46 36 54 22 40 39 6 29 7 25 43 20 55 24 27 10 11 31 57 9 32 58 3 62 8 17 44 60 52 33 28 61 5 13 48 59 1 23 12 18 56 21 45 51 37 53 30 34 42 15 41 
21 18 27 56 40 39 10 59 43 25 35 48 57 12 7 14 34 37 46 9 24 47 16 4 38 3 17 58 44 32 29 61 31 45 50 63 5 52 30 15 8 64 23 11 6 42 49 1 33 53 41 36 19 2 54 51 20 22 13 62 55 26 60 28 
54 32 22 62 46 37 16 13 29 59 27 24 39 60 3 45 12 52 8 49 31 33 57 18 28 15 30 53 23 14 34 41 35 11 55 38 4 2 42 51 58 25 7 44 10 56 9 17 48 43 50 6 40 47 26 20 1 19 36 64 63 21 61 5 
29 11 47 34 33 25 51 42 44 10 62 8 21 41 18 56 30 2 15 60 63 61 32 55 4 52 36 37 13 1 9 5 64 39 53 23 28 20 14 19 43 59 31 57 38 26 45 40 17 58 24 27 22 49 46 3 35 6 54 12 50 16 48 7 
5 28 53 52 31 44 58 15 38 33 23 42 51 1 40 26 50 11 19 21 62 13 35 17 43 46 16 48 8 59 60 45 24 7 54 61 36 22 10 6 41 3 20 32 2 55 12 39 37 9 63 64 30 34 14 4 25 56 18 49 47 57 29 27 
60 7 23 8 48 17 45 6 22 9 20 37 13 61 4 19 53 10 26 54 64 5 42 3 50 63 39 25 56 12 49 2 33 21 1 34 43 47 41 40 27 30 36 35 14 18 15 51 11 62 55 16 28 57 29 44 58 32 46 31 24 59 52 38 
61 50 2 41 24 1 12 43 52 31 30 55 63 5 53 15 36 44 45 20 51 28 56 58 62 54 6 22 26 18 64 35 57 59 49 27 60 48 37 13 34 21 47 46 29 16 4 19 32 25 8 10 7 38 39 42 14 40 9 17 23 3 33 11 
1 16 7 64 36 59 40 22 37 50 63 43 54 42 12 47 46 8 49 52 34 30 4 31 23 29 53 19 55 26 17 11 41 25 21 35 45 27 44 18 48 5 51 9 57 6 33 38 20 56 3 14 10 58 32 39 13 2 60 15 62 61 28 24 
10 46 38 21 63 20 24 56 27 1 45 11 44 2 17 57 25 35 18 55 32 14 3 42 30 34 9 28 60 50 15 16 26 6 39 64 53 51 58 4 40 62 37 29 49 61 19 59 13 7 12 43 23 36 8 47 33 48 52 54 31 5 41 22 
14 23 18 61 60 11 39 62 49 48 56 64 4 35 34 21 38 20 13 28 10 51 58 40 1 43 44 42 5 8 2 7 63 17 37 36 3 31 59 54 52 41 15 45 30 24 55 32 57 22 29 26 33 6 25 19 46 50 47 16 12 27 53 9 
2 35 26 12 55 49 29 50 30 28 10 31 61 40 46 38 15 64 23 5 60 36 62 41 39 58 33 57 14 47 37 32 52 9 22 48 8 7 24 42 17 13 1 21 18 53 56 25 51 59 27 44 54 16 11 63 4 20 19 3 6 45 34 43 
45 30 44 15 41 42 37 53 9 36 33 29 60 26 52 51 17 12 48 2 6 24 19 47 25 27 35 3 54 4 20 59 43 10 32 13 57 11 56 38 14 63 46 22 16 31 64 58 34 50 21 28 62 5 49 61 39 1 23 18 8 7 55 40 
8 52 6 27 47 13 17 54 3 15 16 23 5 19 24 58 45 57 9 50 26 1 22 37 21 18 38 51 61 41 56 48 34 40 12 46 29 62 33 49 39 28 43 7 36 20 42 10 31 30 64 2 55 4 60 53 59 35 32 14 44 11 63 25 
9 51 19 5 28 48 34 33 18 32 59 25 6 8 22 39 44 43 56 61 11 29 7 53 12 36 13 64 31 49 63 62 55 16 20 2 14 23 1 50 54 60 3 27 26 4 47 35 46 24 45 41 15 40 37 52 57 58 17 10 42 38 30 21 
25 58 3 57 4 43 32 31 7 20 14 13 41 55 62 53 16 39 54 63 59 21 27 33 52 22 45 24 40 6 46 10 61 28 19 5 30 60 15 47 44 2 8 12 23 50 34 11 18 35 38 42 48 1 17 9 29 51 64 37 49 56 36 26 
38 6 62 44 34 55 11 2 12 43 46 49 58 14 29 22 7 30 52 3 5 64 47 60 59 4 25 50 32 27 24 42 28 51 10 18 33 13 23 20 31 56 16 26 8 57 21 9 45 41 17 35 39 53 19 40 15 54 48 63 61 1 37 36 
42 24 54 17 56 10 64 51 63 18 15 27 59 39 19 3 6 29 53 8 23 31 46 25 26 45 55 9 38 16 41 30 21 12 11 57 1 61 40 35 33 49 14 13 7 58 48 47 4 36 32 5 44 52 2 37 34 43 22 50 28 62 20 60 
48 57 35 18 16 36 1 63 17 8 28 21 34 20 50 52 54 55 38 32 40 11 26 45 10 6 29 33 7 56 44 15 27 19 3 37 64 9 4 43 53 39 42 5 25 51 60 22 58 47 59 61 14 23 62 12 24 49 31 2 41 46 13 30 
7 25 15 32 29 22 4 21 35 40 41 26 56 24 2 36 18 13 57 44 9 58 48 14 34 62 31 23 11 53 28 60 39 42 59 30 16 63 6 8 3 17 27 19 45 10 61 37 1 54 49 20 38 43 50 46 55 12 33 47 5 64 51 52 
12 45 60 43 5 58 46 40 13 38 1 9 25 53 48 6 21 16 59 56 42 50 61 10 35 64 51 49 37 36 54 20 44 47 41 17 24 14 62 31 28 34 63 15 4 23 2 52 26 33 11 7 3 22 55 30 27 39 57 29 32 18 8 19 
33 26 9 37 13 41 49 52 47 44 61 4 30 51 31 7 43 19 22 1 28 12 63 39 57 17 3 40 18 46 58 21 45 2 25 15 50 5 60 36 62 55 32 64 54 35 29 20 56 8 10 34 27 24 42 48 11 16 59 23 38 14 6 53 
59 14 8 19 23 50 27 20 42 64 5 45 32 57 55 11 62 34 36 37 33 35 51 2 48 12 47 63 22 43 61 39 58 53 38 56 49 26 54 52 30 46 24 6 1 40 18 41 25 31 16 13 29 60 28 15 9 21 44 4 7 10 3 17 
39 53 30 3 61 28 31 47 33 16 60 54 10 62 23 37 24 41 4 27 15 17 49 20 8 13 14 1 2 52 5 19 32 48 29 7 46 34 55 22 59 38 44 50 11 12 36 43 6 21 18 9 57 63 51 64 26 42 25 40 45 58 35 56 
3 8 10 45 6 18 25 32 40 12 37 19 9 17 28 43 29 59 11 35 53 38 54 24 14 16 21 62 57 33 42 26 13 31 34 58 47 46 50 56 5 61 60 36 52 7 63 49 2 64 51 15 4 30 22 55 41 44 1 48 39 20 27 23 
56 59 16 35 64 57 62 11 2 6 21 18 50 44 60 10 47 7 25 14 27 46 41 8 29 9 1 31 58 39 23 17 4 52 51 42 26 38 49 3 13 32 22 37 33 48 30 28 43 20 40 19 45 12 36 54 61 55 15 24 53 34 5 63 
43 54 58 31 42 63 52 48 45 56 53 15 26 3 61 33 4 21 37 22 20 40 28 49 24 5 50 60 12 34 47 64 30 41 16 1 19 25 8 39 9 51 17 55 27 11 57 14 62 46 7 38 59 44 23 35 36 10 6 13 18 29 32 2 
47 49 24 46 22 5 44 28 57 54 51 36 1 38 41 8 23 48 58 15 2 9 60 61 19 40 37 10 25 55 35 18 62 14 45 6 27 17 64 11 12 4 26 20 34 29 50 21 53 13 39 63 32 3 52 56 30 59 42 33 16 43 7 31 
53 19 34 55 12 61 41 30 11 23 42 47 48 64 5 27 26 17 3 57 1 56 39 13 6 28 59 46 51 15 7 4 36 44 63 10 20 37 43 32 24 35 2 16 62 38 40 54 60 29 31 18 9 21 33 14 52 25 8 22 58 49 45 50 
23 38 14 39 15 27 33 17 24 13 58 22 7 32 20 4 55 51 10 43 44 16 31 62 36 61 52 41 49 30 53 63 2 29 9 54 35 18 5 28 47 19 6 3 56 45 59 42 50 37 1 48 8 26 34 25 60 57 40 46 21 12 11 64 
13 1 51 20 9 21 36 29 55 35 39 46 62 59 14 16 63 32 30 12 50 6 34 52 22 48 2 44 43 3 45 56 23 33 60 24 40 57 61 7 64 31 18 58 15 25 53 8 5 27 42 49 11 17 41 10 28 26 37 19 54 4 38 47 
50 37 40 2 26 60 7 4 34 29 31 52 49 25 63 30 19 18 42 33 36 45 5 64 13 38 8 32 20 54 11 27 53 55 15 22 12 21 48 59 23 10 41 43 46 1 39 44 24 57 6 47 58 28 61 16 56 14 35 9 3 51 17 62 

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.