Segmentation fault when using large number of input data in C++

Question

I would like to know the reason behind my code not working in case of large no. of input. Actual this is a problem from codingame.com The problem The code is working on previous test cases. But not on the last test case, where the input is large. I would like to complete the problem 100%, but i am stuck at 80% with the last test case.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <iterator>
#include <cmath>

using namespace std;
int ventarr[1024][1024];

void add_edge(int u, int v,int N) {
    for(int i =0;i<N;i++){
        if(ventarr[u][i] != 0){
            continue;
        }
        else{
            ventarr[u][i] = v;
            break;
        }
    }
}

int main()
{
    map<pair<char,char>,char> rules;
    map<int,int> matrix_player_id;
    map<int,int>:: iterator matrix_player_id_itr;
    vector<int>::iterator player_id_itr;
    vector<char>::iterator player_sign_itr;
    map<pair<char, char>, char>::iterator rules_itr;
    char R,P,C,L,S;
    int key_winner = -1;
    int key_loser = -1;
    int key_final = -1;

    rules.insert(make_pair(make_pair('C', 'P'), 'C'));
    rules.insert(make_pair(make_pair('P', 'C'), 'C'));

    rules.insert(make_pair(make_pair('P', 'R'), 'P'));
    rules.insert(make_pair(make_pair('R', 'P'), 'P'));

    rules.insert(make_pair(make_pair('R', 'L'), 'R'));
    rules.insert(make_pair(make_pair('L', 'R'), 'R'));

    rules.insert(make_pair(make_pair('L', 'S'), 'L'));
    rules.insert(make_pair(make_pair('S', 'L'), 'L'));

    rules.insert(make_pair(make_pair('S', 'C'), 'S'));
    rules.insert(make_pair(make_pair('C', 'S'), 'S'));

    rules.insert(make_pair(make_pair('C', 'L'), 'C'));
    rules.insert(make_pair(make_pair('C', 'C'), 'C'));

    rules.insert(make_pair(make_pair('L', 'P'), 'L'));
    rules.insert(make_pair(make_pair('P', 'L'), 'L'));

    rules.insert(make_pair(make_pair('P', 'S'), 'P'));
    rules.insert(make_pair(make_pair('S', 'P'), 'P'));

    rules.insert(make_pair(make_pair('S', 'R'), 'S'));
    rules.insert(make_pair(make_pair('R', 'S'), 'S'));

    rules.insert(make_pair(make_pair('R', 'C'), 'R'));
    rules.insert(make_pair(make_pair('C', 'R'), 'R'));

    int N;
    cin >> N; cin.ignore();
    vector<int> player_id;
    vector<char> player_sign;
    for (int i = 0; i < N; i++) {
        int NUMPLAYER;
        char SIGNPLAYER;
        cin >> NUMPLAYER >> SIGNPLAYER; cin.ignore();
        player_id.push_back(NUMPLAYER);
        player_sign.push_back(SIGNPLAYER);
        matrix_player_id.insert(pair<int, int>(i,NUMPLAYER));
    }
    /*copy(player_id.begin(), player_id.end(), ostream_iterator<int>(std::cout, " "));
    cout << endl;
    copy(player_sign.begin(), player_sign.end(), ostream_iterator<char>(std::cout, " "));*/
    /*for (matrix_player_id_itr = matrix_player_id.begin(); matrix_player_id_itr != matrix_player_id.end(); ++matrix_player_id_itr) { 
        cout << matrix_player_id_itr->first
             << '\t' << matrix_player_id_itr->second <<'\n'; 
    } 
    cout << endl; 
    */

    for(int i = 0; i < log10(N)/log10(2); i++){
        for(int j = 0; j < player_id.size(); j++){
            int k = j+1;
            if(player_sign[j] != player_sign[k]){
                rules_itr = rules.find(make_pair(player_sign[j],player_sign[k]));   
                if(player_sign[k] == rules_itr->second){

                    for(matrix_player_id_itr = matrix_player_id.begin(); matrix_player_id_itr != matrix_player_id.end(); ++matrix_player_id_itr)
                    {
                            if (matrix_player_id_itr->second == player_id[k])
                            {
                                key_winner = matrix_player_id_itr->first;
                                break;
                            }
                    }

                    add_edge(key_winner,player_id[j],N);

                    player_id[j] = 0;
                    player_sign[j] = '0';

                }
                if(player_sign[j] == rules_itr->second){

                    for(matrix_player_id_itr = matrix_player_id.begin(); matrix_player_id_itr != matrix_player_id.end(); ++matrix_player_id_itr)
                    {
                            if (matrix_player_id_itr->second == player_id[j])
                            {
                                key_winner = matrix_player_id_itr->first;
                                break;
                            }
                    }

                    add_edge(key_winner,player_id[k],N);

                    player_id[k] = 0;
                    player_sign[k] = '0';

                }
            }
            else{
                if(player_id[j] < player_id[k]){

                    for(matrix_player_id_itr = matrix_player_id.begin(); matrix_player_id_itr != matrix_player_id.end(); ++matrix_player_id_itr)
                    {
                            if (matrix_player_id_itr->second == player_id[j])
                            {
                                key_winner = matrix_player_id_itr->first;
                                break;
                            }
                    }

                    add_edge(key_winner,player_id[k],N);

                    player_id[k] = 0;
                    player_sign[k] = '0';
                }
                else{
                    for(matrix_player_id_itr = matrix_player_id.begin(); matrix_player_id_itr != matrix_player_id.end(); ++matrix_player_id_itr)
                    {
                            if (matrix_player_id_itr->second == player_id[k])
                            {
                                key_winner = matrix_player_id_itr->first;
                                break;
                            }
                    }

                    add_edge(key_winner,player_id[j],N);

                    player_id[j] = 0;           
                    player_sign[j] = '0';
                }
            }
            ++j;    
        }

        for(int i=0; i<player_id.size(); i++){
                player_id_itr = find(player_id.begin(), player_id.end(), 0);
                player_id.erase(player_id_itr);
                player_sign_itr = find(player_sign.begin(), player_sign.end(), '0');
                player_sign.erase(player_sign_itr);
        }
        for(int i=0; i<player_id.size(); i++){
            cout << player_id[i] << '\t' << player_sign[i] << endl;
        }
        cout << endl;
    }

    for(matrix_player_id_itr = matrix_player_id.begin(); matrix_player_id_itr != matrix_player_id.end(); ++matrix_player_id_itr)
    {
         if (matrix_player_id_itr->second == player_id.front())
         {
            key_final = matrix_player_id_itr->first;
            break;
         }
    }
    cout << player_id.front()<< endl;
    for(int i=0;i<N;i++){
        if(ventarr[key_final][i] != 0){
            if(ventarr[key_final][i+1] != 0){
                cout << ventarr[key_final][i];
                cout << " ";
            }
            else{
                 cout << ventarr[key_final][i];
            }
        }
        else{
            continue;
        }
    }

}

Answer 1

In various parts of the code you are assigning values and addressing a fixed size array ventarr with an index that can run up to an inputted number N which, as you mentioned, can be very large. If your N is larger than or equal to 1024 then add_edge will trash memory.

If you must use a fixed size array there for any reason, then you need to add an upper limit check for N. If N needs to be large up to a reasonable size, then see if you can allocate your array dynamically to that size,or increase the current maximum.

I took a look at the problem, and it has a bounds specification for N:

N is a 2^k value (2, 4, 8, 16, ..., 1024)

2 ≤ N ≤ 1024

In that case, increase your fixed array dimensions to vetarr[1025][1025] and try it again. However, you do need to make sure inputted value of N does not fall outside the specified bounds.