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

Автор motatoes, история, 7 лет назад, По-английски

I'm trying to solve the python indentation problem in round 455C. My submission is receiving a memory limit exceeded.

Memory limit is: 256 * 1024 * 1024 = 268435456 bytes

In my code I am using at most a 5000*5000 matrix to hold the dp values and this will occupy ~ 200000064 bytes

I am also using a string to hold the program and it will occupy: 5049 bytes

I am using about 6 int variables in my program and then will occupy: 6 * 28 = 168 bytes

so in total: 200005281 bytes

Or 191 MB. So According to my calculations I am still bellow 200 MB, but in CF I am exceeding 256MB. Is there something that I am missing in the memory computation? Is the python interpreter size counted within the memory computation also?

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

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Because in Python not all elements have to be of the same type, Python has to keep some additional information about the elements. Usually Python is considered a language which uses lots of memory because of it's flexibility.

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

One point: You are creating the matrix by appending which can lead to higher memory usage, read this: https://stackoverflow.com/questions/7247298/size-of-list-in-memory

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

    hmm .. I have tried preallocating the memory without using append but it doesn't seem to make a difference

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

      Okay, another idea (which also fits that this happens only after 1.5s): The values grow large and python starts switching to arbitrary precision integers whose size is unbounded. Maybe you can fix this by taking modulo earlier (in every step).