visheshgautam.official's blog

How can we avoid memory limit execeeded errors?
By visheshgautam.official, history, 19 months ago, In English

In this submission :https://codeforces.net/contest/1775/submission/207782995 I am getting MLE i have scartched my head for hours and its still not resolving,can any comrade help this noob?

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

Comments Comments (6)
| Write comment?
»
19 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

(I think maybe you have read the tutorial and trying to do the same thing.)

I just take a quick look. The problem seems to be that there are too many edges. When you build the graph, it's enough to consider only prime factors instead of all the factors because if two numbers have the same common factor, they must have a common prime factor.

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

    can you tell me in which cases MLE errors usually occur i have done that editorial thing still mle

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

      With $$$n$$$ nodes, in the worst case your graph has $$$O(n^2)$$$ edges. This means you can potentially have over $$$10^{10}$$$ values in your adjacency list. Multiplying that by 4 bytes per int, this far exceeds the 256MB memory limit.

      Try to implement an algorithm that does not construct this adjacency list.

      → Reply
    • »
      »
      »
      19 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      (What you are going to do is to construct a bipartite graph that one part represents the really nodes and the other stands for prime factors.)

      Ya, it seems you only add prime factors (Maybe you should check yourself again). However, you don't need an entry for composite numbers. I think it may pass after getting rid of it.

      UPD: I have tried my own and got AC. Here is the code. https://codeforces.net/contest/1775/submission/207871816

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

      Even if you just simply add 3e5 nodes, it'll still pass and is quite lower than the limit. https://codeforces.net/contest/1775/submission/207875652

      I found another problem in your code. Why the number of entries is (2*M)+1? What if M is small? Maybe it tried to use some unitializated memory as a vector due to out-of-bound access and caused a unexpected behavior which allocated a lot of memory. (I'm just guessing.)

      → Reply
»
19 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Just don't submit the code:)

→ Reply