Qualified's blog

The HELL?
By Qualified, history, 4 years ago, In English

Run this O(n^2) program in CF custom test

#include "bits/stdc++.h"
using namespace std;

long long n;

int main() {
    cin >> n;
    for(long long i = 1; i <= n; i++) {
        for(long long j = 1; j <= n; j++) {
            if((i ^ j) == 0) {
                if(i != j) {
                    cout << "NO!\n";
                    return 0;
                }
            }
        }
    }
    cout << "YES\n";
}

with n = 100000000000

You would expect it to be much longer than 1 second, but it takes

15 ms

screenshot

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

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

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

(1^2)==0

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

Codeforces uses a thing named Compiler optimization.

→ Reply
»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

If $$$i \oplus j = 0$$$ then $$$i=j$$$.

However there's also a condition $$$i \neq j$$$, these conditions cannot be both true.So cout<<"NO!"; never processes.

The compiler found it, and then skipped the whole procedure.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

The compiler probably ignores both loops, because these two conditions, if(i ^ j == 0) and if(i != j) will never be true at the same time so it ignores everything as the loops aren't doing anything. Compiler automatically ignores redundant code like that.

→ Reply
»
4 years ago, # |
  Vote: I like it +42 Vote: I do not like it

https://godbolt.org/ — use this website to investigate such stuff. As you can see there is no assembler corresponding to loops. However, if you replace if(i != j) with if(i != j + 1), you can see that asm suddenly becomes much more complicated. Conclusion: compiler indeed optimizes the loops away. I recommend you to play around with this stuff as you seem pretty interested in it. Another example of optimization:

Spoiler

From length of assembler codes you can guess that only MVC and Clang, contrary to GCC don't optimize this loop to a formula. And even GCC wouldn't optimize (a += 69ll*n + 420) %= 228. You can confirm those results using Costum Invocation. Go ahead and play around with this stuff!

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

    (a += 69ll*n + 420) %= 228

    paying my respects!
    → Reply