There are many problems requiring deep recursion. Usually it's graph problems with big limitations which are solved by DFS. But deep recursion requires large stack size, often several megabytes.
In C++ or Pascal/Delphi the stack size can be set by compiler directives. But it's impossible in Java. The default Java thread stack size is quite small, it's 320kb in 32-bit Windows. The most simple solution is to use -Xss command line switch. But this is where problems begin.
Firstly, this thing should be known). As practice shows, many competitions and online judges don't understand such issues or don't want to do it. It results in writing non-recursive DFS which is not always trivial and I'm always lazy to do it. Or I have to write/rewrite code in C++ which is simply sad itself.
Secondly, using of the -Xss switch can cause some bad things. The stack size set by it is assigned to all Java threads. It can be ignored for simple single-thread application but can cause problems in testing system if it creates many Java threads.
Also a problem of unaccounted memory usage arises. If the testing system sets memory limit by -Xmx switch, an application can use more memory than that limit because of stack using. Since the Memory Limit Exceeded verdict control becomes slightly inccorrect if the testing system checks it by handling OutOfMemoryError.
It's worth to say that such flaws are often just ignored. The standard JVM launch command
java -Xmx<?>М -Xss<?>M <class name>
is used at NEERC which it stated in rules given before the contest (though there is no info about it at the official site), at Timus and at Petrozavodsk Training Camp. I also have some suspections that the same command line is used at the ACM ICPC World Finals, but only from answers at Q&A Session.
Thirdly, before Java 1.6 the -Xss switch was applied only for newly created threads, but the main thread used the default OS stack size. Since I had to write something like this in the main method:
But then Codeforces appeared.
Haven't found the necessary command line switches at the compiler description, I post a comment. I was greatly surprised when MikeMirzayanov answered that "It's better to create a new Thread with predefined stack size and run the solution code in it". All my life I thought that it's impossible to predefine the stack size) But after viewing JavaDoc (why couldn't I do it earlier?) I discovered a pretty Thread constructor:
May be you've dealt with some other problems with stack or know other ways to set it? Post it in comments)
In C++ or Pascal/Delphi the stack size can be set by compiler directives. But it's impossible in Java. The default Java thread stack size is quite small, it's 320kb in 32-bit Windows. The most simple solution is to use -Xss command line switch. But this is where problems begin.
Firstly, this thing should be known). As practice shows, many competitions and online judges don't understand such issues or don't want to do it. It results in writing non-recursive DFS which is not always trivial and I'm always lazy to do it. Or I have to write/rewrite code in C++ which is simply sad itself.
Secondly, using of the -Xss switch can cause some bad things. The stack size set by it is assigned to all Java threads. It can be ignored for simple single-thread application but can cause problems in testing system if it creates many Java threads.
Also a problem of unaccounted memory usage arises. If the testing system sets memory limit by -Xmx switch, an application can use more memory than that limit because of stack using. Since the Memory Limit Exceeded verdict control becomes slightly inccorrect if the testing system checks it by handling OutOfMemoryError.
It's worth to say that such flaws are often just ignored. The standard JVM launch command
java -Xmx<?>М -Xss<?>M <class name>
is used at NEERC which it stated in rules given before the contest (though there is no info about it at the official site), at Timus and at Petrozavodsk Training Camp. I also have some suspections that the same command line is used at the ACM ICPC World Finals, but only from answers at Q&A Session.
Thirdly, before Java 1.6 the -Xss switch was applied only for newly created threads, but the main thread used the default OS stack size. Since I had to write something like this in the main method:
new Thread() {
public void run() {
new Main().run();
}
}.start();
It became unnecessary to do it when 1.6 appeared, and I had almost forgot about all stack size-related worries. But then Codeforces appeared.
Haven't found the necessary command line switches at the compiler description, I post a comment. I was greatly surprised when MikeMirzayanov answered that "It's better to create a new Thread with predefined stack size and run the solution code in it". All my life I thought that it's impossible to predefine the stack size) But after viewing JavaDoc (why couldn't I do it earlier?) I discovered a pretty Thread constructor:
public Thread(ThreadGroup group,It should be noted that it's repeated in JavaDoc several times that how the value of stackSize argument is used and whether it is used at all depends on the OS. But the test showed that it works perfectly at least at Codeforces and TJU. The resulting operator in main method is
Runnable target,
String name,
long stackSize).
new Thread(null, new Runnable() {
public void run() {
new Main().run();
}
}, "1", 1 << 23).start();
It sets the stack size of a thread named "1" to 8 MB.May be you've dealt with some other problems with stack or know other ways to set it? Post it in comments)
Codeforces doesn't create a lot of threads. So why do you need to reduce stack size?
Will you please provide a example program using Runnable interface. It will be a great help.
This is how I do every problem that involves deep recursion.