Lakshi4h's blog

[help] Doubt about memory complexity in IOI 2010 Traffic Solution
By Lakshi4h, history, 4 years ago, In English

Today I wrote a solution for IOI 2010 Traffic

But It exceeds the memory limit.

code

Graph is a tree and has $$$n$$$ $$$(<1e6)$$$ nodes. Therefore i think the total memory will be

  • $$$n$$$ for array p

  • $$$n$$$ each for s and d arrays

  • $$$2*(n-1)$$$ for adjacency vector

  • $$$2*(n-1)$$$ for map m

Complexity is $$$O(n)$$$

But how does this exceeds 250MB? Can someone point me to my mistake.

Thank you.

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

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

You are creating an array called P several times in dp function and this causes ML.

But I guess you don't change anything inside it so I think you don't have to send the array P to the dp function.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Thank you for the reply.

    I thought i was just sending the pointer. I didn't knew it copies the array. I'll try this

    Update: It didn't work. submission

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

      Ohh sorry I didn't read it carefully.

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

      I didn't completely understand your solution but this problem can be solvable like this:

      1) City is a tree and let node 1 be the root.

      2) You can dfs the tree and collect sum of fans of subtree of node v in S[v]

      3) Let i will be the arena then the A[i] is max(S[child[1]], S[child[2]], S[child3]....TotalFan-S[i])

      4) Answer will be the minimum A[i]

      Hope this will help you

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

        Thank you.

        In a fundamental level i guess that is what I'm doing but your solution is way better. I did the same thing like a year ago and got 100 pts. Submission

        What I don't understand is how this solution exceeds the memory limit.

        → Reply