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

Cochrane

There is too much badly structured information in this question. I can not understand what you need, what problem you are having or whatsoever. Consider truncating to the necessary information. Consider embedding the relevant portions of the links in the question itself too. If you do, I hope I will be able to provide you help. – Bokbokhara

At which point is Dijkstra heuristic? – Sequela

@Cochrane take a look at en.wikipedia.org/wiki/Admissible_heuristic your h(x) function might be wrong. Also, as xenteros mentioned, Dijkstra should not have a heuristic to estimate distance to goal, do check your notes. – Interosculate

This is a straight forward programming task. There is no need for any heuristics or shortest path search, nor do I see where an "optimum value" would appear. – Martie

@Cochrane I would like to the value of "k" that you have used for the above example. – Giffer

@Cochrane What is the value of k when you choose 100x100 matrix in which your test cases are failing? – Giffer

dropbox, or give the link to the test question – Laplace

@yeppe: I am getting 24 as the answer for the above sample data that you have given. Can you confirm how you got 22? – Giffer

@Giffer 22 is the correct result. – Sequela

@Sequela Hi, can you share the steps on what you have selected after getting the row value and column value as same in the given example – Giffer

@Giffer left ->3, top->5, left->6, any ->8 sums to 22 – Sequela

@Sequela I didn't get what are left, top, any here. What I have done is: 1. Step - minimum value is row with 4 2. step - both row and column has minimum value which is 6. I am confused to select row/column here. If I take column then I get 24. If I take row then I get 22. – Giffer

@Giffer the input is: 2 - size of the matrix, 4 - number of steps, then the array – Sequela

@Sequela I did the given sample matrix using the logic given in https://mcmap.net/q/1320140/-matrix-manipulation-logic-not-fetching-correct-answer-for-higher-order-nxn-matrix-data. I ran my code for the data he wrote on a piece of paper and it worked like a charm where as when I gave the sample data provided in the above I am getting 24. And yes I got it cleared that we need to run it k times and my k value for the data given is 4. And my matrix is [[2,4],[1,3],[2,4]] – Giffer

@Sequela if possible can you explain in the same way so that I can get a clear cut picture on how to solve it. – Giffer

@Giffer your matrix should be 2x2 – Sequela

@Sequela in that case can you give me the matrix through which you have got that value in terms of rows. – Giffer

@Giffer [[1,3], [2,4]] – Sequela

@Sequela I am getting 22 with [[1,3],[2,4]]. Thanks a lot for giving the input matrix and explaining all this while – Giffer

@Cochrane Can you share the file on cloud and edit the post by giving the link of the file that has your 100x100 sized matrix – Giffer

@Giffer Feel free to check my solution - it's fully implemented. – Sequela

@Sequela I saw your approach to your problem which was working absolutely fine. I tried a naive approach for the same problem since I am a newbie to Java which I posted. You can always check my solution and let me know if I need to change or improve a piece of code that is not working fine. – Giffer

I think the problem statement needs to be refined. So is it asking for the minimum value attainable following the procedure? Because so far I see this as just implementing an efficient code to follow the procedure, with the underspecified case when there are multiple row/column sum with the same value. Step 2 can even be interpreted as taking all minimum rows and columns and increment the cells by 1. – Stormystorting

Are you sure that you need to take the minimum at each iteration? Because sometimes not taking the minimum can lead to lower value. For example: N=4, K=3, array = [[2,1,0,0], [2,0,1,0], [2,0,0,1], [0,0,0,0]]. One of the row sum is 0, which is minimum. But if you take that, after 3 iterations the value is 4 (0+2+2). Note that you can reach 3 by selecting the three columns with value 1. – Stormystorting

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.

Sequela

@Cochrane For the smallest counter-example: N=3, K=2. Array = [[1,0,1], [0,1,1], [0,0,1]]. Row sums: [2, 2, 1]. Col sums: [1, 1, 3]. If you take the row first, the output will be 2 (as all col sums will be incremented by 1). If you take one of the columns first, the result will be 1 (as next you will again take the col sum with value 1). Basically this is the combination of the two cases mentioned by xenteros: two same values in columns and one in row. – Stormystorting

