Changing the spaces into dots, does not make the sample more """"illustrative"""". It does make it way less obvious what the format is, though please give me some tests.All test that I found in other topic my programm pass. When the program is launched, the database contains a single word "sun". >>If the length of the resulting list exceeds 20, then you should output the first 20 names only. So, this was my mistake, I initially ignored this statement. Trie with pointers, std::string and std::cin/std::cout gets AC in 0.31 with 10 372 KB used. time 0.078 memory 3 350 kb. I use triplex tree. It is very interesting problem. I used plain arrays and got AC in 0.093 and 410 KB. Solution with std::set and hand-written memory allocator gets AC in 0.062 and 534 KB. Where I can find info about triplex tree? I used google, but nothing found... time 0.078 memory 3 350 kb. I use triplex tree. It is very interesting problem. It's just brute-force task :) There 36 lines in my AC code versus yours 165 lines :) Edited by author 08.03.2013 19:59 thanks, now AC with set :/ It can actually be solved with trie. My solution uses 0.4s (cin) and 20MB. Just store a map in every node. Can someone tell me what's test case 8? With set, all testcases pass but with Trie, I am getting WA at testcase 8. initially, there is "sun" in the DATABASE. is file handling is necessary in this problem or not?.. I've read all posts but still do not understand what's wrong. my solution: -ignores names mentioned twice -output 2 spaces, but not points -outputs only 20 first names -consists of 'sun' in the beginning can anyone please give any tests or hints? Edited by author 08.10.2012 08:31 Edited by author 08.10.2012 08:31 try +sun1 +sun2 +sun3 ... +sun20 ?sun Answer: sun sun1 .... sun19 Or change 20 to 3 for testing. Deleted, my mistake Edited by author 22.06.2014 14:36 try +sun1 +sun2 +sun3 ... +sun20 ?sun Answer: sun sun1 .... sun19 this is not right.. I got AC using Trei and the correct answer is sun sun1 sun10 sun11 ... sun9 I have "Time limit exceeded" in test #12. But time of work is 0.234. Max time in test conditionы is 2.0. I think it is mistake in data reading. Maybe program waits reading data from test. do { var operation = Console.Read(); var request = Console.ReadLine(); ... } while (Console.In.Peek() != -1); Edited by author 12.04.2014 18:28 Edited by author 12.04.2014 18:28 How to solve this problem in 0.5 sec? I have used simple brute force algo - qsort strings every time I needed it, and have used strings hashes for comparison. I got AC in 3,2 sec Straightforward N*log(N) solution is building AVL or R/B tree of strings. But a simpler implementation is sort all input +xxxxx strings (along with "sun") and replace AVL tree with interval tree on which string indices have already been added. Edited by author 17.08.2008 23:47 Another solution is building characters tree, so that paths to terminal nodes correspond to existing strings. First-child & next-sibling indexation will suit memory limit. I also accepted it using AVL tree, but first i tried characters tree. IMHO this solution can't pass memory limit because of many pointers in tree. C++ optimizations haven't helped me. I get 0.125 with not optimal solution, admins, change 10^4 to 10^5, it is cool problem.... First i tried to use character tree - MLE. Then i tried to use character tree with pointers "firstChild" and "nextSibling" in nodes - MLE. Then i realized that i can try to try forcing GC in Java, but it TLE. After all, just for fun, tried with TreeSet and own MyString class... AC 3.6 o_O Just wonder, how people solve this task on Java in 0.2s and 2MB. It seems like they use plain arrays of chars 20*100000. I use sqrt decomposition and get 0.093 sec Edited by author 26.10.2013 12:03 Edited by author 26.10.2013 12:03 Give me please 3 (third) test. I've tested with other tests from this forum - all works fine, but I have WA#3 problem... I rewrote my solution - got time limit on 10th test - good, but I think it's may be bug (or feature?) in 3 test (because i changed only 1 feature in input/output code). Can anyone give me this (3) test? Edited by author 30.08.2011 06:23 Edited by author 30.08.2011 06:26 Time limit is changed from 4 to 2 seconds. First test is changed to the sample. Submissions are rejudged. Несмотря на то, что задача просто решеется с помощью std::set, я написал сжатый бор. Первый раз писать немного сложно, но весело. А теперь ещё и просто. а если в вершинах бора хранить не map<string, node*> а попроще map<pair<int, int>, node*>, то я думаю результат был бы более впечатлительным P.S. решайте сжатым бором Accepted 0.312 2 904 КБ Edited by author 11.01.2012 15:06 Pff, too easy with just map<string, bool>. 0,937s is enough. Hi, I am getting runtime error on test 1 using C#. No reason is given in brackets. Any idea why this may be happening? Is it possible to solve this problem using suffix tree? or it will get MLE? I solved it with std::set. Just use lower_bound() and upper_bound() functions. Applying lower_bound() is quite straightforwardly(yourSetObject.lower_bound(string)), but upper_bound() requires additinal {max_word_len-string.len} 'z' symbols. Read documentation and you will understand why. That's all! I am using C# and dont really know if there is something like lower_bound(), thats why I am asking about suffix tree/array :) I think that my program is corect, but WA#1, WHY??? I print 2 spase before every star Before work, base have one star-'sun' Sample and my easy test is work correct I use sort and binary search I don't know, why my program have WA#1, please help!!!! Edited by author 25.05.2007 18:40 Try this +b1 +b2 +b3 +a1 ?b Output is b b1 b2 b3 Hi, i'm having problems with the input of this task. How does my program know when the input is over? It would be very helpful if you could give me a code sample (only the input, not the actual task :) ). Something like: #what libraries the input needs while(way to know the input is over) { way_to_read (scanf, cin ...something else?) } Thanks, I believe if i get this part, the rest will work first time :) char s[1000]; while (scanf("%s", s) != EOF) { .... } Edited by author 19.09.2007 21:04 while(scanf("%s", s) == 1) Edited by author 17.08.2008 23:53 Tried to use STL (map, vector), but get TL11. Please, give me idea, how to use in this problem triple tree? Can't find any algorithms. Thank you! Edited by author 27.10.2007 23:49 |
|