11488 - Hyper Prefix Sets

[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.

[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.

[annhy]

Thanks quol.
It is a very useful information.

I was too angry to remember trying about this during the contest.

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.

[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

[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?

[annhy]

I don't know how to solve this problem. Any hints?

I solved it by a 'trie' structure.
Good luck!

[andmej]

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.

[annhy]

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