RRMTRX2 - Editorial

PROBLEM LINK:

Practice

Contest

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

3 Likes

practice link please

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][m-1], 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 m-1. 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 (m-1)th column, we have completed a path, and ready to repeat the problem for next path.

2 Likes

for those who need a simple implementation here is link to my solution…

http://www.codechef.com/viewsolution/5629656

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.

3 Likes

http://www.codechef.com/viewsolution/5633010

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

1 Like

Hello,

I got the logic in like 2 minutes.
But, I still could not understand the play of mod here. Why do we need to take mod at every step. won’t that affect the correct answer. E.g. If I do this without mod and say my final answer is 10000009. So, what I thought is to put 2 as answer i.e. 10000009 % 10000007 = 2.
It was my mistake that I did not consider any negative number scenario. But, still its not clear.

Regards.

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

How can one figure that negative numbers can create a problem…

Actually i still didn’t got the role of negative numbers in this problem… Can anyone please explain??

Please…

can anyone explain this test case

2 2
1 3
3 4

output comes 28 according to above theory .
But the only possible vector seems to be [1,1] .
May be i have not understood something. Please Clarify

1 Like

in programming languages, the ‘%’ operator gives a negative integer or 0 as result. Try outputting (-5%3) in your compiler. However, this may result in incorrect answer if a negative number arises in intermediate steps. Hence instead of, say x%mod, we do (x%mod+mod)%mod…

okay i am sorry i was not clear with my question…

Actually in short i didn’t understood the output for this problem clearly…

I mean when we are adding all the numbers of columns and then multiplying them, so how do negative numbers come into existence…?

The final answer is too big to print, or store in a long long variable for that matter. So they ask you to print answer % mod. And no, it won’t affect your answer as modulus is distributive. (a+b) % c = a%c + b%c (you gotta take mod again if the sum exceeds c of course)

It is the same as in example test case:

All possible vectors are {(1, 1), (1, 2), (2, 1), (2, 2)}

Your solution would give TLE. Complexity = order of (pow(n,m)). And also you have not considered that A[i][j] can be negative.