You are not logged in. Please login at www.codechef.com to post your questions!

×

The Great Escape: Runtime Error

I tried solving The Great Escape on the INOI server: http://opc.iarcs.org.in/index.php/problems/GREATESC

I used a simple BFS to find the minimum number of jumps. But my code is showing segmentation fault in the last test case. Can anyone one point out my mistake? My code:

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;

vector<int> adjlist[3500];
queue<int> bfs;

int main()
{
    int n,m;
    cin >> n >> m;
    int a,b;
    while(m--)
    {
        cin >> a >> b;
        a--; b--;
        adjlist[a].push_back(b);
        adjlist[b].push_back(a);
    }
    int s,t;
    cin >> s >> t;
    s--;
    t--;
    int v[n];
    memset(v,-1,sizeof(v));
    v[s] = 0;
    bfs.push(s);
    while(!bfs.empty())
    {
        int node = bfs.front();
        bfs.pop();
        int d = v[node];
        for(unsigned int i = 0;i < adjlist[node].size();i++)
        {
            int node2 = adjlist[node][i];
            if(v[node2] == -1)
            {
                v[node2] = d+1;
                bfs.push(node2);
            }
        }
    }
    if(v[t] == -1) cout << 0 << endl;
    else cout << v[t] << endl;
    return 0;
}

asked 10 Jan '15, 10:51

ketanhwr's gravatar image

6★ketanhwr
1.9k31844
accept rate: 15%

It might be a problem with the testdata, but maybe not. I have the same issue.

(10 Jan '15, 11:45) superty3★

But many people have got 100 :-/

(10 Jan '15, 13:13) ketanhwr6★

I have the same problem too!

(10 Jan '15, 13:19) sandy9993★

They would've looked at the test cases I suppose. A lot of number of iarcs problems seem to have issues

(10 Jan '15, 17:57) superty3★

I asked someone. The test data is faulty. Just check if m = 641902. If it is then output 0 and exit (although the correct answer is 2800). For other m, run the normal program.

(10 Jan '15, 22:29) ketanhwr6★

Yeah, as I said the test cases must be faulty. IMO it's not of any use to do these kind of modifications, you don't learn anything, just get some points in IARCS site which is of no purpose.

(11 Jan '15, 10:58) superty3★

@superty Are the test cases faulty for DEVIOUS as well? I am getting only 80 points.

(11 Jan '15, 17:10) sandy9993★

I got 80 as well. In future you can check in my profile: http://opc.iarcs.org.in/index.php/users/Superty

(12 Jan '15, 00:21) superty3★
showing 5 of 8 show all

Hello @ketanhwr, I am also having the same problem as you in GREATESC. I used the same logic as yours. I once asked Prof. Madhavan Mukund about what can be the probable causes for "SEGMENTATION FAULT". He replied that perhaps I am accessing an illegal memory. However, I recently can to know that it may be shown because of crossing the memory limits. Therefore, though adjacency list representation uses O(n+m) memory, it might be crossing the memory limits (though I am not sure of it). If you come to whether that it is the problem, then kindly inform me.

Cheers!!!

link

answered 21 Jan '15, 23:46

anupam_datta's gravatar image

4★anupam_datta
379525
accept rate: 7%

edited 21 Jan '15, 23:47

1

Please read the comments. The test data is wrong. You probably aren't exceeding the memory limit.

(22 Jan '15, 00:35) superty3★

@superty Well, if the test data is really wrong,then why is it showing "SEGMENTATION FAULT" instead of "WRONG ANSWER"????

(23 Jan '15, 20:55) anupam_datta4★

There is some problem on the server. I checked the test data for myself and my program was showing the correct answer. The output file, too, was incorrect.

(23 Jan '15, 21:02) ketanhwr6★
1

Incorrect test data can result in segfault because your program can't handle the wrong test data. e.g. N <= 100 and the test data is N = 1000 or something.

(23 Jan '15, 21:42) superty3★

Well I'm not so sure about the test cases being faulty. I implemented a simple BFS and it gets 100 on the grader with no issues.

In case you want to check - http://pastebin.com/JMmvUXJ2

link

answered 04 Feb '15, 18:08

ishoo's gravatar image

3★ishoo
54
accept rate: 0%

They've now fixed the test data. The same program which failed previously works now.

(not that the last comment on this thread is dated 23rd Jan)

(04 Feb '15, 18:48) superty3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×504
×365
×109
×13

question asked: 10 Jan '15, 10:51

question was seen: 1,409 times

last updated: 04 Feb '15, 18:50