I thought the output is the last minimum row/col sum? Or is it the sum of all min row/col sum over k iterations? – Stormystorting

To clarify, so the crux of the problem here is to find out "how to pick the row/col with minimum sum when there are multiple of them, such that the total sum after k iterations is minimized"? – Stormystorting

I'm also implemented something which I believe is correct (consider all possible choices) and the result is 50778. Do you happen to know the sequence of selection for your third test case that leads to 50708? There are only 4 conflict cases in that test case if I'm not wrong. – Stormystorting

@yeppe: Your case 2 I can get 30050. But I believe for case 3 it is 50778, not 50708. I'll post my answer. – Stormystorting

But I'm not going row-wise or column-wise, instead, I try both (see my answer). – Stormystorting

I'm not sure, but they could very possibly be the same, it's just that I implemented more heuristics as optional features. Do you also get 4 paths for case 3 in your brute force? – Stormystorting

Another difference might be that my algorithm doesn't copy the sum object, so it is memory efficient. – Stormystorting

Ah, I just saw your update on the algorithm. So you have some heuristics (e.g. when there are more rows, pick row). I traverse both in that case. – Stormystorting

Congrats xenteros! Though I think the problem is ill-defined. As we have followed the procedure. =/ – Stormystorting

If the objective is to have lowest value at the end of the process, you should fix the description. Currently in the procedure you require us to take the minimum value at each step. If this is not the case, please clarify the problem. – Stormystorting

Answer 2

I am a newbie to Java. So, I am using this naive approach to find the result for your problem. I am calculating the row sum and column sum and finding the minimum value and incrementing it by +1 accordingly. When I encounter same value for both row and column that is when I am trying to hold the previous iteration row and column values and getting the next least from there and incrementing it.

Also, I have taken care of not just NxN matrix but also for MxN matrix.

Below is my approach for this problem:

try {
            for (k = 0; k < 4; k++) {
            int rowSum[] = new int[arr.length];
            int columnSum[] = new int[arr[0].length];

            // Gets the sum for rows

            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < ((arr[0].length)); j++) {
                    rowSum[i] = rowSum[i] + arr[i][j];
                }
            }
            System.out.println("Row sum is: " + Arrays.toString(rowSum));

            // Gets the sum for columns

            for (int j = 0; j < arr[0].length; j++) {
                for (int i = 0; i < (arr.length); i++) {
                    columnSum[j] = columnSum[j] + arr[i][j];
                }
            }

            System.out.println("Column sum is: " + Arrays.toString(columnSum));

            // to find the smallest

            int minRowSumValue = rowSum[0];
            for (int i = 0; i < rowSum.length; i++) {
                if (rowSum[i] < minRowSumValue) {
                    minRowSumValue = rowSum[i];
                }
            }
            System.out.println("Min row sum value is: " + minRowSumValue);

            int minColSumValue = columnSum[0];
            for (int i = 0; i < columnSum.length; i++) {
                if (columnSum[i] < minColSumValue) {
                    minColSumValue = columnSum[i];
                }
            }
            System.out.println("Min column sum value is: " + minColSumValue);

            if (minRowSumValue < minColSumValue) {
                int a = getArrayIndex(rowSum, minRowSumValue);
                for (int i = a; i < arr.length; i++) {
                    for (int j = 0; j < ((arr[0].length)); j++) {
                        arr[i][j] = arr[i][j] + 1;
                    }
                    oldMinSumColValue = minColSumValue;
                    oldMinSumRowValue = 0;
                    finalSum += minRowSumValue;
                    break;
                }

            } else if (minColSumValue < minRowSumValue) {
                int a = getArrayIndex(columnSum, minColSumValue);
                for (int j = a; j < arr[0].length; j++) {
                    for (int i = 0; i < (arr.length); i++) {
                        arr[i][j] = arr[i][j] + 1;
                    }
                    oldMinSumRowValue = minRowSumValue;
                    oldMinSumColValue = 0;
                    finalSum += minColSumValue;
                    break;
                }
            } else if(minRowSumValue == minColSumValue) {
                if (oldMinSumRowValue != 0) {
                    int a = getArrayIndex(rowSum, oldMinSumRowValue);
                    for (int i = a; i < arr.length; i++) {
                        for (int j = 0; j < ((arr[0].length)); j++) {
                            arr[i][j] = arr[i][j] + 1;
                        }
                        finalSum += minRowSumValue;
                        break;
                    }
                } else {
                    int a = getArrayIndex(columnSum, oldMinSumColValue);
                    for (int j = a; j < arr[0].length; j++) {
                        for (int i = 0; i < (arr.length); i++) {
                            arr[i][j] = arr[i][j] + 1;
                        }
                        finalSum += minColSumValue;
                        break;
                    }
                }
            }
            System.out.println("\nArray is: " + Arrays.deepToString(arr));
        }
        System.out.println("\n\nFinal Array after "+k+" steps is: " + Arrays.deepToString(arr));

        System.out.println("\nFinal sum value is: "+finalSum);

    } catch (Exception e) {
        // TODO: handle exception
        System.out.println("Exception is: " + e);
    }

