Блог пользователя jha_gaurav98

PROBLEM SETTING AND TESTING
Автор jha_gaurav98, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?

        → Ответить
        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

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

          → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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<>.

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится -9 Проголосовать: не нравится

        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.

        → Ответить