Page 1 of 1

11488 - Hyper Prefix Sets

Posted: Sat Sep 13, 2008 7:11 pm
by annhy
It is in the contest time now.
I want to complaint about the unfair time limit.
My Java code just read in the input data without doing anything, then it gives me TLE. :evil:

This problem is highly I/O bound.
If the C/C++ code needs 0.8 second, then the Java code needs at least 5 seconds.

Re: 11488 - Hyper Prefix Sets

Posted: Sun Sep 14, 2008 12:10 am
by quol
Yeah, I had the same problems with Java on that one.
I spent about 2 hours trying to optimize my solution, but kept getting TLE, until i finally realized it timed out because just reading the input would already take more than 2 seconds.

But the problem is still solvable using Java, after I used BufferedReader instead of Scanner, my code ran in 1.5s.

Re: 11488 - Hyper Prefix Sets

Posted: Sun Sep 14, 2008 4:20 am
by annhy
Thanks quol. :)
It is a very useful information.

I was too angry :evil: to remember trying about this during the contest.
quol wrote:But the problem is still solvable using Java, after I used BufferedReader instead of Scanner, my code ran in 1.5s.
By applying your advise, I get AC in 1.7s.
So your code is really highly optimized. :wink:

Re: 11488 - Hyper Prefix Sets

Posted: Mon Sep 15, 2008 2:38 am
by annhy
Hi, quol:

Would you please kindly take a look on another strange error by using Java.
I even cannot read the input without making 'Runtime error'!!! :-?

11403 - Binary Multiplication
http://acm.uva.es/board/viewtopic.php?f ... =15#p96742

Re: 11488 - Hyper Prefix Sets

Posted: Mon Sep 15, 2008 5:47 am
by andmej
I don't know how to solve this problem. Any hints?
I think the first step is to sort the given strings, but then I don't know what to do. Is O(n^2) fast enough to pass the time limit or is a better algorithm needed?

Re: 11488 - Hyper Prefix Sets

Posted: Mon Sep 15, 2008 8:05 am
by annhy
andmej wrote:I don't know how to solve this problem. Any hints?
I solved it by a 'trie' structure.
Good luck!

Re: 11488 - Hyper Prefix Sets

Posted: Mon Sep 22, 2008 7:35 pm
by andmej
annhy wrote:
andmej wrote:I don't know how to solve this problem. Any hints?
I solved it by a 'trie' structure.
Good luck!
Hello annhy,

I can see an O(n^2) solution using a trie. For each string in the input, "walk it down" in the trie, updating the best answer found so far. This would take around 50000*200 =10 million operations in the worst case, which I think wouldn't run fast enough. Is this how you solved this problem? or is there a faster algorithm?

Thanks a lot for your help.

Re: 11488 - Hyper Prefix Sets

Posted: Fri Sep 26, 2008 4:44 am
by annhy
andmej wrote:Hello annhy,

I can see an O(n^2) solution using a trie.
... deleted ...
Is this how you solved this problem?
My algorithm runs in O(n) by using a trie, not O(n^2).
Therefore the overall time is T * 200 * O(n).

Maybe you should avoid some unnecessary operations.
Good Luck!!