stanislav.bezkorovainyi's blog

Strange MLE
By stanislav.bezkorovainyi, history, 6 years ago, In English

I got two solutions for http://codeforces.me/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

»
6 years 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.

→ Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years 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.

→ Reply
  • »
    »
    6 years 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.

    → Reply