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 1393. Average Common Prefix

To admins: Time Limit in Java
Posted by crdp 19 Sep 2007 21:59
I wrote an O(n*log(n)) algorithm, but have got a TL.
I think this is a problem of Java language (there are arrays and garbage collector due to small memory limit).
And I saw that there is no AC on this problem using Java.
Can You change time-limit for Java on this task?
We have a java solution that works 2.0 sec (-)
Posted by Vladimir Yakovlev (USU) 20 Sep 2007 15:53


Edited by author 20.09.2007 15:54
Re: We have a java solution that works 2.0 sec (-)
Posted by Denis Koshman 7 Aug 2008 14:55
If it's N*log(N) due to sorting, you can implement it at O(N) via bucket sorting. Bucketing array can be filled at O(N) along with list of non-empty buckets. Later this list can be used for O(N) sorted array traversal and for fast cleanup before further sorts.