islam-al-aarag's blog

By islam-al-aarag, 11 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

| Write comment?
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

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

  • »
    »
    11 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.

  • »
    »
    11 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.net/contest/382/submission/5726207 ). I had the same problem, and got accepted with gnu compiler only with dfs on std::stack.

  • »
    »
    11 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!!

»
11 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?

  • »
    »
    11 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[][]

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

    Please Check my 1st comment :)

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

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