segmentation fault on "End Of Fun" problem on SPOJ

[amiable143]

I was solving End Of Fun on SPOJ. Everything is working fine for values of N smaller than 10,but for N > 10 it's giving segmentation fault.I wasted my whole day finding the bug,but i failed.I think, i have used proper integral types according to question everywhere,still facing issues.

#include<bits/stdc++.h>
using namespace std;

void Takeinput(vector<vector<int> > &arr,int N){
     for(int i=0;i<N;i++){
         vector<int> row;
         for(int j=0 ;j<N;j++){
                 int  n;
                 cin>>n;
                 row.push_back(n);
            }
         arr.push_back(row);
     }
    return;}
    
long long int Sum(vector<vector<int> > arrA,vector<vector<int> > arrB)
{   long long int sum =0;
    long long int sum1=0;
    long long int sum2=0;
    int i=0;
    while(i<arrA.size()){
        for(int j=0;j<arrA.size();j++){
            sum = sum + arrA[j][i];
            sum1= sum1 + arrB[i][j];
          }
          i++;
        sum2 = sum2 + sum*sum1;
        sum1 = 0;
        sum  = 0;
    }
    return sum2;
 }
 int main(){
    int N;
    cin>>N;
    vector<vector<int> > arrA,arrB;
    Takeinput(arrA,N);
    Takeinput(arrB,N);
    unsigned int Q;
    cin >> Q;
    while(Q--){
        char ch;
         int x,y;
         long long int z;
        cin>>ch;
        cin>>x>>y>>z;
        if(ch=='A') arrA[x][y] = z;
        else arrB[x][y]= z;
        cout<<Sum(arrA,arrB)<<endl;
        }
        return 0;
    }

[Enoizat]

Everything is working fine for values of N smaller than 10
Your code doesn’t compile; I wander what a code that’s not ‘fine’ looks like…

The exercise asks for the sum of the product of the matrices:
https://www.spoj.com/problems/DCEPC12E/

the sum of the elements of the matrix A*B

I’m not good at math, but I don’t think you’re properly answering the question.

I hope this code could be useful for hints (note: I’ve kept your calculation, which is, I think, misleading).

// Input
// First line consists of N, the dimension of matrix.
// Each of the next N lines contains N space separated integers. This is matrix A.
// Each of the next N lines contains N space separated integers. This is matrix B.
// Next line contains Q, the number of queries asked by Sid.
// Each of the next Q lines consists of queries of the form
//  “A i j K” or “B i j K” (quotes for clarity), meaning 
// change the element in ith row and jth column of matrix A or B to value K.
// 
// Output
// Output exactly Q lines corresponding to Q queries, each containing the sum of
// the elements of the matrix A*B.
// 
// Example
// Input:
// 2
// 1 2
// 3 4
// 4 3
// 2 1
// 3
// A 1 1 2
// B 0 1 3
// A 0 0 10
// 
// Output:
// 40
// 40
// 103
// 
// Constraints:
// 1<=N<=100
// 1<=Q<=100000
// 0<=i,j<N
// -10^6 <= A[i][j], B[i][j] <= 10^6
#include <chrono>
#include <iomanip>      // pointless in production code
#include <iostream>
#include <random>
#include <vector>

using matrix = std::vector<std::vector<int>>;

int getRndInt(int min, int max);
int getRndChar();
matrix resizedMatrix(std::size_t size);
void fillMatrixRndInts(matrix & arr);
void printMatrix(const matrix & m);
long long int matrixSum(matrix & arrA, matrix & arrB);


int main()
{
    int N { getRndInt(2, 4) };              // constraint: 1 <= N <= 100
    std::cout << "input: " << N << '\n';
    matrix arrA { resizedMatrix(N) },
           arrB { resizedMatrix(N) };
    fillMatrixRndInts(arrA);
    fillMatrixRndInts(arrB);
    unsigned int Q = getRndInt(1, 4);       // costraint: 1 <= Q <= 100,000
    std::cout << "\nqueries: " << Q << '\n';
    while(Q--) {
        char ch = getRndChar();
        int x { getRndInt(1, N-1) },
            y { getRndInt(1, N-1) };
        long long int z { getRndInt(1, 100) };
        if(ch == 'A') { arrA[x][y] = z; }
        else          { arrB[x][y] = z; }
        std::cout << ch << ' ' << x << ' ' << y << ' ' << z
                  << " --> matrixSum(arrA, arrB): " << matrixSum(arrA, arrB) << '\n';
    }
    return 0;
}

