PROBLEM LINK:
Author: Sunny Aggarwal
Tester: Vasya Antoniuk
Editorialist: Pushkar Mishra
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Ad Hoc, Greedy
PROBLEM:
Given are N arrays L_1, L_2, …, L_N containing integers. An N dimensional matrix M is constructed out of these arrays in the manner: M[i_1][i_2][i_3]...[i_N] = L_1[i_1]*L_2[i_2]*...*L_N[i_N]. Find the maximum-sum submatrix of this matrix and also the number of submatrices having the maximum-sum.
EXPLANATION:
Let’s go step wise in approaching this question. The first thing to consider is that we need to consider submatrices of an N dimensional matrix. In most ad hoc problems, the way to approach is to first find out how to approach the given data. We must introduce some ordering in which the input needs to be worked upon. In this problem, we first need to figure out how to tell whether certain elements form a submatrix or not. A submatrix is a contiguous part of the matrix. This implies that we need to somehow find a way to determine whether two elements M[a_1][b_1][c_1]...[] and M[a_2][b_2][c_2]...[] are adjacent or not. Observation tells us that they will be adjacent if and only if \mid a_1-a_2 \mid + \mid b_1-b_2 \mid + \mid c_1-c_2 \mid + ... \leq 1. In words, this means that the the points are adjacent if and only if they differ in one coordinate by 1 unit.
There is a very crucial observation to make here. What does the above observation regarding adjacent elements tell us about identifying a submatrix from the given input? It tells us that a submatrix will be a set of elements such that their coordinates along the first dimension form a contiguous range in the array L_1. To be more clear, let’s say M[a_1]...[], M[a_2]...[], M[a_3]...[], …, M[a_p]...[] for p \leq N are elements forming a submatrix, then the elements L_1[a_1], L_1[a_2], L_1[a_3], …, L_1[a_p] for a subarray of array L_1. Similarly, the coordinates along second dimension form a subarray in array L_2, and so on. This is a very important observation. It introduces some order in this ad hoc problem. It tells us that we only need to consider elements forming subarrays in the given L arrays.
Now, can we find a mathematical formula for calculating the sum of numbers in a submatrix? Let’s resort to taking an example and trying to figure out a formula. Let us say we have N = 3. Also, let L_1 = {a, b, x}, L_2 = {c, d, y} and L_3 = {e, f, z}. Now, what is the sum of elements in the subarray bounded by elements M[1][1][1], M[2][2][2]? It is S = (ace + acf + ade + adf + bce + bcf + bde + bdf). Let’s simplify this further:
S = a(ce + cf + de + df) + b(ce + cf + de + df)
\Rightarrow S = a(c + d)(e + f) + b(c + d)(e + f)
\Rightarrow S = (a + b)(c + d)(e + f)
The last line now hints towards the formal algorithm. Since, these elements belong to a submatrix, that reiterates the fact that a, b forms a subarray of L_1, c, d forms a subarray of L_2 and so on. Therefore, (a+b) is subarray sum. So are (c+d) and (e+f). To maximise S over all submatrices of M, we need to maximise the subarray sums we take from each of the L arrays. There can be another way by which we can maximise S. By minimising the subarray sums. Why? Because L arrays can contain negative numbers and if the overall subarray sum that we take is negative, then it can be multiplied with another negative sum from some other L subarray to give positive overall. Why do we need to worry about only the maximum subarray sum and minimum subarray sum. The answer lies in greedy algorithm and exchange argument. If we have to take a positive sum from a subarray, the exchange argument says that we can always maximise S by taking the maximum subarray sum rather than any other positive sum. Similarly, if we have to take a negative number, we can take the minimum subarray sum.
This gives us the formal algorithm:
-
For each of the L arrays, i.e., L_1, L_2, L_3, …, L_N, calculate the maximum sum subarray and the minimum sum subarray and the number of subarrays having the the maximum sum and the minimum sum. Let’s denote maximum sum by low\_high[i][1], minimum sum by low\_high[i][0], and number of subarrays with maximum and minimum sum with cnt_sum[i][1] and cnt_sum[i][0] respectively (i denotes data for L_i). Since L_i can have at most 9 elements, we can calculate all of this using naive \mathcal{O}(N^2) algorithm, i.e., iterating over all subarrays.
-
For each of the L_i, we store two more quantities. We store the number of subarrays which have sum 0 in z\_nz[0] and the number of subarrays which have non-zero sum in z\_nz[1]. We will see later in this editorial why we need these two quantities.
-
For a particular L_i, how can we decide which one of the two options low\_cost[i][1] and low\_cost[i][0] to take in the product S in order to maximise S? Well, we can simply try all the 2^N possible products and take the maximum over them as the answer. Since N can be 9 at maximum, this algorithm is perfect. While calculating S for a particular way out of the 2^N ways, we can use the cnt\_sum array to calculate the number of submatrices which have the same S. If two different ways achieve the maximum S, we can simply add the number of submatrices we calculated from cnt\_sum.
Here is the pseudocode of the algorithm:
//Precomputation part:
low_high[i][1] = maximum subarray sum for the array L_i;
low_high[i][0] = minimum subarray sum for the array L_i;
cnt_sum[i][1] = number of subarrays of L_i having the maximum sum low_high[i][1];
cnt_sum[i][0] = number of subarrays of L_i having the minimum sum low_high[i][0];
z_nz[i][1] = number of subarrays of L_i having non-zero sum;
z_nz[i][0] = number of subarrays of L_i having sum 0;
//Main algorithm
Int_64 S = Negative Infinity; //the variable to be maximised.
int number_of_submatrices = 0; //Number of submatrices having sum S;
for(bitmask = 0 to 2^N-1)
{
long long temp_S = 1;
long long temp_cnt = 1;
for(j = 0 to N-1)
{
if(jth bit in bitmask == true)
temp_S *= low_high[j][1],
temp_cnt *= cnt_sum[j][1];
else
temp_S *= low_high[j][0],
temp_cnt *= cnt_sum[j][0];
}
if(temp_S > S)
S = temp_S, number_of_submatrices = temp_cnt;
else if(temp_S == S)
number_of_submatrices += temp_cnt;
}
output (S and number_of_submatrices);
An important logical detail to note in the algorithm is what happens if for a particular array L_i, low\_high[i][1] and low\_high[i][0] are equal. If we simply run the pseudocode above, we will end up double counting the number of submatrices having the maximum sum. Thus, if low\_cost[i][1] == low\_cost[i][0] for some L_i, then we set cnt\_sum[i][0] = 0 (note, we could have set cnt\_sum[i][1] to 0. It doesn’t matter as long as one is set to 0 to eliminate double counting).
One last part is left. What if S comes out to be 0. In that case, There are many more subarrays having sum 0 than the above algorithm counts. Why? Because we can take any zero sum subarray of a particular L_i and the non-zero subarrays of the other L arrays and the eventual S would be 0. We can take zero sum for x out of the N L arrays and non-zero sums for the remaining N-x. So many more ways than what our previous algorithm counted. Thus, in case of S = 0, we have to recount the number of submatrices in the following manner:
number_of_submatrices = 0; //reset the count to 0
for(bitmask = 1 to 2^N-1)
{
long long temp_cnt = 1;
for(j = 0 to N-1)
{
//Deciding whether to take non-zero or zero part of jth L array.
if(jth bit in bitmask == true)
tmp_cnt *= z_nz[j][1];
else
tmp_cnt *= z_nz[j][0];
}
number_of_submatrices += temp_cnt;
}
output (S and number_of_submatrices);
That completes the algorithm. The editorialist’s solution mirrors the editorial. Please refer to it for implementation details.
COMPLEXITY:
\mathcal{O}(2^N) per test case.