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

Автор PiggyPump, история, 12 дней назад, По-английски

On the most recent Bleddest Div 2, I used gcd instead of mod, thinking I wouldn't get punished.

Becuase O(n^2 log 10^9) = 30 * 5000 * 5000 = 7.5 * 10^8 which should pass.

But it turns out that the C++ built in gcd uses the Euclidian Algorithm:

int gcd (int a, int b) {
    return b ? gcd (b, a % b) : a;
}

Hacked Submission: https://codeforces.me/contest/2283/submission/397357386

So the next time you want to compute GCD, use Stein’s algorithm:

int gcd(int a, int b) {
    if (!a || !b)
        return a | b;
    unsigned shift = __builtin_ctz(a | b);
    a >>= __builtin_ctz(a);
    do {
        b >>= __builtin_ctz(b);
        if (a > b)
            swap(a, b);
        b -= a;
    } while (b);
    return a << shift;
}

I get the easy AC after getting hacked :( https://codeforces.me/contest/2283/submission/397490186

So what do you guys think about the built in gcd?

Edit: newer versions of C++ (later than 17) actually don't use the Euclidian Algorithm. (Read: https://codeforces.me/blog/entry/137056)

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

»
12 дней назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by PiggyPump (previous revision, new revision, compare).

»
12 дней назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

who told you 7.5e8 should pass TL 2 seconds

  • »
    »
    12 дней назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    The problem is that 7.5e8 easily passes but something like 3e9 never does. Since, we really have not accounted the other constants which might honestly play a roll in such tight calculations that is why something like n^2 would have easily passed. The point being it is not the fxn's fault but the author's own fault for not understanding the point of big-oh notation. Correct me if I am wrong, but if you told me that there are exactly 7.5e8 operations in this code I would expect it to pass in 1 second.

  • »
    »
    12 дней назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    7.5e8 should always pass in 2 seconds, you can I tested it yourself by just doing a for loop, now apologize to me.

    • »
      »
      »
      12 дней назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      What about constant? Note that Big O Notation ignores it.

    • »
      »
      »
      10 дней назад, скрыть # ^ |
      ← Rev. 3  
      Проголосовать: нравится 0 Проголосовать: не нравится

      I verified that a simple for loop running from 1 to 7.5e8 runs smoothly in ~0.5 seconds. However, try running this code :

      map<ll,ll> freq;
      for (ll i=1; i<=n; ++i){
          for (ll j=1; j<=n; ++j){
              freq[i]=freq[j]*freq[j]+5;
              ++freq[j];
          }
      }
      

      This code have complexity of $$$O(n^2 log n)$$$ but if I plug in n=5000 then it takes my computer 11 seconds to complete which based on your point runs $$$5000^2*log2(5000) = 3e8$$$ (which should pass right?)

      My point is that the Big O notation cancels out the constants so your solution might run 10 times slower than mine though they have the same time complexity.

»
12 дней назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

The problem isn't the C++ gcd function, submissions are only meant to pass with $$$O(n^2)$$$, not $$$O(n^2 \log a_{max})$$$, so your approach is at fault.

  • »
    »
    12 дней назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится -11 Проголосовать: не нравится

    If you read the blog carefully, you would have noticed that my O(n^2 log max(a,b)) solution passes very easily 1.1s/2s, now apologize to me.

    • »
      »
      »
      12 дней назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится +1 Проголосовать: не нравится

      This blog, and the corresponding comment, are wrong in so many ways.

      • You're right that in your first submission, gcd uses Euclidean algorithm. However, this is because you made your submission in C++ 17. gcd in newer versions already uses Stein's algorithm, so it is highly misleading to tell people that C++ uses Euclidean, since most people make submissions in newer versions of C++.
      • It is absolutely not true that Stein's is asymptotically faster than Euclidean. In fact, the opposite is true; the number of steps required in Stein's algorithm is logarithmic in the larger number, whereas the number of steps required in Euclidean algorithm is logarithmic in the smaller number, so Euclidean is actually asymptotically faster. Therefore, your solution is not $$$O(n^2 \log \min(a, b))$$$ as you claim. ($$$a$$$ and $$$b$$$ aren't even well-defined in this expression, but in some handwavy sense, your solution is $$$O(n^2 \log \max(a, b)) = O(n^2 \log A)$$$ anyways.) The reason why Stein's is sometimes faster is because it avoids division operations, which are expensive.
      • If your solution does not run in the intended runtime, it may or may not pass. If it does not pass, you don't really have the right to get upset, because it does not run in the intended runtime. (If it does pass, good for you.) The intended runtime of this solution is concretely $$$O(n^2)$$$, with no logarithmic term (not even an $$$n\log n$$$ term, like your solution does with sorting).
      • People do not owe you an apology, regardless of whether they are right or wrong. Therefore, you should not rudely request an apology from people. In any case, here they are right and you are wrong anyways.
      • »
        »
        »
        »
        12 дней назад, скрыть # ^ |
        ← Rev. 3  
        Проголосовать: нравится -8 Проголосовать: не нравится

        I have the right to request an apology because my unintended solution does work 100%, did you even bother to check my submission?

        1. C++ didn't share their gcd implementation, so you are right that in newer versions, the faster (not asymptotically) stein algorithm is used.

        2. I never claimed that Stein's is asymptotically faster in my blog, so what are you on claiming that I said it was asymptotically faster.

        3. I was never upset, I was just stating a fact that in the context of this question, Stein's algorithm runs faster than default c++17 std::gcd(). And also, I never sorted at all inside the for loops -- clearly you don't know what you're talking about.

        4. I have the right to request an apology from him (and quite frankly you), because mateiash said "submissions are only meant to pass with O(n^2)", which is simply incorrect, because my O(n^2 log A) works perfectly fine.

        • »
          »
          »
          »
          »
          12 дней назад, скрыть # ^ |
           
          Проголосовать: нравится +1 Проголосовать: не нравится
          • It seemed like you were implying that Euclidean was asymptotically slower; maybe I misunderstood. But in any case, you explicitly said that your solution is $$$O(n^2 \log \min(a, b))$$$ in your (now edited) comment. This is not only ill-defined, but also blatantly false.
          • You certainly seem upset.
          • What the fuck do you call sort (arr.begin(), arr.end()); in your code, if not sorting?
          • Solutions are only meant to pass with $$$O(n^2)$$$. This is 100% true. It is also possible that some $$$O(n^2 \log A)$$$ solutions will pass, but that does not mean they are intended to pass. Indeed, in some problems, pragma cheeses on $$$2e5^2$$$ will pass. They are not supposed to pass. "Passes" and "are supposed to pass" are two entirely different concepts.
          • »
            »
            »
            »
            »
            »
            12 дней назад, скрыть # ^ |
             
            Проголосовать: нравится 0 Проголосовать: не нравится

            I disagree with #4 here. As a problemsetter, my job is to ensure all solutions (including really bad ones within reason) with the correct complexity pass, and no solutions with the wrong complexity pass. In polygon we are required to make all correct solutions run in half TL and all bad ones run in double. Although in fairness, cutting logs is quite hard.

            • »
              »
              »
              »
              »
              »
              »
              11 дней назад, скрыть # ^ |
              ← Rev. 5  
              Проголосовать: нравится 0 Проголосовать: не нравится

              I think you are misunderstanding what I am saying. I mostly agree with what you just said.

              My general take is something like:

              • for this problem, all $$$O(n^2)$$$ solutions should pass (because this is the intended complexity)
              • for this problem, in an ideal world all $$$O(n^2\log A)$$$ solutions should fail (because this is not the intended complexity, and any solution of this complexity is missing fundamental observations in the problem)
              • if I was the setter, I would like to cut all $$$O(n^2\log A)$$$ solutions, but I would also know that in practice this is very hard to do, and I would probably accept that some of them would pass
              • if I was the participant, I would not submit an $$$O(n^2 \log A)$$$ submission with the expectation that it deserves to pass, and if I did submit it, I would not complain if it fails

              I think this is consistent with both my previous comment and your comment.

    • »
      »
      »
      12 дней назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      In the worst case scenario, all numbers in the array are equal to $$$10^9$$$, so you can indeed get to $$$O(n^2 \log a_{max})$$$ complexity.

»
12 дней назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

just use pragma

»
12 дней назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by PiggyPump (previous revision, new revision, compare).

»
12 дней назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I learned this the hard way as well, n^2 log n is generally not considered intended for n=5000 in most cases but it works sometimes

»
12 дней назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

green post downvoted

»
12 дней назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Or you can just use c++20 or newer. They seem to perform at the same speed as your manual implementation. submission

It's generally a good idea to submit on more recent versions unless having a specific reason not to do so.