matrix resizedMatrix(std::size_t size)
{
    matrix m(size, std::vector<int>(size));
    return m;
}

void fillMatrixRndInts(matrix & arr)
{
    for(auto& v : arr) {
        for(int& i : v) {
            i = getRndInt(1, 100); // contraint: -10^6 <= A[i][j], B[i][j] <= 10^6
        }
    }
    printMatrix(arr);
    return;
}

int getRndInt(int min, int max)
{
    static std::mt19937 eng {
        static_cast<unsigned>( std::chrono::high_resolution_clock::now()
                                .time_since_epoch()
                                .count() )
    };
    std::uniform_int_distribution<> dst(min, max);
    return dst(eng);
}

void printMatrix(const matrix & m)
{
    std::cout << "\nmatrix:\n";
    for(const auto& v : m) {
        for(const int i : v) {
            std::cout << std::setw(4) << i;     // std::cout << i << ' ';
        }
        std::cout << '\n';
    }
}

int getRndChar()
{
    static std::mt19937 eng {
        static_cast<unsigned>( std::chrono::high_resolution_clock::now()
                                .time_since_epoch()
                                .count() )
    };
    std::uniform_int_distribution<char> dst('A', 'B');
    return dst(eng);
}

long long int matrixSum(matrix & arrA, matrix & arrB)
{
    long long int sum2 = 0;

    for(size_t i=0; i < arrA.size(); ++i) {
        long long int sum  = 0;
        long long int sum1 = 0;
        for(size_t j=0; j<arrA.size(); j++) {
            sum  += arrA[j][i];
            sum1 += arrB[i][j];
        }
        sum2 += sum * sum1;
    }
    return sum2;
}

[amiable143]

I am getting correct output with my algorithm and your code for random outputs.....u didn't tell me why m i getting seg fault for my code

[Enoizat]

Since I can't execute your code, I can't reproduce your errors.

[Thomas1965]

@Enoizat,
just replace the . with a , on line 36. Then it runs on the shell.

[Enoizat]

@Thomas1965,
thank you for spotting it.

I’m not jealous and this isn’t a contest :-D
Please, fell free to give the OP the proper answer and I’ll read it to learn - btw, that’s why I’m haunting this forum.

Anyway, if I may, the OP neither spent any time to describe the exercise, nor provided a link, nor checked if their code compiled correctly, while I think in general the more you help the others to help you the better help you get. I may be wrong.
Also, if you thank the others for their help, you encourage them to help you again, don’t you?

So, thank you for your clue, but I personally consider this thread solved.

[Thomas1965]

@Enoizat,
you are very welcome.
I am quite busy at the moment so I won't look for the problem.
Normally it should be simple if you have a proper input file.
I guess the code would take you straight to the debugger. :)

[amiable143]

@Enoizat, i am extremely sorry for what i did , I am very new to this forum....and i am learning things from mentors like you..so...i will not repeat the mistake ...thanks,.... but plz help me with the problem

[jonnin]

what do you still need help with?

[Enoizat]

@amiable143,
I still can't reproduce your error. I've executed the following version several times and I've never got a segmentation fault, but it's theoretically identical to your code:

#include <chrono>
#include <iostream>
#include <random>
#include <vector>

using namespace std;


int getRndInt(int min,  int max)
{
    static std::mt19937 eng {
        static_cast<unsigned>( std::chrono::high_resolution_clock::now()
                                .time_since_epoch()
                                .count() )
    };
    std::uniform_int_distribution<> dst(min,  max);
    return dst(eng);
}


char getRndChar()
{
    static std::mt19937 eng {
        static_cast<unsigned>( std::chrono::high_resolution_clock::now()
                                .time_since_epoch()
                                .count() )
    };
    std::uniform_int_distribution<char> dst('A', 'B');
    return dst(eng);
}


