PROBLEM LINK:
Author: Roman Rubanenko
Tester: Tuan Anh
Editorialist: Florin Chirica
DIFFICULTY:
easy
PREREQUISITES:
simple math
PROBLEM:
We take, for each column, exactly one element and multiply what we’ve got. Output the sum of all possible choices.
QUICK EXPLANATION:
One can notice that answer is col[1] * col[2] * … * col[m], where col[x] = sum of all elements from column x.
EXPLANATION:
Let’s learn from an example
Usually, when you don’t know what to do, a good idea is to take an example to feel better the problem. So, let’s take
n = 3 m = 3 and matrix
1 2 3
4 5 6
7 8 9
By now, let’s focus on sums which must contain cells 1 and 2. This is 1 * 2 * 3 + 1 * 2 * 6 + 1 * 2 * 9 = 1 * 2 * (3 + 6 + 9).
Let’s focus now on those having cells 1 and 5. By the same logic, we get 1 * 5 * 3 + 1 * 5 * 6 + 1 * 5 * 9 = 1 * 5 * (3 + 6 + 9).
Finally, considering sums containing cells 1 and 8. We get 1 * 8 * (3 + 6 + 9).
Let’s sum up this. We get (3 + 6 + 9) * (1 * 2 + 1 * 5 + 1 * 8) = (3 + 6 + 9) * 1 * (2 + 5 + 8). It seems to smell like a pattern, isn’t it?
Let’s consider sums which containg 4. We get (after some calculations) value 4 * (2 + 5 + 8) * (3 + 6 + 9).
We do the same for cells containing 7. We get 7 * (2 + 5 + 8) * (3 + 6 + 9).
Now, we add all sums containing either 1, 4 or 7 and two other elements from column two and three. These are all possible sum.
Let’s add. We get 1 * (2 + 5 + 8) * (3 + 6 + 9) + 4 * (2 + 5 + 8) * (3 + 6 + 9) + 7 * (2 + 5 + 8) * (3 + 6 + 9) = (1 + 4 + 7) * (2 + 5 + 8) * (3 + 6 + 9).
Now we really got a pattern. Let col[j] = sum of all elements from column j. It turns out the answer is col[1] * col[2] * … * col[m].
Proof
We’ve made an assumption. Let’s try to proof it. If we can do this, we’re done.
The problem goes as following: for each column j, we choose 1 element from a[1][j], a[2][j], … a[n][j]. We multiplicate them, then we do the sum.
Let’s see what happens when we do (a[1][1] + a[2][1] + … + a[n][1]) * (a[1][2] + a[2][2] + … + a[n][2]) * … * (a[1][m] + a[2][m] + … + a[n][m]).
If we expand the expression, at each step exactly one element will be chosen from each bracket. This is correct, it’s equivalent to choosing one element
from each column. The corresponding terms will be multiplied, and then these results will be added. This is exactly what problem asks us for, so we’re done.
AUTHOR’S AND TESTER’S SOLUTIONS:
To be updated soon
Author’s solution to be updated soon
Tester’s solution