11488 - Hyper Prefix Sets

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
annhy
New poster
Posts: 40
Joined: Sun May 27, 2007 1:42 am
Location: Taiwan

11488 - Hyper Prefix Sets

Post by annhy » Sat Sep 13, 2008 7:11 pm

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.

quol
New poster
Posts: 3
Joined: Sat Sep 13, 2008 11:53 pm

Re: 11488 - Hyper Prefix Sets

Post by quol » Sun Sep 14, 2008 12:10 am

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.

annhy
New poster
Posts: 40
Joined: Sun May 27, 2007 1:42 am
Location: Taiwan

Re: 11488 - Hyper Prefix Sets

Post by annhy » Sun Sep 14, 2008 4:20 am

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:

annhy
New poster
Posts: 40
Joined: Sun May 27, 2007 1:42 am
Location: Taiwan

Re: 11488 - Hyper Prefix Sets

Post by annhy » Mon Sep 15, 2008 2:38 am

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

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11488 - Hyper Prefix Sets

Post by andmej » Mon Sep 15, 2008 5:47 am

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?
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

annhy
New poster
Posts: 40
Joined: Sun May 27, 2007 1:42 am
Location: Taiwan

Re: 11488 - Hyper Prefix Sets

Post by annhy » Mon Sep 15, 2008 8:05 am

andmej wrote:I don't know how to solve this problem. Any hints?
I solved it by a 'trie' structure.
Good luck!

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11488 - Hyper Prefix Sets

Post by andmej » Mon Sep 22, 2008 7:35 pm

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.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

annhy
New poster
Posts: 40
Joined: Sun May 27, 2007 1:42 am
Location: Taiwan

Re: 11488 - Hyper Prefix Sets

Post by annhy » Fri Sep 26, 2008 4:44 am

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!!

Post Reply

Return to “Volume 114 (11400-11499)”