Блог пользователя mblazev

Why does my solution not MLE on worst test but MLE on a seemingly less bad test?
Автор mblazev, история, 6 лет назад, По-английски

My hacked solution: https://codeforces.me/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.

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

git gud and solve it without 255MB of memory

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Or maybe

      for (int j = l[i]; j <= r[i]; ++j)
    if( v[j].size() < 3 ) v[j].push_back(i);
      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 :))

        → Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

c1729 is more powerful than compiler optimizations :orz:

→ Ответить