flaming_top1's blog

How much commands can codeforces run in 1 sec?
By flaming_top1, history, 6 months ago, In English

1e8? 5e8? 1e9? I seriously don't know so can someone kindly help me please? (Im still a newbie)

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

»
6 months ago, # |
  Vote: I like it +28 Vote: I do not like it

idk maybe more than 3 ig

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

I'm pretty sure that in typical Competitive Programming, about $$$10^7$$$ or $$$10^8$$$ operations can be run in a second. So, for example, if you had a code that runs in $$$O(n^2)$$$ time, then your maximum value for $$$n$$$ would be like $$$10^4$$$.

→ Reply
»
6 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Depends upon compiler optimizations, in c++ you can run upto 10^7 instructions in a second.

→ Reply
»
6 months ago, # |
  Vote: I like it -9 Vote: I do not like it

1e8 Upper Bound.

→ Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In c++, absolutely 4 * 1e8

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

5e8, if your code has very good constant factor and use applicable pragmas maybe 1e9

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

    I use C and my program can run up to 1e9*1.5 if I don't use slow operations(such as "/","*","sqrt",etc)

    → Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    then why do $$$1 \le n \le 10^9$$$ solutions TLE when their time limit is $$$\ge 1$$$ second?

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

It can go all the way to 1e10, if the operations take less time, compared to others.

→ Reply
»
4 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

It's about 5*10^7 commands that can run in 1 sec and in 2 seconds 10^8 commands can run

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

Depends on the type of operation; for example, if the bottleneck is bitwise operations (such as in traveling salesman problem) you can do even more than 1e8 a second. If you do a lot of pointer accessing (such as in a binary search tree or linked list) it is closer to 1e7. Overall 1e8 is a great rule of thumb.

Consider this chart and remember most CPUS have a clock speed ≥ 2Ghz. That is why bitwise operations are so fast (and it feels like it can even approach 1e9 ops / sec) while others are closer to 1e8.

→ Reply