BANDMATR - Editorial

bandmatr
basic-prog
editorial
march17
matrix
simple

#1

PROBLEM LINK:

Practice
Contest

Author: Praveen Dhinwa
Testers: Sergey Kulik, Kamil Dębowski
Editorialist: Pawel Kacprzak

DIFFICULTY:

Simple

PREREQUISITES:

Basic matrix knowledge, basic programming

PROBLEM:

The the bandwidth of a square matrix A is the smallest non-negative integer k, such that for all |i-j| > k A* = 0.

For a given binary square matrix A with N rows and N columns, the goal is to a rearrange its elements to get a matrix with the smallest bandwidth. The answer for the problem is the value of the smallest bandwidth we can get that way.

QUICK EXPLANATION:

Put all 1's on the closest diagonals to the main diagonal and compute the result.

EXPLANATION:

Subtask 1

In the first subtask we know that N is at most 100. We can take advantage of this fact and solve the problem as follows. First, notice that the resulting bandwidth is an integer in a range [0, n-1]. Now, we can iterate over all possible bandwidth candidates starting from the smallest one. For a fixed candidate B, we check if the number of 1's in A is not greater than the number of cells A*[j] for which |i-j| \leq B. If it’s the case, then we return B as the answer because then we can put all 1's into these cells, so B it is the smallest integer fulfilling the condition. Notice that for a fixed B the check can be performed in O(N^2) time, and since there are O(N) values of B to check, then the total time complexity of this method is O(N^3).

Subtask 2

First of all, let’s notice that if we take any of the 2 \cdot N - 1 diagonals of the matrix, and any element on this diagonal, let’s say A*[j], then for each other element A[i_1][j_1] on this diagonal, we have |i-j| = |i_1-i_2|.

Thus each diagonal can be defined by a value x = |i-j| where A*[j] is any element on this diagonal.

Moreover, there is just one diagonal with x=0, the main diagonal. Next, there are exactly 2 diagonals with x=1, the ones adjacent to the main diagonal. In general, for 0 < y \leq N-1 there are exactly two diagonals with x=y and they are the diagonals in distance y from the main diagonal, where the distance from diagonal d to the main diagonal is the number of other diagonals between them.

Based on the following observation, if we want to arrange elements of A in its cells in such a way that k for which for all |i-j| \gt k, A*[j] = 0 is minimal, the best we can do is to place all 1's in cells on diagonals as closest to the main diagonal as possible. Thus we can iterate over diagonals in order of their distances to the main diagonal and fill them with 1's until all ones are used. Then the result is the largest integer k for which 1 was put onto a diagonal with x=k during that process or 0 if there are no 1's in A.

AUTHOR’S AND TESTER’S SOLUTIONS:


Setter's solution can be found [here][333]. First tester's solution can be found [here][444]. Second tester's solution can be found [here][555]. Editorialist's solution can be found [here][666].

#2

I am still not able to understand the condition |i−j|>k A*=0
Can anyone explain with some example?


#3

Nice editorial still One of the way to solve this question is using quadratic equation.

The problem can be observed as filling 0’s from both upside right and downside left of the matrix.

Let cnt = (number of zeroes) in the matrix. Then the number of cells in each diagonal will be like 1, 2, 3, 4, … and so on.

Thus the number of zeroes required to fill the kth diagonal is (1+2+3+4+…+k). which is k*(k+1)/2.

But if the last(kth) diagonal is partially filled then the sum will be like (1+2+3+4+…+k-1) which is (k-1)*k/2.

Thus if cnt is the total number of zeroes, then cnt/2 is the total number of zeroes that can be used to fill the upper right triangle or lower left triangle.

The cells in diagonals starting from upper triangle vary as 1, 2, 3, … and so on… and let cnt = cnt/2.

Thus the equation is k*(k-1)/2 = cnt simplified as k^2 - k - 2cnt = 0. therefore appropriate value of k can be found using k = (1 + sqrt(1 + 8cnt))/2.

Thus k is the diagonal till which 0 can be filled.

Thus the final solution is n-k. Check here for final implementation.

Feel free to tell anything wrong in approach or code or any case missing.


#4

The bandwidth of a matrix M=(m(i,j)) is the maximum value of |i-j| such that m(i,j) is nonzero.

For example In the below matrix

1 0 0

0 1 1

1 1 0

M[3][1] = 1 is the non zero value with maximum value |i-j| (3-1)=2.

So bandwidth of the above matrix is 2.

Now in the question they have asked us to find the minimum bandwidth value such that you can swap non-zero value with zero value.

So if you swap M[3][1] & M[3][3] the matrix will look as

1 0 0

0 1 1

0 1 1

Now if you compute the bandwidth, maximum value of |i-j| is 1 such that M*[j]!=0.(Here i=3,j=2. Another possibility i=2,j=3.)


#5

@aniketsanadhya … You misinterpreted the condition … It is |i - j| > k . This is also equal to k<|i-j| …
For the previous matrix, the bandwidth is 2. Because, when k=2, you cant find an (i,j) where a*[j] is 0 (This is due to the condition |i-j| must be greater than k). So when the change is done, a[3][1] = 0 and now you BW becomes 1 as you cant find an (i,j) where a*[j]=0 (Again due to |i-j|>1).
Hope you understood it.


#6

Irony is even O(N^3) solution was getting Accepted for full points.

Then I wrote this more optimized solution .

Happy Coding :slight_smile:


#7

1 0 0
0 1 1
1 1 0
in this case without swap bandwidth 2 is given.
but on (1,3) i-j=2 and aij=0 but k value will less than 2 ,
but on lower value of k doesnot satisfy the condition ,so how bandwidth 2 came ? (without swaping)


#8

@shashankj Consider the given condition |i-j| > k .


#9

I observed a pattern on bandwidth .
First I’m counting number of zeroes,

  • Let’s take k be the possible minimum
    bandwidth. Initially k=0. Then for
    all i=n to 1, (each iteration k will
    be incremented by 1, so maximum
    possible value of bandwidth is n-1) :

    I’m checking if no of zeroes in the
    matrix is >= i**(i-1) or not.If it’s
    then k is the minimum possible bandwidth. (Because minimum i **(i-1) zeros are required in order to get a bandwidth of k)

  • for example, if the size of matrix is 5x5, then minimum 20 (5 * 4) zeroes are required to get a bandwidth of zero, 12(4 * 3) zeroes are required to get a bandwidth of 1, 3 * 2=6 zeroes are required to get a bandwidth of 2 … and so on…

This is my solution.
Click Here


#10

when max diff can be 2 . and k value will be less than 2 according to condition |i-j|>k . so how it is possible?


#11

I solved the problem with O(n) time complexity and O(1) space complexity.
link - https://www.codechef.com/viewsolution/13150961


#12

please can anybody tell me how to find bandwith of matrix ??


#13

this simply means that 0’s should be filled in the matrix away from the main diagonal (where i = j) ie toward upper-right triangle or bottom-left triangle.


#14

I have a doubt, how is the bandwidth of previous matrix = 2. According to the condition, k > |i-j| but a*[j] should also be 0. But here a[3][1] is not 0.


#15

You got the definition wrong. The bandwidth isn’t equal to the maximum value of |i-j| for i and j satisfying some conditions. It’s the smallest non-negative k for which some condition holds for all pairs (i, j).


#16

Yes, I got it now. The condition that a*[j] should be 0 was confusing me…


#17

the editorials are not clear, can anyone tell me fact (actually what is happening, not any kind of trick :XD).