You can easily improve the efficiency by using better approach.

Giffer

@Cochrane What do you mean by that. Is there anything that has gone wrong with the approach? You can test with the data and check if it works. I guess I have implemented all the cases. may be the execution time will be more – Giffer

@Cochrane Ok my bad. Guess I understood that in a different way. I will redo the code and upload it again. Thanks for pointing out the mistake – Giffer

Answer 3

Below is my code. When it encounters ambiguous case (when the minimum values can be found in both row and column), it tries both cases and output the minimum.

For each iteration, it sorts two lists of n values. So the complexity is O(C*k*n log n), where C is the number of distinct paths. I believe this is quite close to optimal (in terms of complexity for brute-force), since after each iteration, exactly n+1 values will change and so we need to at least touch each one of them (unless of course, some more algorithmic insight allows us to touch only a few of them). Depending on the values of k and n, this might or might not be good enough. For case 2 it runs in slightly more than 1 second.

import java.util.Scanner;
import java.io.File;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Collections;

/**
 * 11 Aug 2016
 * To answer the following question:
 * http://stackoverflow.com/questions/38697500
 */
class MinRowCol {

    public static boolean DEBUG = false;
    public static boolean USE_QUICK_ALGO = false;
    public static boolean PREFER_ROW = true;
    public static boolean USE_SUM_COUNT = false;

    public static void inc(HashMap<Integer, Integer> sumCount, int key){
        int oldVal = sumCount.getOrDefault(key, 0);
        sumCount.put(key, oldVal+1);
    }

    public static void dec(HashMap<Integer, Integer> sumCount, int key){
        int oldVal = sumCount.getOrDefault(key, 0);
        sumCount.put(key, oldVal-1);
    }

    /**
     * The class to store a sum
     */
    private static final class Sum implements Comparable<Sum>{
        public int sum;
        public boolean isRow;
        /** Count the number of each sum appearing as row sum (used in quick algo) */
        public static HashMap<Integer, Integer> rowSumCount = new HashMap<Integer, Integer>();
        /** Count the number of each sum appearing as col sum (used in quick algo) */
        public static HashMap<Integer, Integer> colSumCount = new HashMap<Integer, Integer>();

        public Sum(int sum, boolean isRow){
            this.sum = sum;
            this.isRow = isRow;
        }

        /**
         * Returns how many times this sum appears in the matrix
         * This function is used in quick algo
         */
        public int getSumCount(){
            int sumCount = 0;
            if(this.isRow){
                sumCount = rowSumCount.get(this.sum);
            } else {
                sumCount = colSumCount.get(this.sum);
            }
            return sumCount;
        }

        /**
         * Update this sum with the diff
         * This will properly update the sum count (this feature is for quick algo)
         */
        public void update(int diff){
            HashMap<Integer, Integer> sumCount;
            if(this.isRow){
                sumCount = rowSumCount;
            } else {
                sumCount = colSumCount;
            }
            dec(sumCount, this.sum);
            inc(sumCount, this.sum+diff);
            this.sum += diff;
        }

