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

Why MLE when I am using less space ??
Автор Pawan, история, 7 лет назад, По-английски

Link to accepted solution : Accepted

Link to MLE solution : MLE

Irony is Accepted solution uses more memory than MLE one ! :P

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

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

I guess the problem is array jaroori which has size up to N in your solution, but it's clearly contains some info about edges, so should be up to M (or N * N as from and to)

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

    Thanks for pointing it out ! i believe it should give me segmentation fault rather than MLE !

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

      Well, technically it's undefined behavior, so anything could happen =)

      Also if you enable some compiler options (like address sanitzer) it should catch this kind of issue. Check this post http://codeforces.com/blog/entry/15547. It could help to catch this kind of bugs locally (if you actually do proper testing locally, if not then start doing ;)).

      If you want to understand what exactly going on in your case you can take a look at disassembly: https://godbolt.org/g/sYE6qJ

      So it seems that layout for data is jaroori and then parent. So potentially what could happen that you will override some of the parent's value and create a loop, e.g. parent[0] = 1, parent[1] = 0 and then you'll have unbounded recursion. Stack size limit for G++ is 256MB (according to http://codeforces.com/blog/entry/79).

      So you have some memory allocated besides that + you probably almost hit stack size limit and got MLE before you've got RTE due to stack overflow.

      Could be something else, but you can investigate further on your own.

      → Ответить