Hallo all!
I think here is only one solution for this problem.
First of all  sort incoming data in alphabetical order. Then choose words in second array. sort it by frequenscy. Take first  10 words and print them. And do not forget to sort word's with same frequency alphabeticaly. That's All.
But when I implement whis algoritm it slove my test, slove test coming with problem, nevertheles it cannot pass first test at server.

Can U advise me some other ways how to slow this problem.
lbvf(dog)mail(point)ru

All the Best to U...

My algorithms is the same, but TLE on test 12

Maybe a main problem in sorting? I had WA 12

Hash codes of strings and qsort can help to increase speed of sorting, I think. I got TLE12, and don`t have a time during contest to rewrite my program. Maybe later I`ll try to solve it again.

I was using qsort. And testing how it sorts simple incoming data by the  debuger, it was testing normaly. It's looks pretty mistical... I can belive in TLE, but WA in first test looks very strange.

To find a problem at my code I want to create testing porgram that counts words in big Engish book. And then test A program on created test data.

What kind of Hash codes did U use?

I think your output file has one more empty line, when I had such code I had WA1, now I'm one of the many TL12- ers :(

I built characters tree for request and almost beaten the top with it ))

Really good hint! Thanks!

Also this problem can be solved with segment tree and some preprocessing:

1) create array of pairs <string word,int frequency> and sort this array

2) build segment tree on maximum on frequences of sorted array

3) answering the query:
find all words which matches the pattern - these words will be in one sequental interval because array sorted lexocographically,here example of finding this interval:
L = lower_bound(array,array+n,make_pair(pattern,-INF))-array; //substraction pointers
R = upper_bound(*,*,make_pair(pattern+"zzzzz_fill_until_max_len",+INF))-array;
now we found all relevant words, let's choose 10 most frequent:
1 most frequent word - find_max_with_segment_tree(L,R) - also should return index of maximal element
Now you should change maximal element to -INF in order to provide that second most frequent word will be founded by segment tree; change second to -INF and so on;
after answering 10 questions just undo changes: you know old values and indices of altered elements, use this this information and restore segment tree.


Edited by author 11.02.2011 08:31