snorkel's blog

in Java I got with DFS — Memory Limit Exceeded, with BFS — Accepted
By snorkel, history, 4 years ago, In English

Recently I was solving the problem from kattis and typed DFS solution and got Memory Limit Exceeded, then I typed exactly the same thing in C++ and got AC. After not figuring out the fix, I went with BFS and it passed (in Java).

This is my DFS:

DFS Code

This is my BFS code:

BFS code

Full Codes:

Full code - with DFS (MLE)
Full code - with BFS (AC)

What can cause this kind of thing?

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

»
4 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

In your bfs, you break when boolean can becomes true, you try to do the same thing with your dfs implementation, however, you use can=can | dfs(ii, jj, climb) and | clause does not short-circuit meaning that it will examine all the conditions, instead of just breaking if one of the condition is true , which is exactly what happens here because your dfs function is called much more times than intended leading to MLE.

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

    I replace it with if — and still MLE.

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

      Try replacing the final line from can|=dfs(ii,jj,climb) to can=can||dfs(ii,jj,climb) and let me know what happens.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        still MLE. (CF has limited me to 10 minutes for each comment or smth. lol).

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

          It might just be because it is Java+RecursiveSpace, idk, lol. Best of luck!

          → Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

even with java stack terribleness, there's no way you're using an entire gigabyte if your recursion is $$$NM \leq 10^6$$$ in depth. you probably have some stack overflow or something causing you to recurse infinitely.

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

Good question, I appreciate you explaining your problem and having put the effort into making a few different questions and trying to debug rather than just saying 'my code broken how to fix'. I think all of the logic of your code does what it should after some print statement debugging.

The next thing I did was generate a random 400*400 test case and run it in intellij. It crashed from a stackoverflow error at a depth of about 5k stack frames. This is pretty small, but from googling a bit maybe it's normal? (https://stackoverflow.com/questions/4734108/what-is-the-maximum-depth-of-the-java-call-stack)

Perhaps the stack memory size is much smaller than the heap size, and that's your problem. But I feel like I've gotten AC on some DFS programs that went quite deep; maybe someone with more experience can say something on this. I could just be wrong and it's always bad, or maybe it's something with tail recusion making it not problematic sometimes.

With a BFS, you won't have any problems, since your data is all stored on a heap.

So, it seems the moral of the story is to avoid arbitrarily deep recursive calls when the compiler won't be able to optimize them out with tail recursion (java apparently never does this). Though if someone else with more experience would validate my claim, I'd feel better about it, since I feel like I've had similar codes pass in the past.

→ Reply
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

This is probably a case of stack overflow. You can overcome this on most modern online judges by using the thread constructor which sets the stack size.

public class Main {
	public static void main(String[] args) throws InterruptedException {
		Thread thread = new Thread(null, Main::solve, "", 1<<28);
		thread.start();
		thread.join();
	}
	public static void solve() {
		//code here
	}
}
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is very interesting. But now instead of MLE, I got Time Limit Exceeded.

    → Reply