The problem link is http://www.codechef.com/problems/DRGHTS
I failed to understand why my submission is getting RTE.The link to my submission is http://www.codechef.com/viewsolution/3469926
Please Help!!
Thanks.
@tiwariabhishek : You have RTE because of “Recursion”
In Java you will always have RTE when using “Recursion” with big data .
You need to implement iterative DFS
Try with large test cases you can generate them using a small program and you will reproduce your error on your machine
I have been using JAVA in competitive programming for long and programs which pass with “Recursive approach” in other languages don’t pass in Java due to limited stack size that JAVA gives .
Refer to my solution also in JAVA :
1 Like
But sir same solution with a new thread got accepted.Please clear my doubt in this case http://www.codechef.com/viewsolution/3432874
In short : Your program is invoked by JVM and JVM has already used much of the stack space , so stack size is insufficient for your “recursive dfs” . When you start a new thread , it has the a fresh stack allotted to it and is hence sufficient for your processing .
Reading
As each new thread comes into existence, it gets its own pc register (program counter) and Java stack. If the thread is executing a Java method (not a native method), the value of the pc register indicates the next instruction to execute. A thread’s Java stack stores the state of Java (not native) method invocations for the thread. The state of a Java method invocation includes its local variables, the parameters with which it was invoked, its return value (if any), and intermediate calculations. The state of native method invocations is stored in an implementation-dependent way in native method stacks, as well as possibly in registers or other implementation-dependent memory areas.
The Java stack is composed of stack frames (or frames).
A stack frame contains the state of one Java method invocation. When a thread invokes a method, the Java virtual machine pushes a new frame onto that thread’s Java stack. When the method completes, the virtual machine pops and discards the frame for that method.
The Java virtual machine has no registers to hold intermediate data values. The instruction set uses the Java stack for storage of intermediate data values. This approach was taken by Java’s designers to keep the Java virtual machine’s instruction set compact and to facilitate implementation on architectures with few or irregular general purpose registers. In addition, the stack-based architecture of the Java virtual machine’s instruction set facilitates the code optimization work done by just-in-time and dynamic compilers that operate at run-time in some virtual machine implementations.
Also Read
-ss Stacksize to increase the native stack size or
-oss Stacksize to increase the Java stack size, ,
The default native stack size is 128k, with a minimum value of 1000 bytes. The default java stack size is 400k, with a minimum value of 1000 bytes.
Useful Links
http://docs.oracle.com/javase/7/docs/api/java/lang/Thread.html
Note you can specify stack size for a new thread .
Note that the issue has been faced by others .
1 Like
Thanks a lot, I understand my mistake.