        /**
         * Compare based on sum value
         * In quick algo, if the value is the same, the one with higher multiplicity
         * (i.e., appearing multiple times) has priority (i.e., smaller than the other)
         */
        public int compareTo(Sum s){
            if(this.sum < s.sum){
                return -1;
            } else if(this.sum > s.sum){
                return 1;
            } else {
                if(USE_QUICK_ALGO){
                    if(USE_SUM_COUNT){
                        int result = -Integer.compare(this.getSumCount(), s.getSumCount());
                        if(result != 0){
                            return result;
                        }
                    }
                    if(PREFER_ROW){
                        return Boolean.compare(this.isRow, s.isRow);
                    } else {
                        return -Boolean.compare(this.isRow, s.isRow);
                    }
                } else {
                    return 0;
                }
            }
        }

        public String toString(){
            if(USE_QUICK_ALGO){
                return String.format("%d %d %s", this.sum, this.getSumCount(), this.isRow ? "row" : "col");
            } else {
                return String.format("%d %s", this.sum, this.isRow ? "row" : "col");
            }
        }
    }

    public static void main(String[] args) throws Exception{
        String inputFile = args[0];
        if(args.length > 1){
            for(int i=1; i<args.length; i++){
                if(args[i].equals("-v")){
                    DEBUG = true;
                } else if(args[i].equals("-quick")){
                    USE_QUICK_ALGO = true;
                } else if(args[i].equals("-prefer_row")){
                    PREFER_ROW = true;
                } else if(args[i].equals("-prefer_col")){
                    PREFER_ROW = false;
                } else if(args[i].equals("-use_sum_count")){
                    USE_SUM_COUNT = true;
                }
            }
        }
        Scanner scanner = new Scanner(new File(inputFile));
        String line = scanner.nextLine();
        String[] tokens = line.split(" ");
        int n = Integer.parseInt(tokens[0]);
        int k = Integer.parseInt(tokens[1]);
        int[][] matrix = new int[n][n];
        Sum[] rowSums = new Sum[n];
        Sum[] colSums = new Sum[n];
        for(int i=0; i<n; i++){
            rowSums[i] = new Sum(0, true);
            colSums[i] = new Sum(0, false);
        }
        HashMap<Integer, Integer> rowSumCount = Sum.rowSumCount;
        HashMap<Integer, Integer> colSumCount = Sum.colSumCount;
        // Initialize the row sum and col sum
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                matrix[i][j] = scanner.nextInt();
                rowSums[i].sum += matrix[i][j];
                colSums[j].sum += matrix[i][j];
            }
        }
        // Initialize the sum count (NOT USED)
        for(int i=0; i<n; i++){
            Sum rowSum = rowSums[i];
            int val = rowSumCount.getOrDefault(rowSum.sum, 0);
            rowSumCount.put(rowSum.sum, val+1);
            Sum colSum = colSums[i];
            val = colSumCount.getOrDefault(colSum.sum, 0);
            colSumCount.put(colSum.sum, val+1);
        }
        int totSum = minSum(rowSums, colSums, 0, k, new String[k], 0);
        System.out.println(totSum);
    }

    /**
     * Returns the minimum sum after running the procedure for (maxIter-iter) iterations
     * The arguments `selected` and `totSoFar` are for recording the path and the minimum sum, respectively
     */
    public static int minSum(Sum[] rowSums, Sum[] colSums, int iter, int maxIter, String[] selected, int totSoFar){
        int totSum = 0;
        int n = rowSums.length;
        // Consider the minimum in the row and the minimum in the column
        // We don't need to consider multiple minimum values in a row/column
        // since once a minimum value in a row gets picked, the next iteration
        // will surely choose the minimum in the row, since the minimum in
        // the column is no longer a minimum
        Sum minRow = null;
        Sum minCol = null;
        for(int j=0; j<n; j++){
            if(minRow == null || rowSums[j].sum < minRow.sum){
                minRow = rowSums[j];
            }
            if(minCol == null || colSums[j].sum < minCol.sum){
                minCol = colSums[j];
            }
        }
        // Either try both row and column, or just pick row or pick column
        Sum[] minSums;
        if(minRow.compareTo(minCol) < 0){
            minSums = new Sum[]{minRow};
        } else if (minRow.compareTo(minCol) > 0){
            minSums = new Sum[]{minCol};
        } else {
            minSums = new Sum[]{minRow, minCol};
        }
        int curMinSum = minSums[0].sum; // The minimum row/column sum in this iteration
        int subSums = Integer.MAX_VALUE; // To hold the minimum sum after this iteration
        for(Sum minSum: minSums){ // Try all (either one or two) choices
            // Update the sums
            if(minSum.isRow){
                for(int j=0; j<n; j++){
                    colSums[j].update(1);
                }
            } else {
                for(int j=0; j<n; j++){
                    rowSums[j].update(1);
                }
            }
            selected[iter] = minSum.toString();
            minSum.update(n);
            if(iter < maxIter - 1){
                int nextSubSums = minSum(rowSums, colSums, iter+1, maxIter, selected, totSoFar+curMinSum);
                if(nextSubSums < subSums){
                    subSums = nextSubSums;
                }
            } else {
                subSums = 0;
                if(DEBUG){
                    System.out.print("End ("+(totSoFar+curMinSum)+"): ");
                    for(int i=0; i<selected.length; i++){
                        System.out.print(selected[i]+" ");
                    }
                    System.out.println();
                }
            }
            // Revert the sum update we have done earlier
            minSum.update(-n);
            if(minSum.isRow){
                for(int j=0; j<n; j++){
                    colSums[j].update(-1);
                }
            } else {
                for(int j=0; j<n; j++){
                    rowSums[j].update(-1);
                }
            }
        }
        // Return minimum row/col found at this iter + the minimum sum in
        // all iterations after this iteration
        return curMinSum + subSums;
    }
}

