MokaMoka's blog

By MokaMoka, history, 5 years ago, In English

Hello Codeforces,

I started learning Python a week ago, and I've just solved my first problem using it. However; I was surprised by the huge execution time and memory for a very trivial problem, which makes me doubt if there's any effective tricks/advice to follow when using Python for competitive programming.

Wouldn't it be nice if we just collect some of those ideas here or somewhere else and make it available for everyone?

Please don't comment such comments like "The only advice I can tell is Don't use Python for competitive programming" :P, this is serious :)

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

submit solutions using pypy.

even though pypy 2 passed, it barely passed O(nm) where 0 ≤ n, m ≤ 1000 in one second. i would keep a back-up language in case the problem requires a lot of computation.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That sounds cool but, I'm a little bit confused. I've just submit the same solution again but this time using PyPy 2 instead of Python 2, and I was surprised that the execution time got slower :| as well as my code now uses much more memory.

    Can you provide a reason for that, please?

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

      And now it's getting even more weird :(

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

        i know this is too late.. but i need to say something..

        When there's lot of calculation, loops pypy will be faster than python..

        and if solution relies heavily on data structure(set, dict) python will be faster than pypy..

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

    Here is 800ms solution with nlogn complexity(dsu is nlogn) solution

    I fastened the code using fastio template

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

array[j + i * m] instead array[i][j] will speed up python code

p.s. m — row size

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I like using Python a lot. Read the 3 links below, you may find them helpful:

  1. Python PerformanceTips
  2. Dict vs Lists for Graphs
  3. Only Python solution accepted so far. Had to optmize quite a bit

In short:

  1. Write your solution inside a function. Lookup variables in the global scope is more expensive, than using variables in the local scope.
  2. Avoid for loops like the plague. Favor Python builtins. Always use map, filter, concatenate strings with join, etc.
  3. Writing output is really expensive. Writting a gigantic string once, may be better than writting several small strings.
  4. Type casting is really expensive. Avoid if possible (string to int).
  5. Avoid dots. In other words: Cache function lookups. Example: Avoid using stdout.write directly, put it in a variable w = stdout.write.
  6. Careful with Dict vs Lists for graphs
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you provide link to solution where one gigantic string is printed.

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

Use this if you need recursion but recursion limit is reached (e.g. dfs/ dp). Read documentation

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it
Your code here...
import math
N=int(input())
print(int(math.factorial(N-1)/(math.factorial(11)*math.factorial(N-12))))

Sorry I always get 2 wrong in 19 test case(the other 17 test cases are correct) What's wrong with my code?Can any one teach me?Thx a lot~~

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

    Problem Link.

    When you look at the constraints carefully, it is 12≤N≤200.

    And just imagine what is even 100! is. It is 9.332622e+157.

    If you are not convinced yet, try google to search 200! and tell me if you see undefined. Means even google is not going to calculate 200!.