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?
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
What is wrong in my calculation for memory?
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.
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.
Maybe you can use a trie with an array and avoid this problem, i can share my implementation if you want
Yes, do share. That uses same memory as normal trie. But using that would work because vectors are automatically freed.
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