It can also print the path it chooses if you supply -v argument:

java MinRowCol MinRowCol.test -v

There are other options:

-quick - This will reduce the number of cases explored by using heuristics. The heuristics can be specified with other options
-prefer_col - This will prefer column over row (by default prefer row)
-use_sum_count - This will use the multiplicity of the sum

For small test case as the following:

3 2
1 0 1
0 1 1
0 0 1

It will output:

End (3): 1 row 2 row
End (3): 1 row 2 col
End (2): 1 col 1 col
2

Meaning it found three possible paths, two of them have value 3, one has score 2. So it picks the one with value 2, and you can see the choices it made (the sum and the row/col). You can see that choosing the column first leads to smaller value at the end.

For case 3 (case 2 has too many options to be displayed here) the four cases lead to the same answer:

End (50778): 455 1 col 480 1 col 486 1 row 494 1 col 498 1 row 500 1 col 502 1 col 506 1 col 509 1 col 510 1 col 512 2 row 512 1 row 513 1 row 514 1 row 515 1 row 519 2 row 519 1 row 520 1 row 524 1 row 525 1 col 526 1 col 527 1 col 529 1 row 530 1 row 531 1 row 533 1 row 534 2 row 534 1 row 535 2 row 535 1 row 538 2 row 538 1 row 539 2 row 539 1 row 541 3 row 541 2 row 541 1 row 542 1 row 543 2 row 543 1 row 544 2 row 544 1 row 545 1 row 548 1 row 549 3 row 549 2 row 549 1 row 550 1 row 553 3 row 553 2 row 553 1 row 554 2 row 554 1 row 556 1 row 557 2 row 557 1 row 558 1 row 559 3 row 559 2 row 559 1 row 561 1 row 563 2 row 563 1 row 564 4 row 564 3 row 564 2 row 564 1 row 565 1 row 567 2 row 567 1 row 569 1 row 570 2 row 570 1 row 571 1 row 572 1 row 573 1 row 574 3 row 574 2 row 574 1 row 575 2 row 575 1 row 576 2 row 576 1 row 577 2 row 577 1 row 578 2 row 578 1 row 579 1 row 582 1 row 583 2 row 583 1 row 584 2 row 584 1 row
End (50778): 455 1 col 480 1 col 486 1 row 494 1 col 498 1 row 500 1 col 502 1 col 506 1 col 509 1 col 510 1 col 512 2 row 512 1 row 513 1 row 514 1 row 515 1 row 519 2 row 519 1 row 520 1 row 524 1 col 525 1 row 526 1 col 527 1 col 529 1 row 530 1 row 531 1 row 533 1 row 534 2 row 534 1 row 535 2 row 535 1 row 538 2 row 538 1 row 539 2 row 539 1 row 541 3 row 541 2 row 541 1 row 542 1 row 543 2 row 543 1 row 544 2 row 544 1 row 545 1 row 548 1 row 549 3 row 549 2 row 549 1 row 550 1 row 553 3 row 553 2 row 553 1 row 554 2 row 554 1 row 556 1 row 557 2 row 557 1 row 558 1 row 559 3 row 559 2 row 559 1 row 561 1 row 563 2 row 563 1 row 564 4 row 564 3 row 564 2 row 564 1 row 565 1 row 567 2 row 567 1 row 569 1 row 570 2 row 570 1 row 571 1 row 572 1 row 573 1 row 574 3 row 574 2 row 574 1 row 575 2 row 575 1 row 576 2 row 576 1 row 577 2 row 577 1 row 578 2 row 578 1 row 579 1 row 582 1 row 583 2 row 583 1 row 584 2 row 584 1 row
End (50778): 455 1 col 480 1 col 486 1 row 494 1 col 498 1 row 500 1 col 502 1 col 506 1 col 509 1 col 510 1 col 512 2 row 512 1 row 513 1 row 514 1 row 515 1 row 519 2 row 519 1 row 520 1 row 524 1 col 525 1 col 526 1 row 527 1 col 529 1 row 530 1 row 531 1 row 533 1 row 534 2 row 534 1 row 535 2 row 535 1 row 538 2 row 538 1 row 539 2 row 539 1 row 541 3 row 541 2 row 541 1 row 542 1 row 543 2 row 543 1 row 544 2 row 544 1 row 545 1 row 548 1 row 549 3 row 549 2 row 549 1 row 550 1 row 553 3 row 553 2 row 553 1 row 554 2 row 554 1 row 556 1 row 557 2 row 557 1 row 558 1 row 559 3 row 559 2 row 559 1 row 561 1 row 563 2 row 563 1 row 564 4 row 564 3 row 564 2 row 564 1 row 565 1 row 567 2 row 567 1 row 569 1 row 570 2 row 570 1 row 571 1 row 572 1 row 573 1 row 574 3 row 574 2 row 574 1 row 575 2 row 575 1 row 576 2 row 576 1 row 577 2 row 577 1 row 578 2 row 578 1 row 579 1 row 582 1 row 583 2 row 583 1 row 584 2 row 584 1 row
End (50778): 455 1 col 480 1 col 486 1 row 494 1 col 498 1 row 500 1 col 502 1 col 506 1 col 509 1 col 510 1 col 512 2 row 512 1 row 513 1 row 514 1 row 515 1 row 519 2 row 519 1 row 520 1 row 524 1 col 525 1 col 526 1 col 527 1 row 529 1 row 530 1 row 531 1 row 533 1 row 534 2 row 534 1 row 535 2 row 535 1 row 538 2 row 538 1 row 539 2 row 539 1 row 541 3 row 541 2 row 541 1 row 542 1 row 543 2 row 543 1 row 544 2 row 544 1 row 545 1 row 548 1 row 549 3 row 549 2 row 549 1 row 550 1 row 553 3 row 553 2 row 553 1 row 554 2 row 554 1 row 556 1 row 557 2 row 557 1 row 558 1 row 559 3 row 559 2 row 559 1 row 561 1 row 563 2 row 563 1 row 564 4 row 564 3 row 564 2 row 564 1 row 565 1 row 567 2 row 567 1 row 569 1 row 570 2 row 570 1 row 571 1 row 572 1 row 573 1 row 574 3 row 574 2 row 574 1 row 575 2 row 575 1 row 576 2 row 576 1 row 577 2 row 577 1 row 578 2 row 578 1 row 579 1 row 582 1 row 583 2 row 583 1 row 584 2 row 584 1 row
50778

