why is linux killing my code when the input size is larger?

  c++, linux

I’m dealing with an algorithm homework which need to be executable on linux(I’m using wsl), and this homework need to store the solution and export to the output file.

To store the solution, I need to open an 2D array of "vectors storing pairs", and at the end, I need to sort the pairs by its first component in the ascending order.

I know that for the first requirement, the running time would be O(N^2)(This is also the standard answer for this dynamic programming problem), and for the second one, I’ve google C++ STL, and it says that the algorithm used by c++ only needs O(NlogN).

So, I write the following code. When the input file size is 1000, it works properly and efficiently; however, when the input size grows to 10000, the terminal just returned killed.

I don’t know if the following code is not efficient enough, or there’s anything that could make a mistake when the input file size grows larger.
Thanks for helping me with the question!

chord.h:

#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

class Chord {
    public:
        Chord(int);
        ~Chord();
        void setEndPoint(int, int);
        int getMaximumChords();
        void print();
        int size;
        int* data;  //stores the endpoints of the chord
        vector< pair<int, int> >** sol; //stores the solution
        int getEndPoint(int);
};

chord.cpp:

#include "chord.h"
#include <iostream>

Chord::Chord(int tmp){ //initialize all elements 0
    size = tmp;
    data = new int [size];
    sol = new vector< pair<int, int> >*[size];
    for(int i=0; i< size; i++){
        sol[i] = new vector< pair<int, int> > [size];
    }
};

Chord::~Chord(){
    delete[] data;
    for (int i=0; i<size; i++){
        delete[] sol[i];
    }
    delete[] sol;
}
void Chord::setEndPoint(int a, int b){
    data[a] = b;
    data[b] = a;
    return;
}

void Chord::print(){
    for(int i=0;i<size; i++){
        cout << data[i] << endl;
    }
    return;
}

int Chord::getEndPoint(int a){
    return data[a];
}

int Chord::getMaximumChords(){
    for(int j=1; j<size; j++){
        for(int i=j-1; i>=0; i--){
            int k = getEndPoint(j);
            if(k==i){ //case 1: ij is the chord
                sol[i][j] = {sol[i+1][j-1].begin(), sol[i+1][j-1].end()}; //make a copy
                sol[i][j].push_back(make_pair(i,j));
            }else if(k<i || k>j){ //case 2: k outside interval[i,j]
                sol[i][j] = {sol[i][j-1].begin(), sol[i][j-1].end()};
            }else{ //case 3: k inside interval[i,j]
                if (sol[i][j-1].size() > sol[i][k-1].size() + sol[k+1][j-1].size() + 1){
                    sol[i][j] = {sol[i][j-1].begin(), sol[i][j-1].end()};
                }else{
                    sol[i][j] = {sol[i][k-1].begin(), sol[i][k-1].end()};
                    sol[i][j].insert(sol[i][j].end(),sol[k+1][j-1].begin(), sol[k+1][j-1].end());
                    sol[i][j].push_back(make_pair(k,j)); 
                }
            }
        }
    }
    sort(sol[0][size-1].begin(), sol[0][size-1].end());
    return sol[0][size-1].size();
}

main.cpp

#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include "chord.h"

using namespace std;
int main(int argc, char* argv[]){
    if (argc < 3){
        printf("Please enter output file name!");
        return 0;
    }
    //import input
    fstream fi(argv[1]);
    fstream fo;
    fo.open(argv[2], ios::out);
    int N=0, a=0, b=0;
    char buffer[200];
    fi >> N;
    Chord chord(N);
    while(fi>> a >>b){
        chord.setEndPoint(a,b);
    }
    //chord.print();
    int ans= chord.getMaximumChords();

    //export output
    fo << ans <<endl;
    for(int i=0; i<chord.sol[0][chord.size-1].size(); i++){
        fo << chord.sol[0][chord.size-1][i].first << " " << chord.sol[0][chord.size-1][i].second << endl;
    }
    fi.close();
    fo.close();
    return 0;
}

Source: Windows Questions C++

LEAVE A COMMENT