Hack the Interview VI (Asia Pacific)

help
, , ,
1

Question Link: Programming Problems and Competitions :: HackerRank

This was my code… it passed 10/14 test cases only and gave segmentation fault in the rest. Why is that?

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

ll i,n,m,s,q,temp;
cin >> n >> m >> s >> q;

ll ar[n]={0};

for(i=1; i<=m; i++)
{
    ll k;
    cin >> k;
    k--;
    ar[k]=1;
}

while(s--)
{
    ll s1,s2;
    cin >> s1 >> s2;
    s1--;
    s2--;
    temp=ar[s1];
    ar[s1]=ar[s2];
    ar[s2]=temp;

}

ll ar2[n]={0};
ll sum=0;
for(i=0; i<n; i++)
{
    sum += ar[i];
    ar2[i]=sum;
}


while(q--)
{
    ll q1,q2;
    cin >> q1 >> q2;
    q1--;
    q2--;

    if(q1==0)
        cout << ar2[q2] << " ";

    else
        cout << (ar2[q2]-ar2[q1-1]) << " ";  
}

return 0;

}

2

N can be up to 10^9, and I doubt Hackerrank’s Online Judge has more than 7GB of stack space :slight_smile:

5 Likes
3

Can you please explain it in a bit more details and how to resolve it? I am a noob…

4

Does that Problem not have an Editorial?

Anyway, as to why that causes a segment fault: you are creating, on the stack, an array of up to 10^9 items, each of type long long. A long long takes up 8 bytes on most machines, so this eats up 8\times 10^9 bytes of stack which is approx 7.45 GB, which is huge - far more than is available. Hence, the crash.

4 Likes
5

Thanks for the explanation :innocent: That was an useful info. I was actually trying to fix my solution without unlocking the editorial. I will go and check the editorial now… thanks.

1 Like
6

You cannot create such a large array. You need to change your approach.

Hint

Consider using a std::map.

2 Likes
8

Thanks… I will try that. I didn’t think of space consumption earlier.

9

it was a good question . had to find Fine balance between Time and Space.
i learned a lot in this question.
readibilty is not so good, if it helps u. here’s my code:

#include<bits/stdc++.h>
#define ll long long int
#include<unordered_map>
using namespace std;

int main() {
int n, m, s, q, temp, temp2;
cin >> n >> m >> s >> q;

unordered_map <int, bool> my_map;
map <ll, int> my_map2;
for (int j = 0;j < m;j++) ///taking postion of balls
{
    cin >> temp;
    my_map[temp] = true;
    my_map2[temp] = 0;
}

for (int j = 0;j < s;j++)
{
    cin >> temp >> temp2;

    if ((my_map.find(temp) == my_map.end()) || my_map[temp] == false)
    {
        if ((my_map.find(temp2) == my_map.end()) || my_map[temp2] == false)
        {
            ;
        }
        else//temp2 has ball
        {
            my_map[temp] = true;
            my_map2.insert(make_pair(temp, 0));
            my_map[temp2] = false;
            my_map2.erase(temp2);
        }
    }
    else
    {
        if ((my_map.find(temp2) == my_map.end()) || my_map[temp2] == false)
        {
            my_map[temp2] = true;
            my_map2.insert(make_pair(temp2, 0));
            my_map[temp] = false;
            my_map2.erase(temp);
        }
        else//both has ball
        {
            ;
        }
    }
}
int count = 0;


for (auto i = my_map2.begin(); i != my_map2.end(); i++)
{
    count++;
    i->second = count;
}

my_map2[INT64_MIN] = 0;
my_map2[INT64_MAX] = count + 1;
int l, r;
int val1, val2;


for (int i = 0;i < q;i++) {
    cin >> l >> r;

    if ((my_map[l] && my_map[r]) || (my_map[r]))
    {
        auto it = my_map2.lower_bound(l);
        val1 = (*it).second;
        it = my_map2.lower_bound(r);
        val2 = (*it).second;
        cout << val2 - val1 + 1 << " ";
    }
    else
    {
        auto it = my_map2.lower_bound(l);
        val1 = (*it).second;
        it = my_map2.lower_bound(r);
        val2 = (*it).second;
        cout << val2 - val1 << " ";
    }


}


return 0;

}

1 Like