shevlopmes's blog

"You can do 1e9 operations per sec". Well, what "the operation" really is?
By shevlopmes, history, 20 months ago, In English

Hi Codeforces!

Today I'm writing this blog to express my sad feelings about my lack of knowledge. I was pretty sure that a testing system does around 1e9 operations per a second. That's what everyone have been telling me for last 2 years. The problem, as I think, is that I didn't really question myself what "the operation" is. That's why I made an unsuccessful hack attempt in today's round. Some newbie wrote the code for problem A using this:

for(int i = 0; i < m; ++i){
  for(int j = 0; j < i; ++j){
     if(B[i] == B[j]) {...}
  }
}

m is up to 5*1e4, so even these 5 lines make around 5*1e4*2.5*1e4 = 1.25*1e9 operations. Obvious TL, as I thought. But it wasn't (the solution soon got AC on final tests). I think that by saying "the operation" people actually mean some arithmetic operation like plus, minus, maybe divide, while logic operations may take smaller time. Again, this is only my assumption, and if you know the real explanation to this situation, please write it in the commentary section.

Tags c++
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

for(int i{}; i<n; ++i) for(int j{}; j<n; ++j) exit(0);

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

    the line "exit(0);" ends the whole programm, so this code iterated only once.

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

I have known that while solving problems it is safe to assume 1e8 operations per sec in C++. There are some operations which are slower than other operations. It usually depends how cache-friendly your operations are (It can sometimes do 2e9 — 3e9 operations or more as well) . Some operators like % (modulo) are heavier than let's say addition, subtraction.

In case of the code you mentioned, it depends on the code inside the if.

But if it is very light, then it can in fact do more than 1.25 * 1e9 operations.

Here is a recent blog related to this...

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

Some light operations(like addition or bitwise operation) can indeed be very fast. If you add some pragmas, you can do more than a few billions of them.

However, usually this doesn't work if the code is a little bit complex.

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you! I've heard about pragmas as some magic solution but never used them. I'll check it

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

      Then you can use avx instructions and be able to perform $$$10^{10} - 10^{11}$$$ operations per second, depending on the operation.

      → Reply