StasyaCat's blog

By StasyaCat, history, 8 months ago, In English,

I got two solutions for http://codeforces.com/contest/1036/problem/F

First one: 42893786 Second one: 42893945

First solution gets MLE, though it differs from second one only in line 81. On this line in first approach I try to use precalculated values from the array, instead of calculating them anew.

Can someone explain how a person can get MLE because of trying to get a value from an array?

Tags mle
 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it  

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In C++, this is normally due to an assert statement in C++ not returning true, but some STL elements can generate this if they try to store too much memory.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If I erase the assert statement it still does not work.

    As I told you, memory consumption by arrays/STL containers are the same in both of my solutions. It is only line 81 that matters where I try to get value from j-th elemnt of the array.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think that compiler can decrease the size of an array or remove it completely, if it understands that it will not be used.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is not the case here, because in my second 42893945 solution I both multiply the elements of the array and push_back them into the vector, so the array is actively used, but there is no MLE.