3905's blog

Educational Round Problem
By 3905, history, 8 years ago, In English

Hello my submission for the problem http://codeforces.net/problemset/problem/691/D gets MLE while I have seen similar solutions getting passed using lesser memory.Can someone explain what is the reason behind it. My submission http://codeforces.net/contest/691/submission/19745411 & other similar solutions are http://codeforces.net/contest/691/submission/19081882 & http://codeforces.net/contest/691/submission/19274092 & http://codeforces.net/contest/691/submission/19107997. Thanks!

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by 3905 (previous revision, new revision, compare).

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

All other submissions use some kind of structure — arrayList or queue and you use recurrence, which may cause stack overflow and that's probably what happens, if you change your code to use structures it should be okay.

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

    I am also using ArrayList structure.I don't understand what you mean by recurrence.Is that it in dfs?Every submission in dfs have used recurrence structure.

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

      Two of those submissions use bfs not dfs so they have no problem with recurrence stack, I resubmitted the one with dfs and it barely passes the test your code is failing on, I personally would still rewrite that method, because recurrence DFS may cause problems like that, even if it's not the case here. The other thing I see you're initializing vertex and values lists n times, that may also cause some memory problems.

      → Reply