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.

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

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.

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