AC 3,2 sec. How to get 0,5 sec?
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
Re: AC 3,2 sec. How to get 0,5 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
Re: AC 3,2 sec. How to get 0,5 sec?
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.
Re: AC 3,2 sec. How to get 0,5 sec?
Posted by
Eternal 23 Nov 2008 02:24
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.
Re: AC 3,2 sec. How to get 0,5 sec?
Trie
Re: AC 3,2 sec. How to get 0,5 sec?
I get 0.125 with not optimal solution, admins, change 10^4 to 10^5, it is cool problem....
Re: AC 3,2 sec. How to get 0,5 sec?
Posted by
JTim 19 Jan 2011 06:38
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.
Re: AC 3,2 sec. How to get 0,5 sec?
Posted by
bayram 26 Oct 2013 12:02
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