ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1542. Автодополнение

Other ways of solution
Послано Dima&Dima 21 апр 2007 18:05
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...
Re: Other ways of solution
Послано Mingfei_Li 21 апр 2007 19:32
My algorithms is the same, but TLE on test 12
Re: Other ways of solution
Послано Molochiy Ivan[ Lviv NU ] 21 апр 2007 20:17
Maybe a main problem in sorting? I had WA 12
Re: Other ways of solution
Послано Mace[Lviv Polytechniс NU] 21 апр 2007 22:39
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.
Re: Other ways of solution
Послано Dima&Dima 22 апр 2007 12:29
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.
Re: Other ways of solution
Послано Dima&Dima 22 апр 2007 12:31
What kind of Hash codes did U use?
Re: Other ways of solution
Послано Todor Tsonkov 22 апр 2007 14:13
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 :(
Re: Other ways of solution
Послано Denis Koshman 15 июл 2008 00:37
I built characters tree for request and almost beaten the top with it ))
Re: Other ways of solution
Послано KALO 11 фев 2011 03:51
Mace[Lviv Polytechniс NU] писал(a) 21 апреля 2007 22:39
Hash codes of strings and qsort can help to increase speed of sorting

Really good hint! Thanks!
Re: Other ways of solution
Послано Baurzhan 11 фев 2011 08:29
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