december cook off , RRMtrx doubt

Problem link: http://www.codechef.com/problems/RRMTRX2

I am not getting the below lines of problem

Consider every possible vector v of m elements, such that every 1 ≤ vi ≤ n.
Let value of the vector be product of all Avi, i (1 ≤ i ≤ m). You are to count the sum of values over all possible vectors v.

What is vi ??and how vi changes when i changes?? How to choose Avi,i ?? Can i choose numbers from same
position multiple times??. So these things i am not getting??
I think problem is given in weird form.Plz help

1 Like

write down the sum of each columns(dont calculate the value ,just write a(i,j)+a(i+1,j)…) and multiply all the sums and see all the terms you get you will automatically understand

here vi is the ith element of a vector ‘v’. The vector consists of ‘m’ elements, each of which can be chosen from the numbers: 1,2,3…,n. Now, consider the ordered pairs: (vi,i) for all i belonging to [1,m]. This means that the ordered pairs are: (v1,1), (v2,2), (v3,3), (v4,4)… and so on. Now, the value of any vector is the product of all A(vi,i) where (vi,i) can be any of the ordered pairs described above.

Suppose, for example, the vector being considered is 1,1,1,1. Then, the value of this vector is: A(1,1)*A(1,2)*A(1,3)*A(1,4).
another example: Suppose the vector is: 1,3,4,2. Then the value of the vector is: A(1,1)*A(3,2)*A(4,3)*A(2,4).



Hope this helps :slight_smile:

2 Likes

Can you explain this with respect to the test case, please?