How to find entry of each a(i, j) in n*n matrix where n<=900 and a(i,j)=0 or a(i, j)=1?

user_11896664 0
Viewed 159

Suppose i have given n basically n*n matrix with all zero's at start.

And sum's associated with each row and column is given.

eg. n=4

Matrix: 

0 0 0 0 
0 0 0 0 
0 0 0 0 
0 0 0 0

given rows sum : 2, 2, 1, 1

given columns sum: 2, 0, 2, 2

So output matrix should look like: 

0 0 1 1
1 0 0 1
0 0 1 0
1 0 0 0

There's always a solution exist. So for n=4, 0<=rowsum<=4 and 0<=columnsum<=4

algorithm java
2 Answers

You can solve this with a greedy approach.

while not filled:
    find biggest unfilled row:
        fill in putting 1s in columns with largest sums

In your case you started with:

    2 2 0 2
  ----------
2 | _ _ _ _
2 | _ _ _ _
1 | _ _ _ _
1 | _ _ _ _

Filling in one of the rows we get:

    1 1 0 2
  ----------
2 | _ _ _ _
  | 1 1 0 0
1 | _ _ _ _
1 | _ _ _ _

Fill in another:

      1   1
  ----------
  | 1 0 0 1
  | 1 1 0 0
1 | _ _ _ _
1 | _ _ _ _

And the other two can be filled in similarly:

  ----------
  | 1 0 0 1
  | 1 1 0 0
  | 0 1 0 0
  | 0 0 0 1

Assuming that the sum of the row values matches the sum of the column values, and 0 <= value <= n for all of them, this procedure will always work.

UPDATE: As pointed out in the comments, it is possible for no solution to exist in other ways. That will be detectable by the fact that you try to fill in a row and there aren't enough columns left to fill it with.

However if you run into such a barrier, then there was no solution.

user_5854110

Btilly's answer will work for you. However it can be improved. Instead of finding the largest-sum row and column each time, you can pre-process by sorting them in descending order, but it's important to keep their original positions stored. You can use a simple class:

class SortedRow {
    int val;
    int originalIndex;
    public SortedRow(val, originalIndex) {
        this.val = val;
        this.originalIndex = originalIndex;
    }
}

Then sort them (rowVals and colVals are the arrays with desired sums):

public static void preprocess(int[] rowVals, int[] colVals){
    SortedRow[] rows = new SortedRow[n];
    SortedRow[] cols = new SortedRow[n];
    for (int i = 0; i < n; i++) {
        rows[i] = new SortedRow(rowVals[i], i);
        cols[i] = new SortedRow(colVals[i], i);
    }
    // Sort both arrays by val with some sorting algorithm of your choice - in descending order!
}

Now you can start filling a nxn matrix in a greedy approach like Btilly suggested, except you don't have to look for the largest one each time around - you already have it. Fill it out by the originalIndex field of the new class.

It improves worst-case runtime from cubic into quadratic: Preprocess runs in O(nlogn), could even be linear if you have some prior knowledge on the value of n. Filling out the matrix runs in O(n^2).

user_121143150
Related