How to traverse through all possible paths to a solution and pick the optimum path

Question

I am not good at programmatically implementing a heuristic search algorithm / Dijkstra's algorithm/ A* search algorithm mentioned. However, while solving a problem mentioned in one of my post (Matrix manipulation: logic not fetching correct answer for higher order NXN matrix data), I found a flaw in my approach to solve the problem. The problem statement is as below.

Problem Statement

There is a NxN matrix,divided into N * N cells. Each cell has a predefined value. Which would be given as an input. Iteration has to happen K number of times which is also given in the test input. We have to make sure that we pick the optimum/min value of rows/columns at each iteration. Final output is the cumulative sum of optimum value saved at the end of each iteration.

Steps 1. Sum up the individual row and column and find the min sum of rows and columns, (it could be a row or a column, just need the minimum row or a column)

Step 2. Store the sum found above separately

Step 3. Increment elements of the min. sum row or column. by 1

Repeat steps 1,2,3 from 1 to Kth value

add the sum at each iteration(specified in step2)

output is the sum obtained on on the Kth iteration.

Sample data

2, 4 //input data N,K
[1, 3] //matrix' first row
[2, 4] //matrix' second row

Output data 22

My Code

void matrixManipulation() throws IOException {
            int N = Reader.nextInt();
            int[][] matrix = new int[N][N];
            int K = Reader.nextInt();
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    matrix[i][j] = Reader.nextInt();
                }
            }


            int[] row = new int[N];
            int[] row_clone = new int[N];

            int[] col = new int[N];
            int[] col_clone = new int[N];

            int test =0;

            for (int kk = 0; kk < K; kk++) {

                row = calculateSum.calculateRowSum(matrix, N);
                row_clone = row.clone();

                col= calculateSum.calculateColSum(matrix, N);
                col_clone = col.clone();

               Arrays.sort(col);
               Arrays.sort(row);
               int pick = 0;
                boolean rowflag = false;
                int rowNumber = 0;
                int colNumber = 0;
                if (row[0] < col[0]) {
                    pick = row[0];// value
                    rowflag = true;
                    for (int i = 0; i < N; i++) {
                        if (pick == row_clone[i])
                            rowNumber = i;
                    }
                } else if (row[0] > col[0]) {
                    pick = col[0];// value
                    rowflag = false;
                    for (int i = 0; i < N; i++) {
                        if (pick == col_clone[i])
                            colNumber = i;
                    }
                } 

> else if(row[0] == col[0]){
>                         pick = col[0];
>                         rowflag = false;
>                         for (int i = 0; i < N; i++) {
>                             if (pick == col_clone[i])
>                                 colNumber = i;
>                         }

                }
                test= test + pick;

                if (rowflag) {
                    matrix = rowUpdate(matrix, N, rowNumber);
                } else {
                    matrix = columnUpdate(matrix, N, colNumber);

                }
                System.out.println(test);

            }

        }

Issue with my Code

This solution was working for some lower order matrix and simple scenarios, however, when I tried test cases that involved 100x100 sized matrix many test cases failed. Initially, I thought it was some memory issue/stack overflow when the array size increases but now I have worked out that it is a flaw in the code that I am not able to anticipate the correct path that would eventually guides me to the optimum solution I'd like to achieve.

The flaw that I found in my code is, say, in one scenario when the optimum value from both rows and columns is equal. I am free to choose row or column, however, the problem here is, say, if I go with row first it may update the values of row to some non-optimum value, I believe only I'd know all the optimum paths beforehand would help me get the correct answer.

Any help in this regard would be highly appreciated.

This question has a reference to question asked here. Matrix manipulation: logic not fetching correct answer for higher order NXN matrix data

Only when Higher order matrix is used I get the below difference in output when I apply the above approach. Edit:

 Output   Expected Output 
 1 5499   1 5499 
 2 30050  2 30050 
 3 50778  3 50708 
 4 36589  4 36509 
 5 19259  5 19259 
 6 21367  6 21367 

Case 3 (my output was 50778 and the expected was 50708) Case 2 sample data below (my output was 30066 and the expected was 30050)

