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

in Java I got with DFS — Memory Limit Exceeded, with BFS — Accepted
Автор snorkel, история, 3 года назад, По-английски

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?

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

»
3 года назад, # |
← Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

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.

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

    I replace it with if — and still MLE.

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

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

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

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.

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

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.

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

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
	}
}
→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить