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?
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.
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
hmm .. I have tried preallocating the memory without using append but it doesn't seem to make a difference
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).
Thanks a lot, there seems to be progress, but now I'm getting a TLE for the same test case lol .. I think I will give up and rely on C++ for CF problems