100 57
5 6 5 10 6 3 9 2 4 7 6 6 8 6 5 6 1 6 9 1 6 8 3 7 3 2 4 8 7 8 3 6 3 9 4 2 1 8 5 5 1 5 8 6 6 10 5 3 4 7 3 3 10 10 3 1 7 3 8 4 4 9 3 7 6 7 9 3 2 2 2 4 8 9 8 1 10 6 6 10 7 5 5 7 9 8 3 2 3 3 9 6 3 7 5 5 10 3 3 3
7 6 2 3 8 8 3 10 1 8 4 7 5 2 9 5 3 5 4 6 4 10 1 6 1 5 1 6 4 9 6 4 10 1 2 4 8 10 5 9 1 9 1 9 3 10 9 9 6 5 6 5 9 4 1 4 9 8 6 9 1 3 1 4 9 2 3 4 1 6 4 1 1 8 2 5 10 1 1 10 7 8 7 3 9 3 10 3 10 5 8 3 7 9 10 5 7 3 2 3
4 5 4 6 9 6 6 3 6 3 2 4 9 3 3 6 10 6 3 6 7 7 9 8 9 3 6 6 3 4 9 6 2 5 9 9 9 1 5 1 7 4 9 7 10 3 1 8 1 9 9 3 1 4 6 1 8 10 3 1 10 5 9 4 3 6 8 8 1 3 5 9 1 9 9 4 3 5 1 7 1 1 9 2 1 9 7 4 7 8 7 3 3 9 6 9 10 7 10 5
2 9 4 3 4 5 6 8 5 5 8 2 3 2 1 2 5 1 10 6 5 6 6 8 4 8 3 6 6 3 3 1 6 3 3 7 6 4 2 7 1 5 9 8 9 5 8 8 10 8 8 8 10 7 3 1 8 6 7 2 2 5 9 8 10 10 10 3 2 6 8 9 6 10 6 10 5 10 9 7 6 4 5 6 4 8 7 10 3 5 9 1 5 7 5 5 9 9 3 10
10 2 1 8 2 2 7 3 6 8 10 8 4 1 3 9 3 8 4 8 7 5 4 1 5 3 2 1 6 3 8 8 8 9 10 4 8 10 9 1 4 1 5 5 9 2 1 2 4 1 3 7 5 8 7 2 5 1 2 2 5 4 4 2 3 2 9 6 5 3 6 5 2 6 9 3 4 7 9 4 1 8 5 10 3 1 3 6 8 8 6 3 1 4 8 6 2 6 6 1
2 7 3 9 10 8 5 8 1 1 7 6 2 3 4 1 2 3 9 2 2 1 2 2 7 10 8 4 4 9 9 6 3 9 9 4 8 2 5 3 1 2 9 1 2 3 1 9 4 7 7 1 10 8 9 9 6 7 5 2 8 3 1 1 7 4 8 7 10 9 10 7 9 4 10 8 4 10 1 1 10 2 2 9 8 8 1 3 4 2 10 2 2 3 3 7 4 6 6 1
4 1 5 9 2 7 3 9 5 8 8 5 1 7 1 10 1 3 1 4 2 3 7 1 4 3 5 5 8 5 6 10 2 10 6 2 1 10 9 2 3 8 2 6 9 3 2 1 4 9 6 6 7 1 6 1 8 6 1 4 10 10 2 3 1 9 9 2 9 1 5 8 8 1 10 10 8 1 1 7 4 7 7 2 9 8 1 5 10 10 3 5 6 10 4 2 10 6 10 9
5 3 3 7 7 4 10 4 6 4 3 4 5 6 4 1 4 3 3 2 1 5 1 1 10 3 3 8 6 9 9 6 10 3 3 1 6 9 2 8 7 1 7 10 8 4 7 5 8 4 9 10 9 8 4 4 3 2 4 3 10 10 5 7 8 1 9 3 8 1 4 9 3 5 9 1 3 4 8 10 5 2 4 5 2 7 5 5 1 2 9 6 1 2 3 10 4 5 9 9
10 10 2 7 10 9 2 1 3 4 6 10 5 1 10 7 3 5 7 9 8 9 4 7 6 4 8 3 9 10 9 1 5 5 7 7 10 8 6 3 9 4 2 6 6 7 5 2 1 4 6 9 3 5 9 5 8 6 8 2 1 3 6 2 2 4 5 1 1 10 2 1 6 2 10 8 3 3 6 1 2 1 4 10 4 6 6 9 7 6 7 8 2 7 9 3 9 10 1 5
9 3 4 4 8 4 9 1 1 9 7 4 8 1 5 3 2 3 5 4 7 2 6 6 9 5 8 5 2 4 1 3 2 5 7 6 2 8 3 6 10 10 3 3 8 2 4 10 3 4 10 8 2 3 5 2 10 9 3 4 3 4 6 7 6 8 7 3 7 3 1 4 2 4 5 2 5 5 10 4 1 1 7 1 9 6 5 5 7 2 8 2 6 2 10 10 4 3 1 10
6 2 4 7 3 7 4 4 8 1 6 1 9 5 3 2 6 1 7 1 4 8 4 4 1 1 4 8 1 4 5 2 4 2 6 7 3 2 9 5 5 3 3 1 7 10 4 9 10 4 2 4 6 3 4 1 1 7 3 1 2 10 7 9 3 2 8 7 1 1 5 8 7 9 7 8 9 5 1 6 7 6 6 2 10 4 4 8 10 7 4 4 10 5 6 1 9 4 5 4
5 1 2 3 4 6 10 8 1 3 2 3 7 10 4 2 5 10 5 10 8 4 8 5 2 3 2 7 10 6 8 2 1 6 9 1 3 6 8 9 8 7 3 7 2 5 2 7 3 2 5 3 1 5 1 5 4 2 4 4 6 7 5 1 9 6 1 6 5 6 6 7 4 3 1 9 8 6 2 1 8 5 7 7 7 9 1 1 10 6 4 4 1 8 3 10 6 7 1 5
4 6 7 3 8 1 1 7 8 10 8 4 9 7 7 3 4 2 10 6 5 6 2 9 8 2 9 7 10 6 3 3 1 1 3 3 2 7 4 8 4 5 3 7 9 1 5 7 2 4 9 5 4 4 1 10 3 7 6 9 3 8 10 5 5 5 1 4 2 10 4 9 5 5 1 7 6 3 3 8 6 6 10 6 5 10 9 4 10 10 10 6 6 7 8 3 4 1 10 9
8 2 8 2 3 2 4 1 8 3 5 9 8 6 6 9 1 4 2 1 7 3 5 9 1 8 2 5 1 1 5 7 5 9 9 1 10 3 6 1 2 10 9 3 1 10 2 4 10 6 8 6 9 10 7 5 10 10 9 6 8 2 5 9 3 2 4 9 8 8 9 3 5 10 8 1 3 3 2 7 2 1 5 10 10 3 10 7 4 8 9 4 6 2 5 4 8 9 10 4
9 7 3 9 9 9 2 3 6 6 2 1 9 10 6 4 2 10 8 7 8 9 3 10 9 5 6 2 5 1 10 1 4 4 10 6 6 8 4 6 8 9 3 1 4 4 10 1 3 7 6 7 5 6 7 9 4 6 6 6 8 2 8 9 7 4 6 9 7 10 8 6 9 3 6 6 5 3 3 8 10 3 9 1 3 8 5 2 8 10 8 7 5 6 10 7 6 5 9 9
7 9 6 1 8 4 8 8 9 2 10 7 1 4 6 4 5 5 5 10 3 10 8 3 7 1 4 9 10 6 10 3 9 2 8 3 8 4 6 4 8 3 4 4 10 1 1 5 10 2 8 8 4 2 4 6 5 5 9 1 5 10 1 3 5 5 10 9 7 1 1 5 4 6 4 3 10 5 3 2 3 2 10 1 3 7 10 6 8 2 8 8 8 7 6 10 9 4 5 6
2 4 9 1 1 7 2 3 6 10 5 3 9 4 9 1 1 2 8 7 3 2 8 6 4 2 10 7 7 5 1 5 8 9 7 5 8 2 10 8 8 8 9 10 7 1 2 2 5 4 9 10 1 4 4 9 8 6 8 7 2 3 4 1 8 8 1 3 4 7 4 10 2 10 7 7 6 8 7 9 4 6 10 8 2 6 2 7 5 5 4 7 9 10 2 7 3 3 3 4
10 7 9 5 7 10 3 7 6 10 7 4 3 3 1 1 1 7 1 2 8 9 5 2 7 6 6 5 5 5 10 3 4 9 6 9 2 3 3 5 1 9 2 2 5 9 5 7 3 6 4 7 5 1 10 2 3 5 6 6 5 4 1 4 9 3 3 7 8 2 1 7 1 6 1 10 4 6 1 6 10 6 7 2 9 7 4 2 8 2 2 7 6 3 3 3 5 2 1 10
3 9 4 1 8 1 1 3 5 6 7 3 4 8 1 7 6 2 2 3 7 1 7 1 7 8 10 8 7 6 10 7 9 10 9 9 9 2 10 3 8 5 10 7 9 10 7 8 9 4 3 5 7 10 10 6 4 10 1 9 8 1 6 5 9 8 10 4 9 10 7 9 8 8 1 7 4 7 9 3 4 5 7 1 3 6 5 1 9 3 3 10 4 2 5 10 7 9 5 2
1 6 8 8 4 7 6 5 6 6 3 6 10 4 6 5 7 9 1 1 2 4 3 6 10 1 10 8 7 1 1 7 9 1 4 7 7 4 6 6 6 7 10 3 5 5 8 3 4 10 7 1 1 1 6 4 5 1 9 6 7 2 8 3 8 3 1 2 7 7 4 6 8 9 7 4 7 3 6 1 5 4 10 5 6 3 4 10 8 6 8 8 5 3 10 1 4 1 8 5
4 3 2 2 10 4 7 10 6 8 9 2 2 7 7 10 3 6 9 6 3 1 5 10 8 4 10 2 9 3 1 5 9 4 7 8 5 1 1 1 5 2 9 4 7 4 4 6 6 1 8 10 6 5 10 9 9 10 5 5 4 3 9 2 9 3 3 4 4 8 2 1 9 8 10 1 2 7 4 4 9 2 9 2 4 9 8 6 6 8 7 3 10 6 7 1 2 7 5 6
4 3 10 5 4 6 6 1 3 7 5 5 2 4 9 6 3 7 4 7 1 10 7 10 5 6 9 2 3 6 6 3 6 8 5 7 1 5 5 6 2 7 8 4 5 4 2 7 1 5 6 4 6 7 8 3 3 7 8 10 1 4 9 10 2 1 9 5 8 8 8 4 1 9 4 4 10 4 4 4 3 10 9 7 9 4 3 7 10 7 7 9 4 10 6 5 6 6 9 7
3 8 7 1 7 2 9 5 5 6 2 10 10 8 3 10 3 1 4 6 1 8 6 10 9 7 5 3 9 10 3 5 5 1 5 10 4 4 6 3 7 8 9 4 1 10 10 5 6 10 10 1 9 9 1 9 9 3 9 10 9 3 5 1 9 9 4 8 4 3 4 6 10 10 7 6 8 9 2 9 6 7 5 3 8 7 4 7 8 2 5 4 6 8 7 1 8 9 2 6
8 7 7 2 6 7 1 2 4 10 3 1 2 5 10 8 6 9 9 6 4 10 5 4 3 2 10 9 2 9 5 5 4 5 9 8 10 7 8 3 8 4 7 1 10 2 2 7 1 7 8 9 7 9 2 6 3 5 5 3 6 1 2 10 4 2 5 5 4 8 4 1 4 3 10 1 1 8 8 4 5 2 3 4 6 3 7 9 4 5 7 8 4 5 3 5 10 7 8 8
1 6 9 9 8 6 4 9 8 2 2 1 10 6 7 4 8 8 2 2 1 4 3 3 5 7 6 6 5 9 9 10 1 5 7 3 6 4 1 9 10 4 10 8 8 5 7 10 7 8 7 10 6 8 6 6 10 3 9 9 5 3 3 9 5 1 5 8 5 5 7 1 2 7 5 9 9 6 9 3 10 1 1 2 5 9 7 5 3 6 8 4 1 3 3 10 1 10 6 5
8 7 10 8 1 1 5 10 2 9 6 4 8 7 8 3 6 3 2 5 8 2 2 6 6 9 9 4 8 1 8 9 2 4 3 4 2 8 6 1 5 10 4 10 3 3 5 2 1 9 3 5 3 6 7 10 1 5 10 3 3 6 4 9 1 6 4 4 8 7 1 7 9 9 6 3 4 6 5 4 4 4 1 3 9 5 2 2 9 8 7 6 5 10 3 6 4 8 7 8
1 1 9 9 9 9 8 4 7 1 4 5 9 9 9 1 5 7 3 4 6 6 7 4 5 4 9 2 7 10 7 9 8 2 7 8 9 10 8 10 5 8 5 9 10 3 2 5 5 9 4 8 3 8 3 10 10 9 7 5 6 10 10 10 4 3 1 5 9 1 9 3 6 3 1 4 7 10 10 10 8 7 10 6 1 2 6 7 2 10 4 2 5 3 9 6 9 6 5 2
10 2 9 4 9 4 9 1 6 1 5 3 5 10 6 7 1 4 1 7 9 1 1 4 7 7 8 10 7 3 5 3 5 5 4 8 7 1 7 4 8 7 10 3 7 3 2 6 8 9 4 9 2 6 6 4 3 7 6 5 3 2 1 4 6 1 6 3 6 4 1 4 4 5 8 1 7 2 3 6 10 1 4 3 4 3 5 1 6 1 3 9 5 8 2 3 3 3 8 2
8 3 5 7 6 6 6 4 8 9 8 10 7 4 5 10 4 9 10 2 2 5 6 4 10 6 6 2 4 8 9 2 10 3 5 5 7 1 7 6 8 4 2 3 5 5 3 5 7 2 4 3 8 5 9 1 4 8 5 5 7 4 2 4 10 1 2 7 10 3 7 10 6 9 8 3 2 7 2 2 5 3 5 8 10 7 3 5 3 9 3 10 9 1 2 8 4 2 1 10
7 3 5 8 8 6 5 5 9 8 4 2 2 8 2 6 7 8 8 6 6 10 8 6 3 4 5 1 3 10 5 8 2 4 6 5 7 9 7 10 9 4 1 3 2 1 3 10 9 3 8 7 9 1 2 1 10 8 3 1 3 7 2 10 10 8 9 4 4 5 1 2 6 6 9 2 8 7 5 7 9 7 6 5 7 1 4 6 10 4 7 3 8 5 10 8 4 8 8 7
1 2 1 2 6 8 4 2 1 6 7 5 7 9 7 8 9 9 1 10 6 9 2 4 10 1 9 8 7 3 7 3 3 6 4 4 5 6 10 4 9 6 9 9 4 1 3 8 4 2 3 5 4 7 7 1 10 2 1 4 5 2 4 10 4 10 1 6 2 6 3 9 8 4 4 8 3 1 7 10 9 5 5 2 1 6 3 4 4 8 7 9 9 6 6 10 8 7 8 10
4 1 9 4 5 6 6 10 9 6 7 5 8 1 3 9 5 10 6 7 7 10 8 8 9 4 3 4 3 6 1 9 5 10 5 8 4 10 7 4 2 6 6 10 6 4 4 3 5 8 6 4 2 4 8 3 7 4 2 9 1 1 6 2 6 1 5 6 7 10 6 2 6 6 3 4 10 2 1 1 8 5 6 7 5 3 8 10 2 10 6 2 6 9 1 8 5 7 1 1
3 3 2 1 7 2 4 1 3 2 2 8 4 7 1 2 2 10 4 9 8 9 10 8 2 9 9 6 10 2 5 2 8 8 10 7 6 10 1 7 3 8 4 7 9 7 1 7 2 4 6 5 4 1 2 10 8 4 9 7 10 5 8 2 8 7 6 2 9 8 5 6 3 5 10 10 9 6 6 3 1 7 9 10 10 1 3 8 3 3 9 1 2 3 8 6 5 7 10 8
9 8 6 2 10 4 4 4 10 9 2 5 1 1 9 7 3 8 9 8 6 10 5 9 5 4 1 6 2 9 9 4 9 6 10 5 6 3 3 2 2 2 4 4 2 5 5 6 10 7 10 5 1 5 10 9 9 2 6 10 2 5 7 5 8 3 4 3 4 8 4 5 7 7 10 4 7 7 2 6 8 9 4 5 6 9 3 9 3 8 1 10 4 3 5 7 4 5 1 10
3 1 2 9 7 5 1 1 8 4 7 6 7 10 1 6 7 3 4 2 7 10 8 4 7 8 10 5 1 9 4 3 10 9 9 9 1 5 7 8 10 6 5 2 10 9 4 2 6 4 5 9 10 8 10 2 1 4 5 10 7 2 3 9 9 9 2 9 4 3 2 10 6 1 9 8 5 1 5 2 7 1 3 1 9 4 7 1 4 6 8 8 10 9 1 8 7 1 5 2
7 7 7 10 2 10 3 7 1 4 7 1 7 6 6 6 10 4 5 2 1 9 3 1 10 2 1 7 7 1 10 3 3 1 1 2 3 8 2 8 7 6 3 6 6 10 5 8 6 1 10 7 7 1 10 8 4 4 1 7 3 2 10 8 6 2 1 4 4 5 6 7 4 9 1 5 5 1 1 9 5 5 8 1 3 3 9 8 2 10 8 9 2 9 6 8 3 3 3 3
2 8 4 9 5 7 10 5 9 10 2 7 8 1 2 4 10 2 4 1 8 4 3 2 9 7 8 7 10 8 1 5 9 4 5 10 5 10 2 10 10 2 2 2 1 3 1 3 4 1 6 9 7 4 8 4 10 9 8 3 2 8 1 10 4 8 1 8 6 1 5 8 4 2 2 7 7 2 2 5 4 1 7 1 8 7 10 1 10 1 10 9 9 10 1 7 6 1 6 7
6 2 1 6 5 7 2 9 6 10 6 4 3 7 7 9 9 8 7 1 7 7 8 2 5 7 1 10 7 6 2 1 5 10 10 7 2 8 9 10 9 9 1 1 3 10 2 6 3 8 4 2 9 6 7 5 5 2 7 4 7 9 5 1 7 1 5 3 1 4 5 10 7 6 7 8 6 5 8 2 1 10 8 2 9 4 3 10 10 8 5 8 6 3 2 1 4 4 9 3
3 10 6 5 3 9 10 8 5 1 3 4 9 4 8 10 2 7 6 8 6 1 1 3 3 8 5 7 10 4 7 5 2 2 4 10 5 4 9 6 4 5 9 6 10 7 6 7 6 7 1 3 8 5 1 1 4 2 4 10 1 4 5 10 5 9 2 6 7 2 3 1 3 1 1 9 2 5 1 10 10 2 4 10 3 6 2 6 4 5 9 8 7 9 8 9 8 2 3 9
7 10 4 1 3 6 10 7 1 2 6 8 9 9 4 2 3 6 2 1 4 6 9 1 6 7 6 10 4 6 6 4 7 8 6 7 5 8 6 10 10 7 5 7 10 10 7 1 10 10 4 2 10 9 2 5 3 9 8 2 2 7 9 4 8 4 10 3 8 9 9 1 8 4 9 4 3 7 7 9 1 8 7 8 3 6 6 1 2 1 6 5 9 5 3 1 6 2 6 10
10 5 5 3 9 10 6 5 3 6 5 4 7 9 6 10 7 5 5 2 10 9 6 9 7 9 9 3 5 5 9 3 4 4 7 3 9 8 1 6 3 2 8 5 6 6 8 3 6 8 7 7 4 2 4 6 10 4 6 8 5 4 7 5 1 2 9 9 6 5 10 9 4 10 4 8 6 4 9 2 1 5 1 7 3 3 5 1 3 7 8 1 2 10 9 2 4 5 3 2
9 5 1 3 7 10 10 9 9 3 8 3 8 5 4 5 3 3 5 7 9 7 5 8 3 6 5 2 6 3 8 6 8 10 8 2 8 3 2 7 1 8 9 3 4 3 3 4 1 5 2 10 4 7 7 7 3 5 8 3 1 2 8 8 7 5 9 4 6 9 5 3 7 8 1 1 1 5 2 1 10 7 3 8 8 4 3 6 3 6 4 1 8 3 7 4 8 10 10 3
1 10 10 7 3 3 10 3 8 2 5 2 8 4 9 3 8 9 10 5 7 1 6 10 9 2 2 2 10 7 8 2 6 1 8 4 7 3 6 3 7 6 8 5 4 5 5 7 8 9 5 9 8 4 6 9 5 9 8 5 7 7 3 10 1 9 10 3 4 9 10 9 6 4 9 6 6 5 7 4 7 4 6 10 3 9 4 5 7 3 2 9 3 1 1 3 1 10 7 10
6 10 4 9 6 8 3 9 1 6 7 9 1 7 6 5 1 1 3 2 10 7 9 5 8 8 8 8 9 3 3 6 4 8 2 4 3 9 5 1 8 5 9 9 8 2 5 10 10 6 4 4 6 9 9 3 1 5 8 1 7 7 6 4 10 2 3 5 8 8 8 2 10 1 5 2 4 2 2 9 4 7 9 4 3 1 3 9 7 6 6 7 8 2 2 5 5 6 4 4
5 10 2 9 9 7 7 6 3 4 2 6 7 3 6 3 4 3 1 4 9 5 4 6 9 8 8 5 4 4 1 9 6 10 8 8 2 2 8 7 5 3 2 6 3 6 2 5 2 9 5 8 2 9 10 5 6 1 2 5 8 6 2 10 8 2 9 5 10 3 10 6 3 3 1 10 8 9 5 2 1 9 2 3 6 5 5 8 10 9 2 10 7 2 8 5 7 4 7 9
8 9 4 1 6 1 3 9 10 8 7 1 5 8 9 2 7 6 3 6 3 5 8 7 6 1 3 6 7 2 6 8 7 6 8 8 4 4 8 9 5 3 9 1 5 4 6 5 9 1 8 2 7 1 9 6 5 7 9 7 1 1 6 3 1 6 2 6 10 2 4 7 2 3 9 8 7 9 2 6 7 6 8 7 9 4 4 8 8 4 4 2 10 7 8 5 1 7 1 1
5 3 4 7 4 4 4 9 10 4 8 5 2 6 4 5 2 9 5 10 5 8 10 2 7 7 2 2 4 10 2 8 6 4 7 1 2 3 2 1 6 6 10 4 3 9 5 1 4 3 6 7 1 10 10 10 3 4 9 4 2 4 2 8 10 5 8 7 5 2 9 2 2 1 8 4 8 2 9 8 5 5 6 5 2 7 4 2 2 6 9 6 5 4 3 5 6 4 6 8
2 7 5 10 10 8 10 6 4 10 10 2 8 9 8 5 1 4 2 2 4 10 4 8 7 8 10 8 7 4 5 7 10 3 5 5 6 4 10 4 10 4 6 7 3 6 6 7 3 10 2 3 6 1 5 1 2 2 6 4 4 1 7 6 6 7 8 1 8 3 9 4 7 10 7 1 6 7 5 6 4 7 3 3 10 3 4 7 2 1 6 2 5 9 7 7 3 7 1 8
5 2 10 8 2 4 1 5 6 2 7 6 2 2 10 2 9 8 1 5 2 5 8 1 9 10 3 3 2 3 2 5 4 6 4 1 5 6 5 5 8 9 9 8 3 2 5 3 10 9 5 3 4 9 8 3 10 5 5 6 2 1 1 8 9 1 6 9 4 10 1 1 10 8 9 8 2 5 2 4 10 6 3 10 10 6 6 7 2 7 7 9 10 7 7 7 10 9 10 10
8 7 4 10 6 3 7 3 7 6 4 9 10 4 7 4 8 6 2 9 5 4 6 2 3 5 1 6 10 2 5 7 7 8 2 1 3 3 9 6 3 2 10 3 5 4 7 1 2 5 9 5 9 7 10 8 10 6 9 8 3 6 8 10 2 9 1 4 5 7 1 10 7 2 1 3 6 9 2 1 6 1 9 8 9 3 4 3 2 1 2 6 9 3 1 10 3 7 9 3
1 9 8 10 4 5 1 9 6 4 1 5 7 8 4 1 7 5 8 1 5 7 6 2 2 5 3 2 2 8 4 9 1 9 2 8 6 3 6 8 2 2 2 8 8 6 9 7 5 4 4 10 5 8 7 2 7 10 2 4 7 10 4 5 3 1 8 9 5 9 4 10 7 6 3 5 7 3 8 9 5 10 1 5 2 4 6 5 7 10 8 1 5 10 10 5 3 7 3 3
8 9 6 6 9 10 5 8 1 1 2 9 9 9 2 6 1 3 2 9 4 4 1 9 5 2 8 1 5 10 3 8 3 7 10 5 4 10 8 5 10 4 4 9 6 7 1 10 10 2 6 4 5 1 1 10 10 8 2 5 1 1 3 7 5 6 2 8 4 9 8 3 10 6 2 5 3 3 8 10 2 7 9 5 9 7 9 2 1 3 10 7 1 9 7 10 1 1 2 6
6 10 1 5 10 1 4 5 10 5 4 2 2 8 4 2 4 7 7 9 1 5 7 5 2 1 3 6 6 5 5 5 10 7 7 6 10 9 10 3 9 3 2 10 8 9 9 3 5 9 8 4 3 9 3 1 4 1 9 4 3 3 3 2 1 3 1 4 1 5 3 4 5 5 10 2 7 10 9 2 5 6 1 9 4 6 4 10 1 9 4 8 6 1 10 6 7 4 5 5
1 6 6 9 5 3 3 6 5 9 1 2 1 4 9 4 7 9 2 7 10 9 7 6 4 2 5 3 9 6 7 2 5 3 1 3 5 4 5 3 3 7 10 7 3 7 7 5 7 7 6 3 3 9 1 10 7 3 10 7 4 4 3 6 8 1 8 4 7 9 8 10 3 2 6 2 6 8 5 1 7 2 8 2 2 5 5 5 7 6 8 3 10 1 8 9 7 5 8 3
8 2 5 2 9 6 8 2 10 8 2 10 3 9 9 7 6 1 1 3 7 3 2 10 5 1 5 7 4 1 3 6 9 6 9 3 8 3 6 10 2 4 9 9 10 7 5 8 7 2 1 5 9 2 1 2 2 8 5 10 8 6 8 7 7 9 6 6 1 6 3 5 9 8 1 1 5 10 8 9 9 4 2 5 4 7 7 3 3 8 6 3 4 9 10 8 4 7 8 10
10 10 3 5 7 4 6 7 10 2 6 3 8 9 8 3 10 5 9 2 6 9 4 3 6 3 10 1 7 2 9 4 7 4 8 2 7 8 4 8 8 2 4 5 4 10 7 9 1 2 3 9 2 4 6 2 10 7 3 9 6 4 3 6 6 4 6 9 8 2 2 2 7 2 6 6 6 4 9 8 2 1 7 5 5 10 10 9 10 6 10 3 7 7 8 3 6 4 6 8
8 7 3 4 1 6 9 7 6 10 10 10 10 2 9 1 10 10 9 9 2 6 9 4 5 6 3 6 1 5 1 3 2 5 2 6 9 4 5 4 6 9 10 5 5 2 9 1 8 10 8 6 7 6 7 10 1 10 9 5 9 6 8 7 10 7 10 6 10 1 1 4 3 4 2 5 2 10 10 7 9 7 7 3 6 8 4 1 1 5 3 10 7 3 8 5 3 5 5 1
3 2 3 8 5 8 2 10 6 9 8 9 7 7 8 4 10 2 5 4 4 5 8 4 8 5 1 6 3 9 8 6 6 1 1 1 8 9 5 7 8 8 8 3 9 5 10 7 5 2 7 4 4 4 8 8 10 9 6 1 8 5 10 9 1 6 4 4 2 3 6 9 5 4 8 6 4 1 5 2 7 5 8 2 1 1 10 1 5 7 9 9 5 1 5 8 10 10 5 1
10 6 8 10 9 4 8 3 4 10 8 6 4 6 7 6 10 7 10 4 7 6 7 9 3 1 9 2 5 4 2 5 7 1 3 5 5 2 1 7 8 8 1 7 2 9 5 6 3 1 2 10 1 1 7 3 5 8 9 6 7 9 9 8 2 7 3 10 1 8 5 3 7 3 4 6 4 1 2 8 3 9 2 9 1 8 7 6 1 6 4 2 7 7 9 5 10 1 2 2
1 1 4 4 8 1 1 8 5 8 5 4 4 10 1 1 4 10 10 5 8 6 3 8 8 4 3 9 1 9 2 6 9 6 4 1 1 1 5 10 5 3 1 10 4 8 7 3 9 2 1 3 4 10 5 6 4 9 5 2 1 4 4 6 8 6 10 10 6 8 4 4 3 1 4 2 5 9 1 2 4 4 2 6 10 1 7 4 9 4 8 3 5 4 1 1 5 4 10 1
7 1 5 2 10 5 8 2 1 9 7 4 6 1 6 9 1 8 7 3 9 3 5 5 3 2 7 8 5 7 3 2 1 9 3 10 8 9 1 3 1 1 8 1 9 1 8 2 3 1 5 7 8 6 8 6 10 4 8 3 2 3 8 3 7 9 1 6 7 2 7 3 1 10 8 3 7 6 6 8 3 10 5 4 8 1 2 1 2 8 6 9 3 10 7 10 1 4 9 3
8 9 10 1 7 5 9 10 5 4 6 4 7 1 1 5 1 8 6 7 10 10 4 9 1 5 3 10 2 5 9 1 6 1 4 7 2 4 1 9 1 9 5 9 6 10 3 6 2 4 9 1 6 5 10 8 5 10 7 10 5 8 1 9 3 10 5 6 1 8 6 1 7 8 10 7 1 8 8 2 5 4 9 1 10 6 4 6 6 3 4 7 10 6 7 9 3 7 3 1
4 4 8 7 10 5 2 5 7 1 10 7 10 7 9 3 3 10 2 7 5 4 4 2 1 8 9 4 5 9 6 10 7 5 5 6 2 2 1 8 2 3 4 2 10 6 3 2 3 3 5 7 7 4 4 4 10 2 10 9 4 5 8 8 8 8 3 1 3 9 10 10 7 6 7 10 4 10 1 9 8 9 8 2 10 6 5 4 8 5 10 10 8 3 1 9 10 10 3 2
4 8 6 5 4 1 5 4 5 8 9 10 7 10 2 5 5 7 9 4 6 5 8 3 2 8 4 2 5 4 2 2 9 4 6 8 9 3 6 10 8 6 3 7 9 5 1 6 5 4 7 5 5 8 3 1 3 1 1 9 5 3 1 3 8 10 10 4 5 5 4 6 1 2 6 7 8 9 10 2 6 2 9 7 1 4 10 8 7 6 6 4 1 10 8 6 8 2 7 8
7 10 5 9 10 5 6 4 6 9 1 10 4 7 6 1 5 6 3 6 1 7 7 5 6 3 8 6 5 5 2 6 4 6 4 7 1 5 1 10 8 4 4 4 9 5 4 1 6 7 7 3 8 1 5 10 10 2 10 2 10 10 10 6 8 3 3 8 7 7 4 10 1 2 5 9 5 1 7 10 4 1 9 10 7 2 7 3 2 9 2 7 1 3 1 9 2 4 7 6
5 8 9 8 2 9 2 10 4 2 5 5 1 9 7 2 7 3 1 5 9 10 6 10 5 10 2 8 7 1 7 2 1 4 1 9 10 3 4 5 1 2 6 4 9 3 5 3 7 4 10 5 9 3 3 7 8 2 3 3 6 3 9 4 4 7 7 1 4 4 10 2 3 6 5 4 7 9 1 4 7 7 8 5 7 7 10 10 7 10 6 8 9 6 5 5 2 6 5 4
3 6 4 10 5 4 9 8 10 6 7 5 9 6 10 3 5 5 6 7 6 10 1 9 5 3 5 3 9 2 10 7 2 8 1 5 9 9 5 10 10 7 5 9 5 6 9 9 6 2 9 5 7 8 10 3 6 7 5 2 8 5 1 9 6 8 2 6 7 1 7 9 7 6 7 5 5 5 2 8 9 9 5 3 5 1 5 10 8 5 4 5 2 10 3 8 8 4 4 5
3 4 9 6 3 8 9 1 3 4 9 10 8 1 4 1 5 6 10 8 9 2 4 1 9 4 1 6 8 8 9 10 2 5 2 9 4 5 2 7 1 1 6 10 6 8 10 6 4 10 10 10 6 3 6 4 4 8 6 2 7 1 9 2 6 7 8 3 10 6 4 9 5 6 3 6 1 5 9 7 4 9 6 1 8 8 2 5 1 5 5 10 7 5 5 1 9 3 1 10
7 6 8 10 3 6 5 10 3 2 7 5 8 9 10 6 7 2 9 7 6 2 7 1 6 5 1 8 7 8 2 10 5 5 9 8 1 7 5 2 8 7 9 6 5 4 5 6 10 2 4 9 10 4 9 6 7 2 2 5 1 5 9 3 9 4 5 4 9 5 3 6 9 1 3 5 1 1 9 1 4 7 6 8 5 10 5 5 1 1 2 10 2 4 2 4 10 1 9 4
6 4 8 5 6 6 1 6 7 2 3 4 4 2 8 6 5 10 4 10 2 2 10 3 6 5 10 3 10 7 3 5 10 4 4 3 10 7 6 4 4 3 6 8 5 10 3 2 1 1 7 6 1 6 10 5 2 9 7 3 2 7 1 10 6 2 10 10 3 10 5 3 7 1 8 9 7 5 1 4 5 3 6 4 1 6 10 10 10 10 9 3 6 6 4 4 10 1 4 5
6 8 8 1 8 4 6 1 4 5 3 7 10 5 3 4 10 10 10 5 3 7 5 10 3 4 1 4 5 6 5 4 6 7 7 6 6 2 8 10 1 7 9 1 1 4 10 4 7 1 5 10 1 3 5 1 5 5 2 3 5 1 2 8 1 8 3 8 5 8 5 9 5 10 4 1 7 10 5 7 5 9 5 5 1 8 7 5 6 2 1 6 4 2 7 7 1 8 1 4
6 3 3 3 1 10 10 5 7 1 2 2 3 3 6 9 4 4 2 4 7 4 6 9 8 7 5 2 4 5 9 1 9 7 2 5 10 10 4 10 7 6 5 9 2 7 1 2 2 10 9 10 2 10 3 6 5 10 3 5 2 1 3 10 7 5 10 5 5 4 8 9 10 7 4 2 9 10 1 7 5 5 1 3 7 3 2 9 6 4 1 7 4 7 5 10 4 7 10 10
5 3 2 8 10 3 3 1 4 1 4 10 3 10 6 10 8 9 5 7 9 4 5 4 3 3 3 10 3 7 9 10 7 3 9 3 4 6 6 10 10 10 5 6 7 3 4 1 1 1 7 2 3 5 4 7 4 8 4 8 2 1 6 1 5 6 8 5 8 4 2 10 10 8 4 5 4 5 6 3 8 7 1 1 1 3 9 10 1 10 5 1 7 5 6 1 9 10 10 2
7 3 10 2 10 4 9 4 5 3 5 10 10 8 1 4 5 2 1 4 1 9 9 7 1 5 6 7 4 9 4 9 6 4 5 9 2 5 8 8 2 10 9 4 10 4 10 6 3 5 1 4 2 7 6 3 4 8 1 9 10 1 4 7 3 5 4 8 2 1 8 8 5 3 10 8 4 9 7 1 3 6 5 1 2 4 7 1 6 8 5 5 8 7 5 6 9 7 7 3
7 5 7 10 5 2 8 8 6 2 10 7 9 2 6 10 7 8 3 3 10 4 5 9 8 10 9 10 6 5 6 1 10 3 4 6 5 6 8 3 7 7 9 7 7 10 4 3 7 2 3 3 3 5 10 3 3 10 1 4 7 1 8 2 9 8 7 9 4 10 1 7 1 9 7 6 3 9 3 10 3 3 10 4 4 8 6 10 4 9 7 6 2 3 7 6 3 5 4 9
6 6 3 7 5 4 2 1 5 10 6 9 9 3 3 5 6 9 10 6 5 1 6 1 3 1 5 7 8 3 1 3 4 10 5 2 1 8 6 2 3 6 1 7 5 7 4 5 4 3 9 1 10 4 9 4 4 7 8 6 1 9 6 1 1 7 10 3 8 6 5 10 10 10 9 10 3 5 8 7 3 2 9 4 9 6 3 2 5 3 10 4 9 8 3 9 3 6 9 8
2 8 1 3 5 10 1 6 7 5 6 10 4 6 1 8 5 1 7 3 4 1 6 4 10 6 3 6 9 8 2 5 4 7 7 1 7 4 8 1 4 7 7 2 10 5 7 3 9 2 3 4 3 4 2 2 5 6 8 10 2 1 6 1 10 2 9 10 5 10 4 8 8 10 2 5 3 4 8 6 7 9 1 5 8 6 5 9 7 5 2 1 6 2 6 9 10 2 5 7
3 2 4 9 8 4 3 4 2 7 3 4 7 8 7 1 9 8 5 5 7 10 8 4 4 8 5 1 7 10 2 8 2 6 10 1 7 2 6 1 10 6 9 6 5 1 4 5 5 6 3 3 1 9 7 5 8 9 8 4 1 4 8 4 8 10 7 9 2 3 9 4 7 7 8 10 4 1 3 9 9 9 2 5 4 3 4 6 5 6 8 4 7 3 5 2 9 1 5 10
5 9 4 1 1 5 6 9 5 5 3 6 9 10 6 6 6 10 9 5 4 7 2 10 7 2 6 9 10 6 1 4 1 9 1 9 1 6 9 5 5 1 5 5 1 8 7 10 5 3 9 6 3 3 4 6 8 7 5 9 3 3 4 7 6 8 6 9 6 7 7 2 8 4 3 7 9 8 2 6 10 10 10 7 7 7 1 8 3 7 2 2 7 10 7 8 9 6 2 9
5 3 10 1 8 2 4 10 1 9 10 2 4 10 5 5 1 6 4 5 3 4 5 3 1 2 5 6 7 1 6 1 3 6 8 3 4 4 10 1 6 4 8 2 1 4 7 1 9 9 2 7 3 4 6 10 8 6 1 2 6 7 6 8 5 1 7 8 8 8 5 7 6 8 4 4 5 8 8 3 5 8 2 1 6 3 7 4 6 3 6 7 4 4 2 5 4 2 9 7
4 6 5 6 2 5 4 4 8 9 3 7 9 8 5 5 9 9 3 3 2 7 6 1 2 7 9 7 1 8 3 8 2 8 10 9 5 2 10 6 3 8 1 7 8 4 8 8 7 3 5 3 4 7 3 5 3 5 3 5 1 5 2 3 9 5 6 9 1 7 6 2 6 10 8 10 4 4 3 5 6 3 10 2 10 1 3 8 10 8 8 5 1 9 4 10 1 2 3 2
7 3 1 1 1 4 8 8 9 5 8 10 2 10 1 5 6 1 1 5 9 2 8 8 2 6 4 1 1 1 10 9 4 9 7 5 6 4 6 7 2 10 6 1 3 6 2 2 8 3 6 2 7 10 2 1 8 3 6 3 8 2 4 1 3 9 8 8 2 1 9 10 8 9 3 10 7 6 1 2 6 5 1 2 7 8 6 10 10 1 8 9 1 9 3 3 7 9 2 5
7 3 3 7 10 5 6 7 4 10 8 8 3 7 5 9 4 5 4 7 8 4 5 10 4 9 5 10 3 5 9 3 9 8 1 4 6 6 9 8 7 4 5 8 5 7 6 5 2 8 5 9 1 9 8 6 8 9 8 1 4 8 3 2 4 1 7 3 3 3 8 1 4 10 4 6 7 7 10 1 1 4 8 10 2 4 9 6 5 9 8 4 2 6 3 5 6 2 9 3
9 8 4 6 1 2 5 7 2 3 3 10 10 10 9 5 7 6 10 3 6 7 2 9 3 10 10 5 3 1 5 8 1 7 9 8 3 2 1 3 4 7 6 7 10 7 7 1 10 7 1 10 4 5 5 9 10 9 10 6 3 7 8 1 3 5 2 10 5 2 8 7 9 10 10 2 2 8 9 7 1 1 9 10 3 10 6 2 9 1 4 8 8 8 5 5 1 1 10 9
6 2 3 1 8 8 6 1 8 1 4 6 10 7 5 5 5 2 8 10 3 3 2 7 5 5 10 8 9 1 4 1 2 5 7 8 10 8 5 3 9 5 3 6 10 5 10 1 6 3 5 1 10 3 6 8 3 3 4 1 8 3 6 5 4 7 10 1 10 5 10 3 10 1 8 5 3 3 8 10 8 1 5 3 9 8 2 6 8 3 1 6 6 3 3 6 5 8 3 4
7 3 1 10 10 9 5 7 4 6 8 2 6 1 1 9 6 1 7 7 2 2 9 9 1 3 3 6 8 2 3 2 8 7 7 7 5 7 6 4 10 4 7 5 1 5 2 1 5 2 1 5 10 10 7 3 7 8 10 5 7 1 1 2 2 3 1 7 2 4 4 4 4 9 4 1 6 6 9 6 6 7 8 7 2 5 7 2 6 4 3 10 9 9 1 1 8 8 7 2
7 3 6 6 3 9 4 5 7 9 6 3 10 1 7 1 7 4 6 4 2 1 7 3 3 1 7 10 6 7 5 2 7 9 8 8 2 6 6 6 7 1 10 10 6 6 9 5 5 2 2 3 8 5 1 9 7 1 4 7 1 3 4 3 5 10 1 5 10 7 7 6 8 2 9 1 10 1 1 8 1 3 1 4 7 5 7 6 8 7 5 6 1 5 3 10 8 4 1 7
4 5 6 4 5 6 6 1 2 9 7 1 2 5 6 9 2 3 2 5 1 1 1 9 3 1 6 5 3 1 3 10 6 1 2 8 1 3 6 9 3 7 1 5 2 1 5 5 2 4 10 7 6 1 3 3 7 3 10 6 9 9 4 7 2 10 8 4 3 3 8 1 2 1 4 9 8 5 1 7 3 5 6 10 4 8 3 7 9 7 4 4 9 10 6 3 4 2 8 10
7 7 10 10 4 4 2 5 8 6 6 2 2 3 2 3 6 1 4 7 5 1 9 6 3 3 4 10 5 5 1 5 8 2 10 9 3 7 2 2 3 1 5 7 5 2 6 10 4 1 10 10 5 4 8 6 7 7 7 6 3 4 9 4 10 10 10 7 3 1 1 10 3 6 10 5 8 5 4 6 8 3 2 6 5 2 9 3 7 3 2 4 1 7 9 10 4 5 2 6
2 1 6 10 2 3 9 5 4 5 4 8 4 6 3 4 5 2 5 3 3 4 3 4 5 9 7 2 6 3 3 9 9 1 7 7 3 7 7 10 8 8 2 5 10 4 2 3 1 8 5 1 6 3 8 5 8 8 6 5 4 1 2 6 6 7 10 10 4 2 3 9 8 5 10 6 2 3 1 6 4 2 7 4 5 7 2 3 4 5 8 6 8 6 4 1 6 3 3 6
8 8 6 6 6 7 1 2 6 4 4 1 5 5 5 1 9 3 9 2 6 6 5 4 2 3 1 7 5 10 3 9 3 8 8 7 5 4 5 8 7 3 10 1 5 10 7 2 2 9 7 9 2 6 6 2 3 6 7 1 1 2 5 3 4 10 10 4 8 5 9 7 5 8 6 1 7 9 3 10 4 5 6 5 3 9 1 3 9 2 7 2 7 8 9 2 4 3 4 1
4 7 4 3 3 4 7 4 8 6 5 6 4 10 5 10 7 10 8 9 10 6 7 7 9 3 7 4 7 6 3 4 8 6 9 4 7 8 8 4 10 7 10 6 2 4 7 7 3 7 3 3 6 6 8 6 5 10 1 1 8 1 2 4 2 6 4 1 6 4 6 6 5 4 5 6 7 1 5 3 6 8 8 1 10 7 6 7 10 5 2 4 7 4 9 3 3 8 3 6
6 7 2 7 9 9 8 6 1 5 10 9 7 6 6 9 8 3 6 3 3 9 7 1 10 5 2 8 4 5 9 10 8 7 5 7 9 9 1 1 10 5 9 4 6 9 6 1 8 10 2 1 8 3 8 10 8 9 3 3 10 3 2 4 8 3 3 3 8 1 8 7 2 6 3 1 7 9 6 1 10 1 1 7 10 9 7 1 1 10 6 1 3 3 6 8 1 4 5 10
3 5 9 8 7 8 7 5 10 5 9 4 9 8 8 1 4 5 3 4 6 5 10 4 1 10 5 1 8 3 5 5 2 5 10 8 4 5 6 10 10 6 3 6 1 5 9 8 2 10 3 1 2 7 7 8 3 4 9 9 10 5 2 7 1 7 9 3 1 3 3 3 1 3 1 10 1 9 1 7 1 3 2 6 5 3 9 1 2 6 2 8 1 4 6 9 4 3 6 9
4 5 3 3 10 7 1 2 4 4 9 2 10 3 7 3 2 8 5 8 7 7 6 1 3 5 8 1 1 2 9 4 8 10 1 6 1 2 5 6 5 5 7 6 5 2 1 7 9 10 8 8 3 9 1 6 6 3 8 3 7 2 10 7 4 7 8 10 1 9 9 7 9 10 4 5 8 8 2 7 10 6 6 2 1 1 10 9 6 1 6 1 10 3 2 7 9 4 7 3
7 1 4 8 1 6 8 10 9 10 8 2 4 1 4 7 1 5 4 7 8 8 8 5 4 5 8 8 1 5 6 2 1 3 9 4 7 1 2 1 8 8 10 2 5 6 4 1 3 5 10 1 10 6 9 3 7 5 9 3 1 8 1 1 2 7 1 2 1 9 4 8 5 1 6 9 3 8 6 1 5 9 6 9 9 10 1 1 3 7 1 3 6 9 3 4 8 4 10 10
1 7 7 9 3 4 3 3 10 7 1 10 2 10 5 1 4 9 4 8 5 4 10 10 2 1 5 6 7 3 7 9 8 3 10 5 6 5 1 3 5 10 7 2 6 4 3 3 5 2 7 7 2 10 4 9 4 1 7 8 3 6 4 2 8 8 6 2 2 10 7 10 5 7 3 6 5 1 4 7 9 9 2 2 8 5 8 7 9 4 8 3 8 4 10 10 4 7 6 6
6 4 10 9 5 3 7 10 4 8 9 3 1 8 4 3 8 10 6 3 3 2 2 9 5 6 3 10 8 3 10 3 7 9 3 4 2 3 4 8 5 6 7 7 8 7 6 10 6 4 9 10 1 2 1 8 5 3 4 3 9 1 1 5 2 7 9 2 8 9 7 2 5 1 7 1 7 1 2 2 4 8 8 7 10 2 7 8 2 6 7 6 4 6 7 4 9 10 8 6
8 6 7 8 10 9 3 3 10 10 4 9 2 10 3 8 2 7 10 4 4 6 2 5 10 3 10 5 3 7 9 10 6 3 5 8 3 2 9 8 5 9 8 2 9 6 4 5 6 2 10 5 1 7 5 2 4 1 8 1 9 4 1 8 8 3 9 6 3 3 6 6 7 2 6 10 4 1 9 10 2 10 5 4 4 2 3 8 8 2 3 4 7 4 3 5 6 4 10 9
7 10 9 6 9 2 9 1 4 5 8 10 1 5 6 6 2 4 1 1 7 9 7 7 8 10 3 2 5 2 3 9 7 3 8 8 7 7 3 7 1 5 6 8 6 8 8 1 5 3 3 5 6 4 5 4 9 1 9 9 1 4 8 7 4 4 8 6 2 5 9 10 7 3 7 7 4 9 8 10 2 9 1 5 7 7 10 4 5 2 1 6 2 3 5 9 3 8 2 4

