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

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

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

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

»
2 года назад, скрыть # |
 
Проголосовать: нравится +28 Проголосовать: не нравится

idk maybe more than 3 ig

»
2 года назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится

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$$$.

»
2 года назад, скрыть # |
 
Проголосовать: нравится -9 Проголосовать: не нравится

1e8 Upper Bound.

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

In c++, absolutely 4 * 1e8

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

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

  • »
    »
    2 года назад, скрыть # ^ |
     
    Проголосовать: нравится -8 Проголосовать: не нравится

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

    • »
      »
      »
      2 года назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      "very good constant factor and use applicable pragmas"

      • »
        »
        »
        »
        2 месяца назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        so you're saying someone can brute force a solution for problems with n<=10^9 just with a very good constant factor and applicable pragmas?

        • »
          »
          »
          »
          »
          2 месяца назад, скрыть # ^ |
           
          Проголосовать: нравится +1 Проголосовать: не нравится

          Firstly, N<=1e9 is quite rare and you would never have 1e9 elements in an array given input alone would probably exceed time limit. Secondly if it is used as sort of limit to a value e.g. values of an array a1,a2,a3... am where ai <= 1e9 then iterating over all values of [1,1e9] is rarely (never afaik) the intended solution and would likely require you to do very simple calculations per iteration and idk if anything more than a bitwise operation or two can run and often it would require several operations (and usually not bitwise ones) and thus isn't very practical. But if all condiitons are met, yes as maxrgby said it can be done with a VERY good constant factor.

        • »
          »
          »
          »
          »
          2 месяца назад, скрыть # ^ |
           
          Проголосовать: нравится +15 Проголосовать: не нравится

          If your code is incredibly tight, then I think so.

          This can probably run >= 10^9 times in a second if your CPU is 4GHz:

          a:
            add ...  # latency 1 cycle, throughput can run up to 4 independent ALU instructions in a single cycle
            add ...
            mul ...
            add ...
            jmp a  # generally 1 cycle
          

          But, divisions can be 20+ cycles (now you only get maybe 2 * 10^8 of them in a second), and if n = 200,000 and you create a vector<int> that takes 800 KiB in memory, random accesses into it will generally hit L2 and each access takes 10-20 cycles. Sets and maps are worse, it does mallocs, which themselves traverse linked lists which are slow, and you will probably end up in L3 which takes far longer. If you have ifs, mispredicted branches can take 20+ cycles too.

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

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

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится -11 Проголосовать: не нравится

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

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

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.