kingofnumbers's blog

[help] Strange memory limit exceeded (solved)
By kingofnumbers, 9 years ago, In English

Hello

I was trying to solve problem H in this gym contest , the problem shortly states:

given a connected graph you are required to add one edge so that the number of bridges in the graph is minimized, an edge is called bridge if and only if removing it makes the graph disconnected.

the solution is very simple , find bridges in O(n+m) then change every connected component of non-bridge edges into one node , then you will have a tree consisting of bridge edges only , then find the length of diameter of tree and subtract it from the number of bridges and this is the final answer

this algorithm is O(n+m) time and memory but when I coded it , it gave me Memory limit exceeded which is very strange since all arrays which I allocated can't be more than 256MB , here's my code which took MLE.

then I tried to code it without using structs or pointers but I used vectors, and it got AC with only 16MB memory , link to my AC code , as you can see there's big difference in memory and I have no idea what is happening.

I wrote a code that calculate the sum of number of nodes and the number of edges in all test cases of input file and the result was: sum of nodes=639884 , sum of edges=678426

any help explaining the MLE would be appreciated.

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

Comments Comments (11)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I observed the same problem when trying to index strings using trie vs map. Although trie is faster yet it takes a lot of memory and it ends up usually with MLE and I have no idea why.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    note that memory complexity of trie is O(a*s) where s is sum of strings lengths and a is alphabet size which is 26 in case of only lowercase letters are allowed, map doesn't have the alphabet factor in its memory complexity.

    this might be the reason in your case

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

First, you have provided misleading code — it differs from your only submission which gets ML in the system. I guess it's not a big deal. Wrong statement was here, my bad, I'm sorry

The main problem is that you do not understand purpose of C++ destructors. You should never call them manually, unless you're writing your own data structure which pre-allocates memory. When you create vector (or any other well-implemented C++ class) you are typically allowed to do any operations with it (including assignments, copying and so on) without any memory leaks as long as you don't create raw pointers. So, instead of:

adj[i].clear();
adj[i].~vector();
adj[i]=vector<edge*>();
adj[i].shrink_to_fit();

you should write:

adj[i].clear();
adj[i].shrink_to_fit();

or

adj[i] = vector<edge*>(); // we create a new empty vector with no preallocated memory and discard the old one

In either case the vector will be cleared to all pre-allocated memory will be de-allocated.

What happened before is what's called double free: memory is deallocated by explicitly called destructor first and then it's deallocated inside operator=. Double free is undefined behavior, possibly causing damage to memory allocator and, therefore, any kind of special effects.

After I've replaced these lines your code received runtime error, which I think can be reproduced locally.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Thanks yeputons for replying

    First, you have provided misleading code — it differs from your only submission which gets ML in the system. I guess it's not a big deal.

    no it is the same code which gave me MLE , you can resubmit it to see MLE

    When you create vector (or any other well-implemented C++ class) you are typically allowed to do any operations with it (including assignments, copying and so on) without any memory leaks as long as you don't create raw pointers

    I did that because I have read that clear method of vector doesn't destruct the struct of array elements (which is in my case edge) , I have already tried to call only clear and shrink_to_fit but I got the same MLE verdict , but yours got RTE because I temporarily changed the memory limit to 1024 MB instead of 256 MB and notice that your submission also have more than 256 MB memory.

    I guess I knew what is the problem I will write a comment explaining what happened soon

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 4   Vote: I like it +5 Vote: I do not like it

      no it is the same code which gave me MLE , you can resubmit it to see MLE

      There can be different ways of getting MLE. The submission I'm talking about is 12031262. E.g. there are differences in line int mx=-1,smx=-1; and the submission also adds some extra wrong vector clearing. My bad, irrelevant to the main question.

      I did that because I have read that clear method of vector doesn't destruct the struct of array elements

      Where have you read that? It's wrong. vector calls destructor of underlying elements.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        I have a lot of submissions with verdict MLE to this problem , each one slightly differ from others , I picked one of them and pasted it to blog but you went to my submissions and opened another one to see there's actually those differences that's what happened.

        and about the wrong information , I have read it on the internet but I don't remember where exactly because that was long time ago

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did that because I have read that clear method of vector doesn't destruct the struct of array elements (which is in my case edge)

      it is true only for pointers. For example, here you must call destructors before clearing vector to prevent memory leak:

      vector<edge*> edges = { new edge() };
for (auto& e: edges) delete e; // mandatory
edges.clear();

      (of cource in real code you should use shared pointers or whatever):

      vector<shared_ptr<edge>> edges = { make_shared<edge>() };
edges.clear(); // no leak
      → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

it seems that I forgot to reset the variable is to false of array (which is telling whether an edge is bridge or not) in the start of every test case. when I added extra line list[i].is=false the memory reduced to about 10 MB , but it is still not clear why this bug caused MLE, I tried to see what happens if non-bridge edges are considered as bridge and it seems that it causes the tree to have self-loop edges (an edge that connects a node with itself) and the self-loops causes infinite loop in nested calling dfs3 function which I think caused stack overflow.

to make sure I have tried to execute this code in custom test that is supposed to cause stack overflow

#include <iostream>
using namespace std;
int h=0;
void dfs(int nd){
	if(nd==1000000000)h=4;
	int g[5000];
	g[nd%5000]=nd+1;
	dfs(g[nd%5000]);
}

int main(){
	dfs(2);
	cout<<h;
}

surprisingly it's giving TLE with very low memory consumption , anyone can explain it?

so I think there must be another reason why forgetting it reset bridges causing MLE.

moral of story, bugs don't only cause WA, it can cause TLE , RTE and MLE too

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

    My suggestion is that it's caused by tail call optimization — optimizer can replace recursion with a loop in your code: you do nothing after the only recursive call and there is no reason to preserve local variables.

    This one successfully crashes both on my Windows laptop and in gym:

    #include <iostream>
using namespace std;
int h=0;
void dfs(int nd){
	if(nd==1000000000)h=4;
	int g[5000];
	g[nd%5000]=nd+1;
	dfs(g[nd%5000]);
	h += g[nd%5000]; // the change
}

int main(){
	dfs(2);
	cout<<h;
}
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I thought that it might be because of some compiler optimization but I'm not experienced with them so I couldn't know what exactly the optimization is doing , so I tried to make array g and using random cell to stop the optimization but it seems it was not enough. thanks for information :)

      → Reply