Answer 1

This is the algorithm I've found. It's O(n^2) so it's around optimum. Why? You have to read n^2 cells so the OPT will be at least O(n^2).

Count sums of all rows and all columns. Store them in a class like that:

public class Sum implements Comparable {
    public long currentSum;
    public boolean isRow;
    public int index;

    public Sum(long sum, boolean row, int i) {
        currentSum = sum;
        isRow = row;
        index = i;
    }

    public Sum(Sum s) {
        currentSum = s.currentSum;
        isRow = s.isRow;
        index = s.index;
    }

    @Override
    public int compareTo(Object o) {
        Sum s = (Sum)o;
        return  Long.compare(this.currentSum, s.currentSum);
    }
}

The algorithm is:

1. If there is a column or a row which has the smallest sum (i.e. it's the only lowest sum) - choose it.
2. If there are more then one smallest sums:
    a)if there are no rows with smallest sum - pick column
    b)if there are no cols with smallest sum - pic row
    c)Try both out otherwise

Store the Sums in a heap - e.g. java.util.PriorityQueue. Better write your own heap. It can be also a list which you will sort, but it will be less efficient. Here you have to make some research on which data structure will be most efficient on resorting when half of the elements get incremented and one strongly enlarged.

I've implemented the working solution with an ArrayList. Feel free to use it, but you'll have to change the code a little bit for efficiency.

 //Creates list of all available sums. Sorts them and passes to calculate
 public static int solution(int[][] a, int K, int n) {

    List<Sum> sums = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        int rowSum = 0;
        int colSum = 0;
        for (int j = 0; j < n; j++) {
            rowSum += a[i][j];
            colSum += a[j][i];
        }
        sums.add(new Sum(rowSum, true, i));
        sums.add(new Sum(colSum, false, i));
    }
    Collections.sort(sums);
    return calculate(sums, K, n, 0);
}

