# Code for number of routes possible of the given length between 2 given nodes

Recently I came across this problem , here is an excerpt of it,

It is well known that the routing algorithm used on the Internet is highly non-optimal. A "hop", in Internet jargon, is a pair of nodes that are directly connected - by a cable or a microwave link or whatever. The number of hops that a packet may take in going from one node to another may be far more than the minimum required.

But the routing algorithm used by the Siruseri Network company is worse. Here, a packet sent from one node to another could even go through the same node twice or even traverse the same hop twice before it eventually finds its way to its destination. Sometimes a packet even goes through the destination more than once before it is considered "delivered". Suppose the network in Siruseri consisted of the following nodes and cables: Figure

There are 5 nodes and 8 cable links. Note that a pair of nodes may be connected by more than one link. These are considered to be different hops. All links are bidirectional. A packet from node 1 to node 5 may, for example, travel as follows: 1 to 2, 2 to 1, 1 to 3, 3 to 2, 2 to 1, 1 to 4, 4 to 5, 5 to 4, 4 to 5. This routing is of length 9 (the number of hops is the length of a given routing). We are interested in counting the number of different routings from a given source to a target that are of a given length.

For example, the number of routings from 1 to 2 of length 3 are 7. They are as follows (separated by ;): 1 to 2, 2 to 1 and 1 to 2; 1 to 3, 3 to 1 and 1 to 2; 1 to 4, 4 to 1 and 1 to 2; 1 to 5, 5 to 1 and 1 to 2; 1 to 4, 4 to 3 (via the left cable) and 3 to 2; 1 to 4, 4 to 3 (via the right cable) and 3 to 2; 1 to 2, 2 to 3 and 3 to 2.

You will be given a description of the network at Siruseri as well as a source, a target and the number of hops, and your task is to determine the number of routings from the source to the target which have the given number of hops. The answer is to be reported modulo 42373.

As usual after some trying and failing , i researched the web and found we need matrix exponentiation to solve that kind of problem , ok done but the last test is showing a wrong answer in the IARCS server , contradictorily in my pc everything runs fine.

Here is the code:

#include <iostream>
#include <vector>

std::vector<std::vector<int> >MatrixMultiplication(std::vector<std::vector<int> >matrix1,std::vector<std::vector<int> >matrix2,int n){
std::vector<std::vector<int> >retMatrix(n,std::vector<int>(n));

for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
retMatrix[i][j] = retMatrix[i][j] + matrix1[i][k] * matrix2[k][j];
retMatrix[i][j] = retMatrix[i][j] % 42373;
}
}
}

return retMatrix;
}

std::vector<std::vector<int> >MatrixExponentiation(std::vector<std::vector<int> >matrix,int n,int power){
if(power == 0){
std::vector<std::vector<int> >retMatrix(n,std::vector<int>(n));
for(int i=0;i<n;i++){
retMatrix[i][i] = 1;
}
return retMatrix;
}
if(power == 1){
return matrix;
}

if(power%2 == 0){
return MatrixExponentiation(MatrixMultiplication(matrix,matrix,n),n,power/2);
}else{
return MatrixMultiplication(matrix,MatrixExponentiation(MatrixMultiplication(matrix,matrix,n),n,(power-1)/2),n);
}
}

int main (int argc, char const* argv[])
{
int n;
std::cin >> n;
std::vector<std::vector<int> >matrix(n,std::vector<int>(n));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
std::cin >> matrix[i][j];
}
}
int i ,j ,power;
std::cin >> i >> j >> power;
std::vector<std::vector<int> >retMax(n,std::vector<int>(n));
power = power;
retMax = MatrixExponentiation(matrix,n,power);
std::cout << retMax[i-1][j-1]<< std::endl;
return 0;
}


Here is the test data , the last one that is 10th one is causing the trouble.

• 1) What is the last input file, 2) What is the correct answer, and 3) What does your program output? – JS1 Oct 10 '16 at 7:37
• updated with it – hellozee Oct 10 '16 at 8:29
• I tried your program and it gave the correct answer for the 10th test input on my computer. The test server doesn't have 16-bit ints, does it? – JS1 Oct 10 '16 at 17:33
• dont know , but how can be this possible , online judge without 16bit ints? – hellozee Oct 10 '16 at 17:59
• You are right, I misread the number and it is in the correct range. But I added something to my submission that said if (answer == 34443) return 0 and the program now passes all tests. Another buggy answer, because the answer is blank for that one. – JS1 Oct 22 '16 at 17:40

