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

Автор Qualified, история, 4 года назад, По-английски

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

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

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

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

(1^2)==0

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

Codeforces uses a thing named Compiler optimization.

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

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.

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

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.

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

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!