public static int calculate(List<Sum> sums, int K, int n, int res) {

    //if (K < 50) System.out.println(K);
    int result = res;
    for (int i = 0; i < K; i++) {
        Collections.sort(sums);
        Sum chosenSum;
        if (sums.get(0).currentSum == sums.get(1).currentSum && K > 1) {
            long low = sums.get(0).currentSum;

            int colCount = 0;
            int rowCount = 0;
            Sum rows = null;
            Sum cols = null;
            for (Sum s : sums) {
                if (s.currentSum == low) {
                    if (s.isRow) {
                        rowCount++;
                        if (rows == null) {
                            rows = s;
                        }
                    } else {
                        colCount++;
                        if (cols == null) {
                            cols = s;
                        }
                    }
                }
            }
            if (colCount == 0) {
                chosenSum = rows;
            } else if (rowCount == 0) {
                chosenSum = cols;
            } else {
                chosenSum = (calculate(copySums(sums), K - i, n, new Sum(rows)) < calculate(copySums(sums), K - i, n, new Sum(cols)) ? rows : cols);
            }
        } else {
            chosenSum = sums.get(0);
        }

        result += chosenSum.currentSum;
        chosenSum.currentSum += n;
        for (Sum s : sums) {
            if (chosenSum.isRow ^ s.isRow) {
                s.currentSum++;
            }
        }
        Collections.sort(sums);
    }

    return result;
}

public static int calculate(List<Sum> sums, int K, int n, Sum chosenSum) {

    for (Sum s : sums) {
        if (chosenSum.isRow ^ s.isRow) {
            s.currentSum++;
        }
        if (s.isRow == chosenSum.isRow && s.index == chosenSum.index) {
            s.currentSum += n;
        }
    }
    Collections.sort(sums);

    return calculate(copySums(sums), K, n, (int) chosenSum.currentSum);
}

public static List<Sum> copySums(List<Sum> sums) {
    ArrayList<Sum> result = new ArrayList<>();
    for (Sum s : sums) {
        result.add(new Sum(s));
    }
    return result;
}

This code returns 30050 in case 100 57. Still 50778 for 100 93 test case.