islam-al-aarag's blog

By islam-al-aarag, 7 years ago, In English

I've been debugging this for a while and I still can't tell why it exceeds the memory limit.
Can somebody help me?
Submission: 5723491

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

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

Turns out using ArrayDeque instead of LinkedList makes the problem pass.

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

    Yeh, ArrayDeque is more compact (x2-x5 memory savings according to the size)

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

I have the same problem, what can I do? Submission : 5724820

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

    I think it's because you do recursion and the stack can grow up to 4kk (essentially the longest path) keeping the state of all intermediates. You can generate that case easily.

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

    By the way, your code gets accepted using MS C++ ( http://codeforces.ru/contest/382/submission/5726207 ). I had the same problem, and got accepted with gnu compiler only with dfs on std::stack.

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

    Some codes with the same recursion passed, but they were close to memory limit,
    I just submitted the code with MS C++ and it used much lower memory!!

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

I have the same problem MLE:

Submissions:

I first started with recursive dfs with excessive usage of new (1st submission), so I kinda removed it, then found the longest path will overflow the stack. So, I went to iterative bfs, while storing the final nodes, and following back their path (2nd submission), it didn't go well. So, I removed all that and calculated the distances as I go through the BFS (3rd submission), and now I have no idea, what might have caused the MLE, given that I seen Java solutions similar to what I do. Any help?

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

    What if you change int[][] grid to char[][] grid or at least short[][]

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

    Please Check my 1st comment :)

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

      It worked, thanks! I better learn to watch out next time.

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

        Who can give information about Memory consumption???