For case 2, the result is as follows:

With no options (search all cases):

30050

With -quick -prefer_row:

30066

With -quick -prefer_col:

30050

So we do need to explore multiple paths. But I'm not sure why for case 3 the correct answer should be 50708 instead of 50778.

Stormystorting

Answer 4

You don't actually need to keep the whole matrix, just the sums, by row and by column.

Given a NxN matrix, let SumByRow be a vector of length N which contains the sum of each row of the matrix, and let SumByCol be the same thing regarding columns. In your example, those vectors would be:

Matrix = [ [1,3],
           [2,4]]

SumByRow = [4,6]
SumByCol = [3,7]

Now, regardless of the actual index of the minimum row[column] we can be sure of one thing: that at the next iteration the SumByRow[Col] vector would have one element incremented by N(because we are adding one to each element of that row[column]) and the SumByCol[Row] would have 1 added to each of its elements(because whatever the sum was, we are adding one to one and only one of the elements that compose it).

So we can get rid of the big ugly matrix and work with those two vectors. The reasoning above also suggest a way to implement the iteration, namely:

Step one: find index of minimum element between both vectors
Step two: increase final sum by that element's value, increase that element by N, increase each element of other vector by one
Step three: rinse and repeat until smooth anf fluf- enough iterations have been calculated

