You are not logged in. Please login at www.codechef.com to post your questions!

×

RRMTRX2 - Editorial

1
1

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

This question is marked "community wiki".

asked 22 Dec '14, 00:23

elfus's gravatar image

3★elfus ♦♦
0112527
accept rate: 0%

edited 22 Dec '14, 01:15

admin's gravatar image

0★admin ♦♦
19.8k350498541


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.

link

answered 22 Dec '14, 01:03

saurabhsuniljain's gravatar image

2★saurabhsuniljain
8115
accept rate: 0%

edited 22 Dec '14, 01:11

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.

link

answered 22 Dec '14, 00:44

rachitjain's gravatar image

5★rachitjain
1307
accept rate: 0%

edited 22 Dec '14, 20:06

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) shivam2174★

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

link

answered 22 Dec '14, 01:34

king_of_hacker's gravatar image

3★king_of_hacker
204312
accept rate: 7%

practice link please

link

answered 22 Dec '14, 00:24

chashmeetsingh's gravatar image

3★chashmeetsingh
521210
accept rate: 7%

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

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

link

answered 22 Dec '14, 00:59

ma5termind's gravatar image

3★ma5termind
1.7k11730
accept rate: 11%

link

answered 22 Dec '14, 01:33

naveenkumarph's gravatar image

3★naveenkumarph
11
accept rate: 0%

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.

link

answered 22 Dec '14, 10:05

sagark3592's gravatar image

2★sagark3592
1
accept rate: 0%

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)

(29 Dec '14, 16:42) rushilpaul4★

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

link

answered 22 Dec '14, 17:41

big_boss's gravatar image

3★big_boss
111
accept rate: 0%

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..

link

answered 23 Dec '14, 02:40

rishabhprsd7's gravatar image

2★rishabhprsd7
1.9k11243
accept rate: 14%

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...

(23 Dec '14, 11:58) gvaibhav217★

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..?

(23 Dec '14, 16:03) rishabhprsd72★

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

link

answered 24 Dec '14, 00:39

inishona_29's gravatar image

2★inishona_29
11
accept rate: 0%

edited 29 Dec '14, 16:47

betlista's gravatar image

3★betlista ♦♦
16.9k49115225

It is the same as in example test case:

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

(29 Dec '14, 16:48) betlista ♦♦3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×3,820
×281
×82

question asked: 22 Dec '14, 00:23

question was seen: 3,621 times

last updated: 01 Mar '15, 01:09