Pawan's blog

Why MLE when I am using less space ??
By Pawan, history, 8 years ago, In English

Link to accepted solution : Accepted

Link to MLE solution : MLE

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

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

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

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)

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

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.net/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.net/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.

      → Reply