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
This question is marked "community wiki".
asked 22 Dec '14, 00:23

Didn't expected Matrix to have negative numbers, got WA during contest submitted the same code by just adding "if(sum<0) sum += mod" and got AC. Needed careful attention, nicely set problem statement by the setter than the problem itself, though a little hint could have been found in output description. answered 22 Dec '14, 01:03

Source Code for Implementation of above Problem in 30 Lines of code Explanation We basically want to find a path that starts from a[i][0] and ends at a[iDash][m1], where i,iDash ∈[0,n) . Now to complete the path, we would have a total of m points. As we traverse our path, jth (i.e column) index increases from 0 to m1. For every j (i.e column) we have a point P>a[i][j] such that i∈[0,n) . So, in all, we would be having pow(n,m) paths. For each path we need to calculate the product of its points, and then add the result for various paths. For some random path, let us be at point P>a[i][j] and variable prod be the product of points covered till now. We now have to go to next point Q>a[iDash][j+1], where iDash ∈ [0,n). So we have n ways to do so. So we use a recursive function that takes all possible values of iDash, and for each value taken, updates our product variable prod, and takes to next column. After reaching (m1)th column, we have completed a path, and ready to repeat the problem for next path. answered 22 Dec '14, 00:44
Your solution would give TLE. Complexity = order of (pow(n,m)). And also you have not considered that A[i][j] can be negative.
(01 Mar '15, 01:09)

Why do we need long long for the variable to store the answer.. we are doing mod in every step right... then why is long not suffecient?? getting ac with long long, but wa using long.. pls explain answered 22 Dec '14, 01:34

for those who need a simple implementation here is link to my solution.. answered 22 Dec '14, 00:59

I think math symbols used in problem statement sometimes cause confusion and wastes time to interpret. I would suggest adding latex style formulas or expressions. For example mathjax allows to add math formulas in latex style: http://docs.mathjax.org/en/latest/start.html answered 22 Dec '14, 17:41
