PROBLEM LINK:
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[i] = 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[i][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[i][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[i][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[i][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.
First tester’s solution can be found here.
Second tester’s solution can be found here.
Editorialist’s solution can be found here.
