Блог пользователя visheshgautam.official

How can we avoid memory limit execeeded errors?
Автор visheshgautam.official, история, 18 месяцев назад, По-английски

In this submission :https://mirror.codeforces.com/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?

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

»
18 месяцев назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

(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.

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

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

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

      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.

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

      (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://mirror.codeforces.com/contest/1775/submission/207871816

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

      Even if you just simply add 3e5 nodes, it'll still pass and is quite lower than the limit. https://mirror.codeforces.com/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.)

      → Ответить
»
18 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Just don't submit the code:)

→ Ответить