SWAPMATR- Editorial

general
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Praveen Dhinwa
Tester 1 Goutham Kobakini
Tester 2 Arjun Arul
Editorialist: Praveen Dhinwa

DIFFICULTY:

Easy

PREREQUISITES:

understanding of factorization, maintaining prefix sums in two dimensional grid.

PROBLEM:

You are given a binary matrix (i.e. each element of matrix is either 0 or 1) of size n \times n. You want to swap 0’s and 1’s in such a way that all the 1’s of the matrix form a rectangular region.
If it is not possible to do so, print -1.

QUICK EXPLANATION

  • Make an array sum[N][N] where sum[i][j] denotes number of 1’s (which is also equal to sum as 0’s contribute nothing in sum) in the array made of region top left coordinate is (0, 0) and bottom right coordinate is (i, j).
  • As we know that the rectangular region should contain only 1’s and all the 1’s of the matrix. So it’s area will be equal to number of 1’s in the entire matrix.
  • Now if we fix the height to some integer from 1 to n, width is also fixed. Also note that height should be a divisor of area, otherwise width won’t be integral.
  • So we iterate over all possible heights h (corresponding width = w) and check maximum number of 1’s in a sub-matrix of size h \times w in \mathcal{O} (n^2) time. Note that have to swap out all the 0’s from this matrix with outside 1’s. So total swaps taken will be equal to number of zeros in this sub-matrix.

EXPLANATION

Find the area of rectangular region in which all the 1’s will go finally
As we know that the rectangular region should contain only 1’s and all the 1’s of the matrix. So its area will be equal to number of 1’s in the entire matrix. It can be computed in \mathcal{O} (n^2) time.

Fix height of the rectangular region
Now we will iterate from h = 1 to n where h denotes the height of rectangular region. We can find w from h easily as h will be \frac{area}{w}. Note that we don’t have to consider all h's from 1 to n. We only need to consider the h's which divide n completely, otherwise width w won’t be integral.

Number of swaps required are related to number of 1’s and 0’s
Let us consider a rectangle having height h and width w, then if want this to contain 1’s only, then we have to swap all the 0’s from this rectangle with 1’s from the remaining region of matrix. Hence total number of swaps needed will be equal to total number of zeros in this region.

As our target it to minimize the number of swaps, so we want to minimize number of 0’s in the region. Alternately we can say that we want to maximize the number of 1’s in the region. In other words, we can say that we want to maximize the sum of the elements of the region.

Solving the problem when height and width of rectangle are fixed
Now we will iterate over all possible regions of given height and width and we will pick the region containing most number of 1’s. So we need to have a function which can count number of 1’s in a sub-matrix efficiently.

Counting number of 1’s in a sub-matrix of a binary matrix
This part was one of the most important parts of the problem.

Assume that you want to solve this problem for one dimensional array instead of matrix, i.e. you want to find sum of sub-array (a[L, \ R]). The idea is that you can maintain a prefix sum array. So sum[i] will denote the sum of elements of the array from 1 to i. Then sum of subarray a[L, \ R] will be sum[R] \ - \ sum[L - 1].

We have to use the same idea for 2 dimensions. Here sum[i][j] denotes sum of binary matrix where top left coordinate is (0, 0) and bottom right coordinate is (i, j).
We can create this array in \mathcal{O} (n^2) time easily.

Now assume we have to find number of 1’s (i.e. sum of sub-matrix) of a sub-matrix whose top left coordinate is (x1, y1) and bottom right coordinate is (x2, y2).
Then it will be equal to sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1].

Drawing
Drawing811×529 3.2 KB

In the diagram above, we need to the area of green region (i.e. sum of subarray from a[x1][y1] to a[x2][y2]).
So for finding that, we need to subtract regions of violet, orange and blue regions.
Here sum[x2][y2] denotes the entire region.
sum[x2][y1 - 1] denotes violet and green region.
sum[x1 - 1][y2] denotes orange and green region.
As we have subtracted green region twice, We had to subtract it only one times, so we need to add it one more times.
So we also add sum[x1 - 1][y1 - 1] which denotes green region.

Overall time complexity
So we can notice that we are taking \mathcal{O} (n^2) time for each fixed height from 1 to n which divides area. So in the worst case, as area could be up to 10^6. Total number of divisors of 10^6 won’t be much larger. (around 200 or so). So total time will be \mathcal{O}(200 * n^2) which means around 2 * 10^8 operations that will pass easily in given time.

AUTHOR’S, TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

2

DON’T Know whats wrong with my code and logic it showing wrong answer

 /**
 * Programmer Coder Logic Builder : Osama Inayat
 */

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.logging.Level;
import java.util.logging.Logger;

public class Main {

   

    public static void main(String[] args) {

   
Scanner scanner = new Scanner(System.in);
            int numberOfOnes = 0;
            int T = scanner.nextInt();

            for (int t = 1; t <= T; t++) {
                int n = scanner.nextInt();

                int loopCounter, swapCounter = 0;
                boolean rowContainsZero = false;
                int array[][] = new int[n][n];
                boolean reject = true;
                //Worst and the most simpler conditions
                if (n == 1) {
                    System.out.print("0");
                    exitingSystem();
                }
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        array[i][j] = scanner.nextInt();
                        if (array[i][j] == 1) {
                            numberOfOnes++;
                        }
                    }
                }
                if (n % 2 == 0 && numberOfOnes % 2 != 0) {
                    System.out.println("-1");
                    if (t == T) {
                        exitingSystem();
                    }
                    continue;

                } else if (n % 2 != 0 && numberOfOnes % 2 == 0) {
                    System.out.println("-1");
                    if (t == T) {
                        exitingSystem();
                    }
                    continue;
                }
                //     System.out.println("Here i am");
                //From here swaping processes will take the place
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        if (array[i][j] == 1) {
                            continue;
                        } else if (array[i][j] == 0) {
                            loopCounter = i;
                            reject = true;
                            while (loopCounter < n) {
                                if (array[loopCounter][j] == 1) {
                                    int temp = array[loopCounter][j];
                                    array[loopCounter][j] = array[i][j];
                                    array[i][j] = temp;
                                    reject = false;
                                    swapCounter += 1;
                                    break;
                                }
                                loopCounter++;
                            }
                             if (rowContainsZero) {
                                System.out.println("" + swapCounter);
                                    break;
                            }
                            if (reject == true) {
                                System.out.println("-1");
                                break;
                            } else {
                                for (int m = i + 1; m < n; m++) {
                                    for (int k = 0; k < n; k++) {
                                        if (array[m][k] == 0) {
                                            rowContainsZero = true;
                                        } else {
                                            rowContainsZero = false;
                                            break;
                                        }
                                    }
                                }
                            }
                           
                        } else {
                            System.out.println("0's and 1's were Expected :(");
                            exitingSystem();
                        }
                    }
                    if (reject == true) {
                        break;
                    }
                }
            }
       
    }

    public static void exitingSystem() {
        System.exit(0);
    }

}