1

I am doing a hackerrank challenge called gridland metro and I have been toiling away at this for hours with no success. Basically I have looked at the editors solution and compared to my code and figured that the only substantial difference between our code is that the accepted solution does not pass this array "track" to a function, which I do. Here's the code.

#include <bits/stdc++.h>

using namespace std;

int gridlandMetro(int n, int m, int k, map<int,int> mp, vector< pair<int,int> > track) {
    long long total, non_emp, temp;
    int sz1,sz2;
    sz1 = mp.size();
    for(int i=0;i<sz1;i++){
        sort(track[i].begin(),track[i].end());
    }
    total = (long long)n*(long long)m;
    non_emp = 0;
    for(int i=0,p;i<sz1;i++){
        p = 0;
        sz2 = track[i].size();
        for(int j=0;j<sz2;j++){
            if(track[i][j].first <= p){
                temp = track[i][j].second - p;
                if(temp>0){
                    non_emp += temp;
                }
            }else{
                non_emp += (track[i][j].second - track[i][j].first + 1);
            }
            p = max(p,track[i][j].second);
        }
    }
    return total-non_emp;
}

vector< pair<int,int> > track[1003];
map<int,int>mp;

int main() {
    int n,m,k,r,c1,c2;
    cin >> n >> m >> k;
    for(int track_i = 0;track_i < k;track_i++){
        cin >> r >> c1 >> c2;
        if(mp.find(r) == mp.end()){
            mp[r] = mp.size();
        }
        r = mp[r];
        track[r].push_back(make_pair(c1,c2));
    }
    int result = gridlandMetro(n, m, k, mp, track);
    cout << result << endl;
    return 0;
}

It works on low inputs, but on large inputs it fails. I have tried passing the vector as a pointer, which seems to be what people suggest when passing arrays to functions. However this hasn't worked. I'll put the description of the challenge here but I don't think it's totally necessary.

The city of Gridland is represented as an matrix where the rows are numbered from to and the columns are numbered from to .

Gridland has a network of train tracks that always run in straight horizontal lines along a row. In other words, the start and end points of a train track are and , where represents the row number, represents the starting column, and represents the ending column of the train track.

The mayor of Gridland is surveying the city to determine the number of locations where lampposts can be placed. A lamppost can be placed in any cell that is not occupied by a train track.

Given a map of Gridland and its train tracks, find and print the number of cells where the mayor can place lampposts.

Note: A train track may (or may not) overlap other train tracks within the same row.

Input Format

The first line contains three space-separated integers describing the respective values of (the number of rows), (the number of columns), and (the number of train tracks). Each line of the subsequent lines contains three space-separated integers describing the respective values of , , and that define a train track.

Constraints

Output Format

Print a single integer denoting the number of cells where the mayor can install lampposts.

Davis Owen
  • 57
  • 1
  • 9
  • 2
    What is the input it is failing on? Have you run it in a debugger to see where the problem is? Is the failure a crash, the wrong answers, etc.? Are you sure this is your actual code, because this doesn't compile. – Retired Ninja Mar 09 '18 at 03:01
  • 1
    You do not really need to pass `track` to your `gridlandMetro` function since you've declared `vector< pair > track[1003];` in a global scope. What is the problem/error that you're facing? – Suhaib Ahmad Mar 09 '18 at 03:14
  • I'm running it in the hackerrank IDE environment I haven't compiled it locally. The failure is a wrong answer, not a crash. I guess I could try running it locally and use gdb. However any insights into the behavior of arrays being passed to functions would be good to know because it's weird that it works on small inputs but fails on larger inputs. – Davis Owen Mar 09 '18 at 03:16
  • @SuhaibAhmad Interesting I just realized that and didn't pass them as arguments to the function but it still didn't work unfortunately. I'm gonna compile it locally and try to find the problem – Davis Owen Mar 09 '18 at 03:20
  • 1
    if you are going to run it locally, run it in a debugger as @RetiredNinja also suggested. And what do you mean "it works on small inputs but fails on larger inputs"? If you are referring to the value are you sure that your `long long` cast to `int` is correct? A debugger can help in this – Suhaib Ahmad Mar 09 '18 at 03:30
  • @SuhaibAhmad I have found the problem. My vectors of pairs are not being sorted when I run sort() in line 10. Why is this? Is it because the array is simply being passed as a pointer? How should I handle this? I am relatively new to c++ and pointers. – Davis Owen Mar 09 '18 at 04:07
  • So, you can consider your `track` vector to be like a 2-dimensional array, i.e. n-by-2 array. The way you are using `sort` in your code is as if `track` is one dimensional, have a look at this link on it. http://www.cplusplus.com/reference/algorithm/sort/ However, since your vector is of pairs, you have to specify what value are you sorting it on - 1st element of the pair, the 2nd element, or other criteria? Have a look at this SO link which mentions how you can sort pairs: https://stackoverflow.com/questions/18112773/sorting-a-vector-of-pairs – Suhaib Ahmad Mar 09 '18 at 04:58
  • Try passing the containers (vectors or maps) by `const` reference, rather than passing them by value. And, instead of an array of `1003` vectors, why not use a container (`std::array`, `std::vector`, etc)? – Peter Mar 09 '18 at 05:09

2 Answers2

2

You are using std::vector, std::pair and std::map already, so why not std::array aswell.

#include <array>

array<vector< pair<int,int> >, 1003> track;

int gridlandMetro(int n, int m, int k, map<int,int> mp, array<vector< pair<int,int> >, 1003>& track) {
    //...
}
super
  • 12,335
  • 2
  • 19
  • 29
0

So I'm stupid and it was just because my function was returning int instead of long long. Woops

Davis Owen
  • 57
  • 1
  • 9