Marine7's blog

By Marine7, history, 3 months ago, In English,

Hello Codeforces, I'd like to open a discussion about the title.

A judge has a special testing environment, which assumes equal execution time of every instruction (one clock cycle each).

Could you (specifically in C++) take somehow advantage of this testing system property, and write your programs in a style, which generally uses more costly instructions, but fewer of them, as to make it faster in this environment?

And then also, what about things like caching, do they matter in that case?

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

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can you please elaborate on which judge this is? It seems very strange, what does the phrase "assume equal time of every instruction" mean? They look at how many instructions you make? What is an instruction defined as? It would be nice if you can elaborate. Thanks.

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

    Instructions are each individual assembler commands, each counts as 1 instruction, except for REP, REPE, REPZ, REPNE, REPNZ.

    The number of called instructions is counted during execution using Intel PIN. Then, the number of instructions is divided by 3GHz for example, so 3 billion, and that's how the final time result is received I suppose.

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

      I don't think that's how it works (at least on Codeforces).

      Otherwise submitting the same code twice should result in exactly the same execution times, but it doesn't.

      Also counting e.g. integer and floating point operations both as 1 would be weird.

      According to your logic, something like this http://codeforces.com/blog/entry/54753 couldn't happen.

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

        Yes, as I wrote in the main text, I'm talking about a special testing environment used on POI.

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Is the list of "instructions" that count as one clock cycle available?

Sending data to disk and allocating memory would be the most costly operations I can think of right now: -Creating a lot of pointers (this is seen in implementations like an implicit segment tree in an array or a explicit segment tree with pointers, where getting a chunk of memory (array) at once is more efficient) -Flushing data to disk with cin and cout (if this counts as one cycle, you can use cin and cout instead of scanf and printf aka fast I/O without penalty (or just don't have to use the cin.tie, cout.tie, sync_with_io... lines)

Other than those, there would be microoptimizations like: -x << 2 is faster than x * 2

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

    Every instruction except for instructions prefixed with REP, REPE, REPZ, REPNE, REPNZ take one cycle.

    The once listed take as many cycles, as the number of iterations.

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

If cache doesn't matter, std::list would be much faster for sure.