1254 - Top 10

All about problems in Volume 12. 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
sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

1254 - Top 10

Post by sith » Wed Nov 07, 2012 7:53 am

Hi

I am using prefix tree to solve this task, but got TLE,
(I am using java)

Is it not enough fast?

Code: Select all

AC
Last edited by sith on Sat Nov 10, 2012 7:34 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1254 - Top 10. Why TLE?

Post by brianfry713 » Wed Nov 07, 2012 10:28 pm

My C++ code is AC in 1.7 sec. I first sort the dictionary in this order:
The words with shorter length come first, if they have equal length then
The lexicographically smaller words come first, otherwise
The words with smaller label come first.

Then for each query iterate through the dictionary until you have up to the top 10. I use std::string::find to see if the word contains the substring.
Check input and AC output for thousands of problems on uDebug!

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 1254 - Top 10. Why TLE?

Post by sith » Sat Nov 10, 2012 7:33 am

I've got AC.

But I think that this approach is not optimal. We make a lot of substring operations.
Suffix tree would be better, but my first implementation has O(n^2) to init the tree, I believe because of that I've got TLE

flashion
New poster
Posts: 17
Joined: Thu Jul 24, 2014 10:29 pm

Re: 1254 - Top 10

Post by flashion » Mon Sep 15, 2014 5:49 pm

Can I have some tests, please?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1254 - Top 10

Post by brianfry713 » Mon Sep 15, 2014 8:39 pm

http://www.udebug.com/UVa/1254
Click "Random Input", "Go!".
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 12 (1200-1299)”