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

How competitive is PyPy 64-bit?
Автор tomowama, история, 2 года назад, По-английски

I am rather new to CP, and am curious that now that there is PyPy 64-bit on Codeforces, how much more competitive does that make python? I have seen in other blog posts on here that one of the main things slowing down python (PyPy) was the fact that >32 bit integers were being stored as big ints. Does this change make Python more competitive and actually usable? I only ask because I know c++ and python (I know python better than c++ as I've only recently been using c++ for cp), but can code solutions to problems much faster and "cleaner" in python.

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

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

PyPy is fairly competitive. I solve most problems with PyPy and I know that others do too, such as pajenegod.

However, there are issues with problems with tight time limits where pythonic Python isn't fast enough and you have to use crab-Python, which can take some time to learn. Techniques in crab-Python involve flattening multidimensional lists to 1 dimension and manually performing index arithmetic, packing tuple elements into 64-bit ints before sorting because sorting ints is 10x faster than sorting tuples, finding ways to avoid dicts and sets, coping with the lack of balanced search trees (segment trees are nice if you can afford the space), and programming recursion with an explicit stack because recursion is too slow.

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

    shoutout to kclee2172 for being a Python god

    → Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Sounds difficult. Is it really still simpler than C++?)

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

      It depends on how stubborn you are.

      A good skill to have is to be able to judge from the limits and your expected solution whether you might experience issues with the time limit in Python. When this is the case you can opt to use C++ instead of Python.

      Generally I find that Python solutions are shorter and therefore faster to type than C++ solutions, which is why I prefer it.

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

Up to the rank of specialist, which is the highest I reached, you can use python without any major concerns, although there are a few things you have to take into account:

  • You need to use fast input if the problem requires you to read over 10⁵ elements and integer values up to 10⁹, otherwise your solution will probably get a TLE. You can use a template and forget about it.

  • If you use a dictionary and integers can be up to 10⁹ your solution can be hacked see https://codeforces.net/blog/entry/101817.

  • You can't generally use recursion.

  • Sometimes I've missed a balanced search tree although I have been able to use a BIT.

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

    Thank you for your response!

    so you can’t really use normal dictionaries for large ints?

    since you aren’t using recursion, how are you handling tree algorithms?

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

      Sometimes recursion will work, it will depend on the constraints of the problem, but you have to be aware more often than not it will be too slow.

      Truth is you won't face many tree problems at those ranks, I only recall a D problem in a DIV3 contest, anyways for a tree if you want a inorder or postorder traversal you can use a stack to emulate the recursion, if you want a preorder traversal you can use a deque.

      → Ответить