Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Страница 1 |
Unclear problem statement | Denis Koshman | 1542. Автодополнение | 12 авг 2011 19:08 | 3 |
1) What should be output when there are no words starting with input string? 2 successive empty lines in the output are weird, so I ask. 2) If input contains some word exactly as it is, should I place this word in the output? I.e. does the verb "start" allow equality as well? Ok, my AC solution treats equal strings as starting and it will output two blank lines in case of empty result between two non-empty ones. What about ten empty results between two non-empty ones? |
Very strange test 21 ! Anyone can comment | Reflective | 1542. Автодополнение | 19 мар 2008 09:19 | 2 |
i make stupid mistake Edited by author 19.03.2008 09:20 |
Interesting mountain for climbing up(1542) | svr | 1542. Автодополнение | 15 июл 2008 00:34 | 3 |
Now I am at Bottom with 3 cec. The top has 0.25 cek. Now it's difficult to imagine what technicue they used. Edited by author 04.07.2007 14:39 Edited by author 04.07.2007 14:40 I got AC in 0.453, using Hash method. I think that's faster then sorting + binary search, because i got TLE with this metod. Hashes are faster and more easy to implement (for me..) I got 0.281 with characters tree on requests. And just 4Mb as well :) |
WA #11 | Rafal | 1542. Автодополнение | 26 авг 2009 00:16 | 2 |
WA #11 Rafal 24 май 2007 12:09 Hi. Any hints regarding this test? All my samples work correctly... Thanks! Re: WA #11 Pavel Khaustov [Tomsk PU] 26 авг 2009 00:16 |
any hint about how to avoid MLE? | fOrgIvE | 1542. Автодополнение | 3 май 2011 15:40 | 4 |
My old prob got AC before rejudge, but MLE 21 now, I tried to make it better but failed. Any hint? There are less requests than words |
To admins (-) Some bugs. | UdSU: Ajtkulov, Kotegov, Saitov | 1542. Автодополнение | 6 май 2007 00:49 | 2 |
Our earlier solution that have AC now gots TLE#21. But in status this problem is AC. We know people with same bugs. Whats happens? May be you should rejudge this problem. Some new tests have been already added and some more will be added soon. Then the problem will be rejudged. You may be sure that your old submit will lose AC verdict if the same code couldn't get AC now. Edited by author 06.05.2007 21:25 |
ANSWER ME!!!! Why it may be WA on test 12? | IGOR_Lviv NU | 1542. Автодополнение | 28 апр 2007 23:36 | 3 |
I think my algo is correct? Maybe mistake in output? Give me some tests. can you send to me yur source at tabledott@gmail.com, I'm also stuck at test12 Its true that there are several identical input lines in test 12!!! Did you notice that? e.g. 2 a 10 b 12 4 a b a b |
What is test 12? I always get WA on it! | IGOR_Lviv NU | 1542. Автодополнение | 24 апр 2007 20:32 | 3 |
try 20 words with like a****** with the same freqency or try this test 3 asd bfs dfs 2 d d My progarm works nice on this test, but I have WA. Can someone give me more tests? Pls... |
Test 10 | ★Perfez★ | 1542. Автодополнение | 24 окт 2010 20:05 | 3 |
If you print more than 10 lines per query you will get WA on this test. Edited by author 21.11.2010 17:40 |
If somebody can help... | Mihalcea Maricel | 1542. Автодополнение | 23 апр 2007 09:35 | 2 |
I also used preprocesing... and for all my examples it works... why can't it pass test 1 ?!?!?!?! It's because you put empty line in the end of output. Edited by author 23.04.2007 09:36 |
Maybe someone know what TEST 11 is special for?(+) | CF# /*Anoshin,Sotov,Khuramshin*/ | 1542. Автодополнение | 8 май 2007 22:00 | 2 |
And what if there is no words in dictionary which are started with some given prefix? What should I output? Edited by author 22.04.2007 22:32 Edited by author 08.05.2007 22:00 It's first big test. And i had WA because my RadixSort and BinarySearch were wrong, so test 11 isn't special. |
WA11 give me some test please (+) | Alias (Alexander Prudaev) | 1542. Автодополнение | 3 май 2007 19:01 | 6 |
description of output is not clearly enough, I think i have WA11 because of it what should i output for such test? 2 a 3 b 2 3 x a z But what is a real answer for this test? Answer should be: [empty line] a [empty line] I had WA11 becouse I handled multiple equal queries incorrectly My AC prog writes: a [empty line] 2admins: please dont' rejudge it :) you have to describe output format more clear |
PLease, give me some tests | Antikr | 1542. Автодополнение | 22 апр 2007 19:07 | 1 |
I've got WA5 ad I do'nt imagine what is the problem. |
Crash (access violation) on test #7 | Itania | 1542. Автодополнение | 22 апр 2007 00:28 | 1 |
Crash (access violation) on test #7 - what is wrong? Help. write, please, test #7. |
Other ways of solution | Dima&Dima | 1542. Автодополнение | 11 фев 2011 08:29 | 10 |
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. 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 )) Hash codes of strings and qsort can help to increase speed of sorting 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 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. |
N log^2 N - TLE | Crazy_serbs | 1542. Автодополнение | 22 апр 2007 16:42 | 7 |
Hi, i coulnd't find anything better than N log^2 N solution for this taks, but it gives me TLE at 12 test case. Any hint for better approach? all strings are up to 15 characters long, so i used preprocessing for each of the length Mine is O( NlogN + MlogM + (N*15)logM ). It still got AC , and of course , not so fast ( ~ 2.8 s ). It can be faster but that's enough. I think you should optimize your code . Your complexity is fast enough. Is it smart search on the tree or I can use binary search with some precalculations? Can you explain in details the preprocessing of the strings ? for each _len_ length of a string sort the original array using following ordering: 1. first _len_ chars of a string 2. number of times it is encountered, desc 2. whole string I do the same but still have TLE on this server :( Although my computer process any test within 2.6 s Edited by author 22.04.2007 16:48 |
No subject | levani | 1542. Автодополнение | 21 апр 2007 15:28 | 1 |
|
WHy WA? | woaiduanduan | 1542. Автодополнение | 21 апр 2007 14:57 | 1 |
WHy WA? woaiduanduan 21 апр 2007 14:57 |
No subject | levani | 1542. Автодополнение | 21 апр 2007 16:46 | 5 |
what do yuo want? Edited by author 21.04.2007 15:31 Edited by author 21.04.2007 15:31 I need hep too! WA #7. Can`t you give me some test data, please! What is test#1? Help me please. I going крейзііііііііііііііііііі Sample (-) Vladimir Yakovlev (USU) 21 апр 2007 16:46 |
What must I output if the letter, entered by the user, isn`t met in sequence? | Rakovets Alex | 1542. Автодополнение | 15 июл 2008 00:38 | 5 |
Just an empty separator line (and only if there are more requests following). |