Don't know why my code could get a Memory Limit Exceeded?


  • 0
    Y

    During the contest, I got 2 penalties because of a strange error: Memory Limit Exceeded. It failed at test n = 100000 when I submitted, although it still run normally when I test it with the "Run Code" button??? I also tested it on ideone (http://ideone.com/TiIZ4C) to make sure my code work normally. Finally I got the problem AC by moving two vectors outside the class. So I guess there are some problem with the way the judge program run my code, may be relevant to the stack memory.
    As this problem caused me 2 penalties and moved me from the FIRST place to the FOURTH place, i would be very appreciated if the problem setter could double check this problem again. Thank you :)

    My solution:

    class Solution {
    public:
        int magicalString(int n) {
            vector<int> a={1,2,2,1}, b;
            while(a.size()<100000){
                b.clear();
                int num=1;
                for(int i=0; i<a.size(); ++i){
                    for(int r=0; r<a[i]; ++r) b.push_back(num);
                    num=3-num;
                }
                a = b;
            }
            int res=0;
            for(int i=0; i<n; ++i) res+=(a[i]==1);
            return res;
        }
    };
    

  • 0
    Y

    Any contest setter here?


  • 1

    Hi @yen-thanh,

    After carefully considering your solution, and decide it is not a excepted solution.

    For the correct solution, we excepted you for using <queue> in this problem and pop back elements again and again.

    Since we have pointed out the range of elements in the problem description, it's too large for the stack and thus you need to process the data while you are traversing the array but not store the data.

    For your program. You could see, you cleared array b's data but not the a's data. And the space complexity is O(n) while most AC solution's space complexity is O(1).

    I know it's unfortunate to move you from the first place to the fourth place, but it's unfair for other participants to open up an additional memory space for you since many people also got MLE.

    And there maybe lots of strange feedback during the contest and interviews, what we can do is to think and try to find the causing of the problems and solve them. And that's the charming point of the contest.

    We'll have contests every week, I believe you could win your first place one day : )

    Best,
    Leetcode Team


  • 1
    Y

    Thank you for your reply. I do understand that I have done this problem in a worse way than others because I need to find out a way to implement it quickly. What I don't understand is why my code could get a MLE as the space complexity is just O(n), as you mentioned that I don't clear the a's data, but in fact after the assignment a = b it will be automatically allocated (or cleared and added with the new data) by the internal allocator (http://www.cplusplus.com/reference/vector/vector/assign/).
    The thing makes me surprised is that I got MLE despise of having tested my program with n = 100000 by the "Run Code" button and it run ok. Generally, thing like this shouldn't happen in a real contest. As my program could pass test n = 100000 with the "Run Code" button, I considered my program should run ok for all testcases and couldn't believe when it got MLE. I bet there is a problem with the way we implement the judge program, may be we forgot to create a whole new object, whole new process, or even forget to force the system to run the garbage collector before every test, or maybe we forgot to clean the object after every test case, etc,... in short I do have some experience with writing the judge program for contests like this, if we don't do it correctly it may create some strange error with the memory, sometimes I even need to make sure the user's code run on individual process/judges for every single test...

    I hope that you guys could do a deeper look in this problem and make sure that it won't happen again in the future, in another hand, I do appreciate for your effort to make this contest successful. Hope I could have a better experience when participating in this contest in the future.


  • 1

    @love_FDU_llp said in Don't know why my code could get a Memory Limit Exceeded?:

    Since we have pointed out the range of elements in the problem description, it's too large for the stack and thus you need to process the data while you are traversing the array but not store the data.

    You think vectors store their contents on the stack?

    most AC solution's space complexity is O(1).

    Can you show some? I haven't seen any.


    Also, I tested it and with "Run Code", @yen-thanh's solution not only handles n = 100,000 well, but even n = 4,000,000 (after changing the number in the code, of course).

    I myself have had trouble with MLE sometimes as well, I think the system can take an unreasonably large amount of space that's not the fault of our solutions. The system might somehow accumulate the memory over all test cases in the test suite. And I think "Last executed input" doesn't show the input where the memory was exceeded.


  • 1

    @yen-thanh Hi, I just tried running your code and it uses x3.5 of the default C++ memory limit. In other words, your solution uses around 70MB of memory while the default memory limit for C++ is around 20MB.

    Note that this has nothing to do with the stack memory, as vector is a dynamic structure which uses the heap memory.

    I recommend that you read the FAQ about how your solution is judged, the reason for this behavior is due to all test cases were run together in one process

    I tried pasting the line 100000 20 times in the custom test case and click Run Code, and it results in Memory Limit Exceeded. Base on this, my guess is the vector that's been allocated does not get freed. By the way, the C++ is run in debug mode without any optimization. I would have to dig in this deeper. Will update when I find out more. Thanks.


  • 1

    I have converted the solution to use dynamically allocated arrays, and also calling delete[] before returning from the function:

    class Solution {
    public:
        int magicalString(int n) {
            int *b = new int[104248];
            int *a = new int[104248];
            a[0] = 1; a[1] = 2; a[2] = 2; a[3] = 1;
            int aSize = 4;
            int bSize = 0;
            while(aSize<100000){
                bSize = 0;
                int num=1;
                for(int i=0; i<aSize; ++i){
                    for(int r=0; r<a[i]; ++r) {
                        b[bSize++] = (num);
                    }
                    num=3-num;
                }
                for (int i = 0; i < bSize; i++) {
                    a[i] = b[i];
                }
                aSize = bSize;
            }
            int res=0;
            for(int i=0; i<n; ++i) res+=(a[i]==1);
            delete[] a;
            delete[] b;
            return res;
        }
    };
    

    I tried running the above code with the single line custom test case of 100000, then repeat the run code again with two lines of 100000, and three lines. Here is the memory consumption:

    1. 1490944 bytes
    2. 2347008 bytes
    3. 3055616 bytes

    As you can see, the increase from 1. to 2. is about 856,000 bytes, which is also almost the same amount of memory used in allocating the two arrays (a and b) in the method: 104248 * 2 * 4 = 833,984 bytes.

    So it seems like calling delete[] does not free the memory? Doesn't seem right to me.


  • 0
    Y

    This morning, I tried to add one more line to my program if (n == 100000) return 49972; and guess what, it still got a MLE error. So I guess the judge program failed before giving the input n = 100000 to my code, maybe the judge's code itself got MLE, not my part of code...

    class Solution {
    public:
        int magicalString(int n) {
            if (n == 100000) return 49972;
            vector<int> a={1,2,2,1}, b;
            while(a.size()<100000){
                b.clear();
                int num=1;
                for(int i=0; i<a.size(); ++i){
                    for(int r=0; r<a[i]; ++r) b.push_back(num);
                    num=3-num;
                }
                a = b;
            }
            int res=0;
            for(int i=0; i<n; ++i) res+=(a[i]==1);
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.