AmmarDab3an's blog

Don't use std::array in ICPC contests
By AmmarDab3an, 8 months ago, In English

I don't know why, but using std::array causes RTE in official contests.

In a local contest, there was a problem that I solved using matrices, and because I was used to using Array<> to store the values of the matrices, I faced weird run time errors if I compiled my solution using the Test button on the PC2 on my machine, or if I submitted my solution to the judge. Not just in the locals, but also in the recent 2023 ACPC competition there was a similar problem and some teams that didn't know of the problem faced the same issue which caused them to lose most of the contest's time trying to figure things out without any luck.

It's also a good idea to use the Test button on the PC2 before submitting any problem to catch such errors or to check if the problem was solved.

If anyone know why such a behavior is happening or how to use Array<> without getting an RTE, please share the solution.

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

»
8 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Try asking your local committee to follow the ICPC World finals programming environment https://docs.icpc.global/worldfinals-programming-environment/ to prevent this kind of things happening again

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    They said that they are using the same environment that is going to be used in the next ICPC in Luxur.

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      According to the linked page, they are not. WF uses DOMJudge.

      Also, who is still using PC^2 in 2024?

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        That hurts, in the ACPC, they were supposed to test the systems that are going to be used next month.

        → Reply
»
8 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Are you sure you initialized the arrays properly? Something like "std::array<int,2> x;" as a local variable leaves the values uninitialized. I had a bug like that before.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    Yes, and I wasn't the only one having the same problem, and even so, that wouldn't give an RTE problem on sample test cases at least.

    → Reply
»
8 months ago, # |
  Vote: I like it +58 Vote: I do not like it

maybe give code first if possible

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    I don't have the code rn, but what I did then, is that I only replaced std::array, with std::vector, and got an AC.

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      So maybe std::array causes stack overflow? When it is created as local variable, it is allocated in stack. Did you try using simple C-like array int x[N]; instead of std::array? Did it give same runtime error?

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        no, I didn't try a C-like array, but I think this problem is related to the compiling flags that are being used because if I compiled and ran the sample test cases using the code blocks environment, everything would be fine. but if I used the Test button on the PC2, it would return RTE.

        → Reply
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it +26 Vote: I do not like it

          It's possible that the stack sizes are different in both runs, for example, if PC2 is a different machine (I don't know what you mean by PC2).

          Using a std::vector of std::vector for a matrix is much slower than std::array of std::array, at least for small matrices (you can see this in the matrix exponentiation gym for example), so you might want to do something like auto& dp = *(new std::array<std::array<int, N>, M>()); instead to allocate on the heap.

          → Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    some of the teams that faced the same problem, used c-like arrays in a template such as:

    struct Matrix {
    int dp[110][110];
    Matrix() {
        memset(dp, 0, sizeof dp);
    }
};
    → Reply