There's one last kink, what shall we do in case of same minimum value of the sum by both row and column? Going random isn't really helpful, nor it is always chosing one over the other, as those methods could toss you into a suboptimal lane, some form of lookahead is then called for. I opted for a simple simulation of what would happen at the next step if both options would have been invalidated, in a recursive but limited manner, so to try and look ahead for as much as possible. But there might well be a more efficient heuristic approach, or even a fully complete strategy, but none of that comes to my mind right now.

EDIT: Actually, thanks to justhalf, I'm not sure anymore that a locally greedy approach is any good, as an optimal strategy might start with some not explicitly optimal choices...

Here is the code I cobbled togheter to demonstrate, it's quite ugly but I hope understandable, please let me know if you spot errors or need any clarification https://ideone.com/EZW3wt

from numpy import matrix
import numpy as np
n = 2
k = 4
A = matrix([[1,3],
            [2,4]
            ])

sc = [0]*n
sr = [0]*n
for i in range(0,n):
    sc[i] = sum( A.A[:,i] )
    sr[i] = sum( A.A[i,:] )
output=0

def whichmin(c,r, iter):
    if(iter < 0):
        return 1
    r[np.argmin(r)] += n
    c[np.argmin(c)] += n
    if ( np.amin(c) < np.amin(r) ):
        return 1
    elif ( np.amin(r) < np.amin(c) ):
        return 0
    else :
        return whichmin(c,r, (iter -1) )

for j in range(0,k):
    minc = np.amin(sc)
    minr = np.amin(sr)
    if (minc < minr):
        incrindex = np.argmin(sc)
        sc[incrindex]+=n
        sr = [x+1 for x in sr]
        output += minc
    elif (minr < minc):
        incrindex = np.argmin(sr)
        sr[incrindex]+=n
        sc = [x+1 for x in sc]
        output += minr
    else :
        min = whichmin(sc.copy(),sr.copy(), (n - i) )
        if (min==1):
            incrindex = np.argmin(sc)
            sc[incrindex]+=n
            sr = [x+1 for x in sr]
            output += minc
        else:
            incrindex = np.argmin(sr)
            sr[incrindex]+=n
            sc = [x+1 for x in sc]
            output += minr

print(output)
print(sc)
print(sr)

Lampkin

Sorry...You can't keep just the sums: You need to record the whole matrix. – Enthronement

@Bohemian: Why do you think it is so? The values in the matrix won't give any difference in the behaviour of the sums, since each move (picking a sum and then increase the values accordingly) is deterministic and the behaviour is well-defined with knowing just the sums. – Stormystorting

@Stormystorting not if there are a row and column with the same sum – Enthronement

Oh, you mean if we are storing the result as a set? As a list I don't see a problem, since we would always record 2*n number of sums. – Stormystorting