mblazev's blog

Why does my solution not MLE on worst test but MLE on a seemingly less bad test?
By mblazev, history, 6 years ago, In English

My hacked solution: https://mirror.codeforces.com/contest/1132/submission/50838954

On the worst possible test (test 52):

5000 5000
1 5000
...
1 5000

It just barely passes with >255 mb used. Memory usage is high beceause I fill all of those 5000 vectors with as much as data possible. However, a slightly different test (generated hack):

5000 5000
(randomly choose 1 or 2) 5000
...

Causes MLE. How could this be? Is it possible that generator affects memory usage? It MLE on that same hack upon resubmit though.

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

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

git gud and solve it without 255MB of memory

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

    If only I had written short instead of int I would have been purple now :( So sad. I even considered that memory would be issue but it didnt occur to me to use short to be on the safe side.

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

      Or maybe

      for (int j = l[i]; j <= r[i]; ++j)
    if( v[j].size() < 3 ) v[j].push_back(i);
      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You mean < 3. That also needs to be distinguished because i can remove 2 painters. But yeah. Learning to be more careful the hard way :))

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

c1729 is more powerful than compiler optimizations :orz:

→ Reply