simp_pro's blog

By simp_pro, history, 3 months ago, In English

Problem link: https://codeforces.com/contest/1625/problem/D

Sorry for necroposting, but I didn't find any solution for this in comments or anywhere

In problem D, The editorial solution uses a trie. if you use trie. Then there are at most nlogA vertices. If we implement using pointers then its memory would be nlogA*32 (32 if because of pointer address size in 32 bit compiler) = 3*10^5*30*30 = 2.7*10^8 ~ 2 GB. But memory limit is just 256 MB. How to solve this issue?

My MLE submission

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Actually it is not 2 GB. its 354 megabytes, (I ran your code in a mashup and changed the memory limit).

I optimized your memory by freeing the memory of tries you create and it worked, in 149 MB. Here it is: 236410169

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

    What is wrong in my calculation for memory?

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 3   Vote: I like it +3 Vote: I do not like it

      I don't know, I don't even know whats your solution. I just tested it.

      Oh actually i think i figured it out. The size of pointer is just 4 bytes, instead of 32 bytes. 32 bits = 4 bytes

      We actually get 2 Giga Bits of memory which is pretty much 250 megabytes.

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

        Thank you so much. In my calculation, I am taking upper bound of memory. But in actual trie, there are a lot of colliding vertices. People who submitted using single trie got AC. But I did some casework and was creating multiple trie so I was not having much collisions.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe you can use a trie with an array and avoid this problem, i can share my implementation if you want

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

    Yes, do share. That uses same memory as normal trie. But using that would work because vectors are automatically freed.

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

      actually generally i do only one trie so i create a int[][] of a specific size, but i guess changing it to a vector wouldnt really change it. i dont have a specific implementation but ill explain it. every index in the array is an adjacency list for all possible next letters, so fe trie[2][2] is the index if you add b to the trie. and when you add to it a letter ß you check if its "pointer" is 0, if it is you make the trie bigger by 1 and update it, otherwise you go to the index that it points to