jha_gaurav98's blog

PROBLEM SETTING AND TESTING
By jha_gaurav98, history, 7 years ago, In English

I am organizing a contest for my college students. For this I thought of a basic graph question. In order to generate the test cases , I used random number generator. But I am not able to generate the output as when I try to run it on my computer it runs out of memory.Can anyone please tell how to run programs with big inputs and outputs? And also is there any other effective way of generating the test cases except the random number generator? Thanks in advance.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Most probable reason for the crash will be stack overflow. The default stack size on Linux is 8 MB which is not sufficient for DFS on graphs with 105 nodes. You can increase stack size using ulimit. (Details)

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have tested the code using debug statements. The program crashes as soon as I create the adjacency list using following line of code:

    vector < int > adj[n + 1];

    I am first taking n (number of vertices) as input and then creating an array of vectors of size n + 1 for creating adjacency list.When I test the code for n = 1000 , it works fine but not for n = 100000. By the way I am using windows.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Use this statement in global scope out of any function. Probably that should solve this.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes it worked. I declared the variable globally as follows:

        vector < int > adj[100005];

        and it worked fine.But why it didn't work inside the main?

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Probably because local variables are stored on stack which has less space and therefore you run out of memory.

          → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You don't understand how C/C++ works.

      When you initialise an array with [length], this is done at compile time, not at runtime. The compiler doesn't know what the value of n will be when you're doing that, so you end up with a nonsense program.

      Either use dynamic allocation new vector<int> [n+1] or a 2D vector<>.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it -9 Vote: I do not like it

        1) But then how it is working when n = 1000 .

        2) According to you , instead of n + 1 we need to give some constant value for length so that compiler can understand it during compile time.So , I changed the above line of code as follows:

        vector < int > adj[100005];

        keeping in mind that value of n can never exceed 105. But then also the program crashes.

        3) And then I did the same declaration globally(outside the main function) and it worked well.

        → Reply