Marine7's blog

How to take advantage of Equal execution time per instruction — one clock cycle on Polish Olympiad in Informatics
By Marine7, history, 7 years ago, In English

On POI, there is a special testing environment, which assumes equal execution time of every instruction (one clock cycle each), the count of the cycles is then divided by some number which mimicates the real CPU cycle capabilities, to get the runtime.

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 the execution time faster in this environment?

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

Comments Comments (6)
| Write comment?
»
7 years 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.

→ Reply
  • »
    »
    7 years 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.

    → Reply
    • »
      »
      »
      7 years 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://mirror.codeforces.com/blog/entry/54753 couldn't happen.

      → Reply
      • »
        »
        »
        »
        7 years 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.

        → Reply
»
7 years 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

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   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 ones above take as many cycles, as the number of iterations.

    → Reply