How to solve this problem in 0.5 sec? I have used simple brute force algo - qsort strings every time I needed it, and have used strings hashes for comparison. I got AC in 3,2 sec

Straightforward N*log(N) solution is building AVL or R/B tree of strings. But a simpler implementation is sort all input +xxxxx strings (along with "sun") and replace AVL tree with interval tree on which string indices have already been added.

Edited by author 17.08.2008 23:47

Another solution is building characters tree, so that paths to terminal nodes correspond to existing strings. First-child & next-sibling indexation will suit memory limit.

I also accepted it using AVL tree, but first i tried characters tree. IMHO this solution can't pass memory limit because of many pointers in tree. C++ optimizations haven't helped me.

Trie

I get 0.125 with not optimal solution, admins, change 10^4 to 10^5, it is cool problem....

First i tried to use character tree - MLE.
Then i tried to use character tree with pointers "firstChild" and "nextSibling" in nodes - MLE.
Then i realized that i can try to try forcing GC in Java, but it TLE.
After all, just for fun, tried with TreeSet and own MyString class... AC 3.6 o_O
Just wonder, how people solve this task on Java in 0.2s and 2MB. It seems like they use plain arrays of chars 20*100000.

I use sqrt decomposition and get 0.093 sec

Edited by author 26.10.2013 12:03

Edited by author 26.10.2013 12:03