void Takeinput(vector<vector<int>>& arr, int N)
{
    for(int i=0; i<N; i++){
        vector<int> row;
        for(int j=0; j<N; j++) {
            int n { getRndInt(1, 100) };
            // cin>>n;
            row.push_back(n);
        }
        arr.push_back(row);
    }
    return;
}


long long int Sum(vector<vector<int>> arrA, vector<vector<int>> arrB)
{
    long long int sum =0;
    long long int sum1=0;
    long long int sum2=0;
    int i=0;
    while(i<arrA.size()) {  // warning: comparison between signed and unsigned
                            // integer expressions
        for(int j=0;j<arrA.size();j++) {    // warning: comparison between signed
                                            // and unsigned integer expressions
            sum = sum + arrA[j][i];
            sum1= sum1 + arrB[i][j];
        }
        i++;
        sum2 = sum2 + sum * sum1;
        sum1 = 0;
        sum  = 0;
    }
    return sum2;
}


int main()
{
    int N = getRndInt(10, 14);
    // cin>>N;
    vector<vector<int>> arrA, arrB;
    Takeinput(arrA, N);
    Takeinput(arrB, N);
    unsigned int Q = getRndInt(1, 8); // narrowing conversion (int --> unsigned int)
    // cin >> Q;
    while(Q--){
        char ch { getRndChar() };
        int x { getRndInt(1, N-1) },
            y { getRndInt(1, N-1) };
        long long int z { getRndInt(1, 100) };
        // cin>>ch;
        // cin>>x>>y>>z;
        if(ch=='A') arrA[x][y] = z;
        else arrB[x][y]= z;
        cout << Sum(arrA, arrB) << endl;
    }
    return 0;
}

What tests is it supposed to undergo?

- - -
Btw, I didn't mean to rant. I just meant this is a forum fro free help; people here give help at their leisure. The more you make your question appealing, the more help you get.

[amiable143]

Take #39 and #40 as testcases..it gives segmentation fault on my program

link- http://spojtoolkit.com/history/DCEPC12E

[amiable143]

@jonnin sir, my code giving segmentation fault for larger input size as given in my last comment

[Thomas1965]

When I run your last code with the input from the website Q was not read correctly and then later of course y had an invalid valid out of range, and that coursed the crash.
Your code to read input seems correct so my guess is that maybe the website or maybe the editor add some additional line breaks.

BTW. These problems are easy to spot when you run the code in the debugger. Maybe in future posts you can provide the input from the beginning, it would have saved you some time.

[keskiverto]

Your function Sum() is very fragile, because it makes huge (and unnecessary) assumptions about its input data:

vector<vector<int>> arrA;
vector<vector<int>> arrB;
size_t row=0;
while ( row < arrA.size() ) {
  for ( size_t col=0; col < arrA.size(); col++ ) {
    arrA[row][col];
    arrB[col][row];
  }
  row++;
}

Every arrA[row] is a vector<int> object.
However, the inner loop does not iterate over arrA[row].size() elements.

In other words, the nested loop is safe only if in the actual data
arrA.size() <= arrA[row].size() is true for each row.


Furthermore, you do access arrB[row][col] in that loop.
That is safe only if arrB is at least as big as arrA.



The std::vector has two element access methods: operator[] and function at().
arrA[row][col] yields the same element as arrA.at(row).at(col), but the at() will throw exception rather than silently allow out-of-range indices (which may lead to a crash later).

[amiable143]

@keskiverto
Sir, According to the question,as the matrices are square matrix...
i) arrA.size() = arrA[row].size() in all cases.
ii) arrA has same dimension as arrB .

[jonnin]

what input is crashing it?
do you know where it crashes?
is there *any* chance you ran out of memory somewhere, and a push-back failed or something leading to invalid [] access leading to a seg fault??

[amiable143]

Take #39 and #40 and for n>10 , testcases..it gives segmentation fault on my program

link- http://spojtoolkit.com/history/DCEPC12E
Thanks...