### simp_pro's blog

By simp_pro, history, 3 months ago,

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

• 0

 » 3 months ago, # |   0 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 →   0 What is wrong in my calculation for memory?
•  » » » 3 months ago, # ^ | ← Rev. 3 →   +3 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 bytesWe actually get 2 Giga Bits of memory which is pretty much 250 megabytes.
•  » » » » 3 months ago, # ^ |   0 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, # |   0 Maybe you can use a trie with an array and avoid this problem, i can share my implementation if you want
•  » » 3 months ago, # ^ |   0 Yes, do share. That uses same memory as normal trie. But using that would work because vectors are automatically freed.
•  » » » 3 months ago, # ^ |   0 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