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

Avoiding stackoverflow with recursive algorithms?
Автор brycesandlund, история, 8 лет назад, По-английски

I am wondering what tricks the competitive programming community uses to avoid stack overflow with recursive algorithms. I vaguely remember pulling up someone's code a while back that used a recursive DFS with input size at least 100,000. I also have Steven and Felix Halim's Competitive Programming book and they seem to use recursion without regard to the possibility of stack overflow.

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

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

You can increase default stack size using a custom Thread in Java, something like this (1<<26 is the stack size):

  public static void main(String[] args) throws Exception {
    new Thread(null, new Main(), "Main", 1<<26).start();
  }
 
  public void run() {
   // solve the problem here
  }

For example, 20402431 submission works for trees having up to 400,000 nodes.

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

    Clever. Can you do anything similar for c++?

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

      Stack size in C++ is a property of the compiling/running environment, so it depends on the judge setup. In most judges it is set to a very high value (Codeforces has 256MB), so it's very hard to cause stack overflow. This is probably why most people don't even consider the possibility.

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

        Thanks guys. Unfortunately, it does not look like ACM-ICPC, at least at the World Finals level, increases the default stack size. The compilation command at the ICPC World Finals is:

        g++ -g -O2 -std=gnu++11 -static $*

        And it looks like the compilation on Codeforces is:

        g++.exe -static -DONLINE_JUDGE -lm -s -x c++ -Wl,--stack=268435456 -O2 -o {filename}.exe {file}

        I would like to maintain coding strategies that are sufficient for ACM-ICPC World Finals.

        Sources: - https://icpc.baylor.edu/worldfinals/programming-environment - http://codeforces.me/blog/entry/79

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

          That switch is only relevant if you're dealing with a Windows judging machine (ICPC WF uses Linux).

          If we're talking stack sizes in Linux, then you can change them from outside the program by ulimit or within the program by calling setrlimit(). I don't know whether you can use either of those options in WF, but the compiler switches don't tell the whole story.

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

            Can anyone speak as to whether these options are allowed in ICPC WF? Or if they manually set the stack limit higher with ulimit?

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

              I asked John Clevenger and typically, the stack size is 64MB for c++, matching that of Java. This is enough to do some deep recursion, but can become an issue if your recursion is >=1,000,000 frames deep.

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

                This doesn't sound entirely correct. Let me clarify.

                There are two judging systems being used at the WF: Kattis and DOMjudge. Kattis' sandbox for running programs doesn't impose any limit on the stack size, other than the usual overall memory usage limit. So for C++, it's effectively being run with "ulimit -s unlimited".

                Java, on the other hand, is given a stack limit of 64MB, as seen on https://open.kattis.com/help/java

                I'm not too familiar with the DOMjudge setup, but the intention is that Kattis and DOMjudge should give the same verdict on any given submission. So if the above is true for Kattis, it should also be true for DOMjudge. (During the WF the two judging systems communicate and alert us if any submission gets different verdicts).

                One final thing I wanted to point out is the Kattis online judge. It's running the same software as is run at the WF, so you can use it to try out submissions before going to the WF. You can even find past ICPC problems here. There are some minor differences, so you should be vary of those (such as per-test-case verdict being shown on the OJ but not at the WF, and MLE being displayed as RTE at the WF). But that's why you have the dress rehearsal at the WF: so you can double-check that everything is behaving as you expect.

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

                  Here is the email I received from John Clevenger regarding the issue:

                  "Hi Bryce, First, my apologies for the long delay with no response. Somehow your question got lost in the shuffle of all the ICPC stuff I'm dealing with; I apologize.

                  The answer to your question isn't completely straightforward; here's why. The WF 2017 OS environment adjusts the stack size to be "unlimited" (overriding the default 8MB limit in Linux).

                  However, what ultimately determines the actual stack size limit used is not the OS, it is the Contest Control System (CCS) -- the software which actually executes team submissions. The CCS team sets the stack size on a per-problem basis, at the direction of the WF Judges.

                  At this time the Judges are still developing the problem set (so, they most likely haven't even begun to consider limits like stack size). In addition, the CCS to be used for WF2017 hasn't yet been chosen. So all of these things mean that the answer to the question "what will be used at WF2017" is "it hasn't been decided yet".

                  Sorry; I know that's not what you wanted to hear. If it helps, I can tell you that LAST year the Judges specified that C++ should be limited to the same as Java, and last year Java was set at 64MB. If I had to guess (and it's just a guess), I would guess they would do the same thing this year....

                  john"

                  It seems there is not a simple answer, but since they used a 64MB limit last year, I would expect it to be similar this year.

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

                  I just double-checked with the Kattis team, including one of the WF judges. John is mistaken about the 64MB stack limit for C++, and it has been unlimited for several years now. My comment above still stands.

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

                  WFIW: I can confirm that DOMjudge at the last few ICPC World Finals used (as it does by default) these very same settings: stack size set to unlimited, so everything is limited by the overall memory limit only.

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

                  Thanks guys. John emailed me recently and linked to the 2017 environment: https://icpc.baylor.edu/xwiki/wiki/public/view/worldfinals/programming-environment which states a 64MB stack size for Java and no stack limit for C, C++, and Python.

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

Another thing to avoid that I discovered recently is to pass as little as arguments as needed to the recursive function.

For example, I had a function with the signature 

dfs(int node, vector<int> &visit, vector<int> &tim, vector<int> &bridge, .. 2 more arguments)

When I made the vectors gloabal, and just allowed the function to have 1 argument, suddenly the code was running in time.

dfs(int node)

This is something that we tend to miss at times, but with each function call you should minimize the stack space used! It can also be confusing as this was giving me TLE, but on running valgrind I saw that it's getting stuck due to lack of stack space.

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

Let's say you have a recurrence of this form :

F(x) = CostFunction + F(x — 1)

Let's say x can be pretty large so we if we call it immediately as F(x) it will overflow. If instead we call F(1) then F(2) then F(3) and so on till F(x), we will not get overflow because previous states will already be computed and ready in the DP table.

Of course this is a silly example, but you get the idea. With that being said, I only needed this once on a problem on UVA and I was using Java without re-sizing the stack.

→ Ответить