ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1414. Astronomical Database

AC 3,2 sec. How to get 0,5 sec?
Posted by Beksinski 22 Jan 2008 01:47
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?
Posted by Denis Koshman 17 Aug 2008 23:46
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?
Posted by Denis Koshman 17 Aug 2008 23:52
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?
Posted by gvsmirnov 3 Oct 2009 05:36
Trie
Re: AC 3,2 sec. How to get 0,5 sec?
Posted by Vit Demidenko 4 Oct 2010 18:34
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