chickenDo's blog

Memory limit exceeded
By chickenDo, history, 5 years ago, In English

This is my solution for problem C round 61: https://mirror.codeforces.com/contest/1132/submission/58241037 I used a 2d array[N][N] (N = 5000) and a 2d vector. I think the maximum size of the vector is N*N so the memmory of array is approxiate 100MB and vector is 100MB. How could it be MTL? (200MB < 560MB). Thanks.

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

Comments Comments (2)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

You're cutting it really close to the memory limit. The memory limit is 256MB, which is 2^28 B.

an integer NxN array is 5000^2 = 25 * 10^6 = approximately 2^25 ints, which is 2^27 B. since you have an array and vector both of that size, you're near the 2^28 B limit, which is why you are triggering the memory limit error.

→ Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

One thing that may push 200MB over the 256MB limit is how vector grows when doing push_back. If vector increased the reserved size by 1 for each push_back then it would have to relocate whole vector each time and total complexity for doing N push_backs would be N^2.

Instead when vector's capacity is reached it doubles the size. Not sure if all implementations use factor 2, any other multiplier bigger than 1 would work. I doubt anyone uses more 2 as that would be waste of space. With such approach amortized complexity for N pushbacks is N. Downside is that vector might take up to twice as much memory as necessary. Waste of memory can be prevented by using either reserve or resize to get the exact size you need.

→ Reply