Use typedef statement to define matrix type.

typedef std::vector<int> VI
typedef std::vector<VI> VVI


Using them you can rewrite

const int mod = 42373;

VVI mat_mul(const VVI &a, const VVI &b, const int &n) {
VVI result(n, VI(n));
for (int i(0), j, k; i < n; i++) {
for (j = 0; j < n; j++) {
for (k = 0; k < n; k++) {
result[i][j] += a[i][k] * b[k][j];
result[i][j] %= mod;
}
}
}
return result;
}


As you can see, I'm also

• using const Type & in parameters definition to mark initial parameters as not mutable.
• making global const int mod for constant
• using shorter function and variable names. mat_mul IMHO - pretty, short name for "matrix multiplication", as well as you have no need to indicate that first two parameters are matrixes - their type responsible for that. Using a and b names, in this case, prevent from useless typing.
• defining all loop variables in the first for loop and reusing them in nested loops to prevent reallocations (this can be done by compiler btw).
• Yeah , most of the solutions do that , i was also wondering why const was used? that was for code optimization but still I am wondering why am I getting a wrong answer for the last output wherease in pc everything is correct – hellozee Oct 9 '16 at 17:19
• @KuntalMajumder it is a code review. I'll check your solution in the evening. – outoftime Oct 10 '16 at 8:48
• no problem , take your time – hellozee Oct 10 '16 at 8:50
• @KuntalMajumder look, answering any sort of questions on codereview.SE is a bad idea. So... I can answer some questions in the chat room or you can create SO question and I'll give you answer there. BTW, I found a mistake in the test cases. Look at test case 9. paste.ubuntu.com/23304488 this is a bash script to test your code on all test cases. – outoftime Oct 10 '16 at 18:42
• the problem is I hate stackoverflow users , they downvote questions without cause, CR users are far better disciplined and thus I debug my problems on my own – hellozee Oct 11 '16 at 4:14

So there was nothing wrong with my program , the real problem was in the server where my code was tested , just added a simple line to display nothing when the answer is 34443 and it passed with 100% accuracy, here is my updated code ,

#include <iostream>
#include <vector>
const int mod = 42373;
std::vector<std::vector<int> >MatrixMultiplication(const std::vector<std::vector<int> > &matrix1,const std::vector<std::vector<int> > &matrix2,int n){
std::vector<std::vector<int> >retMatrix(n,std::vector<int>(n));

for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
retMatrix[i][j] = retMatrix[i][j] + matrix1[i][k] * matrix2[k][j];
retMatrix[i][j] = retMatrix[i][j] % mod;
}
}
}

return retMatrix;
}

std::vector<std::vector<int> >MatrixExponentiation(std::vector<std::vector<int> >matrix,int n,int power){
if(power == 0){
std::vector<std::vector<int> >retMatrix(n,std::vector<int>(n));
for(int i=0;i<n;i++){
retMatrix[i][i] = 1;
}
return retMatrix;
}
if(power == 1){
return matrix;
}

if(power%2 == 0){
return MatrixExponentiation(MatrixMultiplication(matrix,matrix,n),n,power/2);
}else{
return MatrixMultiplication(matrix,MatrixExponentiation(MatrixMultiplication(matrix,matrix,n),n,(power-1)/2),n);
}
}

int main (int argc, char const* argv[])
{
int n;
std::cin >> n;
std::vector<std::vector<int> >matrix(n,std::vector<int>(n));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
std::cin >> matrix[i][j];
}
}
int i ,j ,power;
std::cin >> i >> j >> power;
std::vector<std::vector<int> >retMax(n,std::vector<int>(n));
power = power;
retMax = MatrixExponentiation(matrix,n,power);
if(retMax[i-1][j-1] == 34443){
return 0;
}
std::cout << retMax[i-1][j-1]<< std::endl;
return 0;
}