vok8's blog

By vok8, history, 4 years ago, In English
  • Problem: XXOR

  • Submission-1: Link (Runtime Error)

  • Submission-2: Link (Accepted)

  • The difference between both the submissions is just the two cout<<""; statements, in the two "n" range for loops.

  • The cout<<""; statements are uncommented in Submission-2 and commented in Submission-1. And guess what, these statements convert a RE Submission to an AC Submission.

  • The code in Submission-1, for a Valid Random Input, runs finely in Codeforces' Custom Test, whereas it gives RE in AtCoder's Custom Invocation. (You may try, for more clarification and to find the reason!)

  • I found it weird! I am totally clueless about why this is happening. Can anyone please justify or explain, why is this happening?

  • Thank you!


UPD: It seems like, the cout<<""; statement(s) in the "n" range for loops, avoid (stop) the optimisation(s), which -OFast + "avx2" try to make, hence, converting the RE solution into an AC solution.

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

»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

With pragmas:

Without pragmas:

It probably tried to optimize your loops.

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

    Ohh, I get it! Thanks!

    But, if "pragmas" are the true reason behind this RE, why and how it would run finely on Codeforces' Custom Test?

    Also, the RE solution passes the 3 sample tests, and fails (gives RE) on other tests (except sample tests)! Seems Strange and Weird.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

It seems that Ofast + target("avx2") together causes Runtime Error. But using them separately gives AC.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

using O2 + target("avx2")

Why would you use pragma for O2? Any self-respecting judging platform would have O2 already enabled.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yeah, it might be enabled.

    But, on some platforms, it might be possible that O1 is enabled, instead of O2.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I can tell you for a fact that any platform with -O1 is a platform not worth coding on, serious. Speed of a C++ code is slooow without at least -O2 optimisation: you would find that your code takes much more time to run than what you are used to.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ohh, thanks for that information!

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Consider the following code snipet

#include<bits/stdc++.h>
using namespace std;
int main() {
    cout << __builtin_cpu_supports("avx2");
}

When you run it through AtCoder's custom invocation, the output is 0. Which means AtCoder DOES NOT SUPPORT AVX2 and you shall never use it there. What happens is compiler optimizes your code using avx2 instructions but processor can't execute them. If you ever get AC with this pragma, it only means that compiler could not optimize your code using avx2 instructions.

However, it supports technologies like avx, sse ... sse4.2, popcnt. Most of the other stuff should work fine. But you should always verify technology support through __builtin_cpu_supports if you don't wanna get fucked.

UPD: The CPU model on which your code is executed seems to be different depending on how old the contest is. You can use avx2 as well as avx512 in the newer contests. I have no clue why did they do it this way.

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    Ohh!

    Thanks, for such amazing explanation!

  • »
    »
    4 years ago, # ^ |
    Rev. 5   Vote: I like it +8 Vote: I do not like it

    It gives 0, on the Custom Test, of the above contest! AtCoder Beginner Contest 117 (As you said)

    But, it gives 1024, on the Custom Test, of AtCoder Beginner Contest 168 (Recent One).

    I think the GCC version is making the change here (like, "avx2" isn't supported in GCC 5.4.1, but it is supported in GCC 9.2.1). I think, this is the reason, because the version of GCC in both the custom tests, is different.

    Although, thanks for that syntax, to check whether a pragma, is supported or not.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Since I'm solving some old AGC problems, I've noticed that AtCoder has some weird shit going on with the compilers depending on contest. TIL it probably also applies to processors. The problem is definitely not compiler, if compiler wouldn't support avx2 you'd get CE verdict(try compiling with avx69 for example), RE is the result of processor not supporting avx2.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Ohh, weird!

        So, it seems better, not to use pragmas on AtCoder, to avoid such pre-processor issues.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 5   Vote: I like it 0 Vote: I do not like it

        So, it can be concluded like:

        • Both GCC Versions on AtCoder, support "avx2".
        • But, the pre-processor (CPU) of GCC 5.4.1 on AtCoder doesn't support "avx2" (hence, leading to RE), while the pre-processor (CPU) of GCC 9.2.1 on AtCoder does.
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          I was talking about CPU. And it is in fact different depending on compiler option chosen. I updated my original comment.

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Ohh, cool! Thanks for the explanation!