| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| Страница 1 |
| Идея | ibra (TNU) | 1414. Астрономическая база данных | 12 фев 2013 21:25 | 2 |
Идея ibra (TNU) 11 янв 2012 15:04 Несмотря на то, что задача просто решеется с помощью std::set, я написал сжатый бор. Первый раз писать немного сложно, но весело. А теперь ещё и просто. а если в вершинах бора хранить не map<string, node*> а попроще map<pair<int, int>, node*>, то я думаю результат был бы более впечатлительным P.S. решайте сжатым бором Accepted 0.312 2 904 КБ Edited by author 11.01.2012 15:06Re: Идея Andrew Sboev [USU] 12 фев 2013 21:25 Pff, too easy with just map<string, bool>. 0,937s is enough. |
| WA#3 ? | Evgeniy | 1414. Астрономическая база данных | 31 авг 2013 22:21 | 3 |
WA#3 ? Evgeniy 30 авг 2011 04:55 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 Re: WA#3 ? Anton Chaplygin [Kungur][USU][Psych Up club] 31 авг 2013 22:21 |
| Question | SKYDOS | 1414. Астрономическая база данных | 19 июл 2010 22:38 | 3 |
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 :) |
| AC 3,2 sec. How to get 0,5 sec? | Beksinski | 1414. Астрономическая база данных | 26 окт 2013 12:02 | 8 |
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 |
| Stupid question | Alexss | 1414. Астрономическая база данных | 27 окт 2007 23:48 | 1 |
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 |
| C++ Input handling (end of input, that is) | Mihail Minkov | 1414. Астрономическая база данных | 17 авг 2008 23:52 | 4 |
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 read faq Vladimir Yakovlev (USU) 20 сен 2007 15:55 while(scanf("%s", s) == 1)
Edited by author 17.08.2008 23:53 |
| Why WA#1? | Neizvestnii | 1414. Астрономическая база данных | 14 ноя 2008 22:56 | 2 |
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 |
| What is the 5-th test? | realman.lv(Lviv NU) | 1414. Астрономическая база данных | 24 дек 2007 01:44 | 2 |
|
| test 1 Crash (access violation)! | snake | 1414. Астрономическая база данных | 19 янв 2007 18:03 | 2 |
Can anybode help me!!!
I always have Crash (access violation)!!!
But my program work right on my computer!
I have tested this programm on tests like this
+a5000
+a999
....
+a1
?a
?a
...
?a
Everything is right!!!
no problem
just pastle:
fillchar(root^, sizeof(TRootType), 0);
Edited by author 19.01.2007 18:03 |
| WA on test #5 | teamSaratov | 1414. Астрономическая база данных | 24 июл 2014 18:34 | 5 |
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 |
| how i may get end entering command (i writen on C) | jobi | 1414. Астрономическая база данных | 19 ноя 2006 02:28 | 1 |
how i may get end entering command (i writen on C)
Edited by author 19.11.2006 02:29 |
| how about this test? IMHO TLE anyway... | Alexander Prudaev | 1414. Астрономическая база данных | 2 сен 2006 21:42 | 2 |
+a1
+a2
...
+a5000
?a
?a
?a
and 5000 queries ?a
or this operations in random order
IMHO O(N^2) - is best. I am right?
I try to solve this with red&blak tries but WA#5
what's in this test? I had WA#5 when my program gives more then 20 names of stars. |
| How can I get where's the end of commands? | Lutsenko | 1414. Астрономическая база данных | 19 апр 2006 21:48 | 8 |
How can I get where's the end of commands? There are no files and eof() in pascal won't help. Thanx, but now I have another problem: WA #5.
I'm adding all the stars, was it in the base or not. Then on a query I create a new array with stars matching the mask, but not in this array already. Then quicksort this array and output.
Maybe my algorythm is wrong and I should enter all the stars first, sort them and then output. This may work because only 20 first stars should be printed.
What can you say?
And sorry for my bad english :) Your algo seems to be correct. I Write Simple Algo But WA 5 too... I do add the word "sun" in my base I would be very gratefull, here's my email: zorg-n-ko@nm.ru |
| WA#11 | igrok | 1414. Астрономическая база данных | 7 фев 2006 20:13 | 1 |
WA#11 igrok 7 фев 2006 20:13 |
| Why I have WA#1??? | snipious {USSR СССР SIAL СМАЛ Pimenov Пименов}#1 | 1414. Астрономическая база данных | 7 янв 2006 19:57 | 3 |
Here is my source:
version #1
[code deleted]
version #2
[code deleted]
Edited by author 10.12.2005 16:02
Edited by moderator 22.02.2006 22:07 You shouldn't print points) And write a directive {$IFNDEF ONLINE_JUDGE} (not JUDJE but JUDGE) correctly. |
| WA 5? | Tkach | 1414. Астрономическая база данных | 9 ноя 2005 20:15 | 10 |
WA 5? Tkach 5 ноя 2005 01:04 Only sort array and use binary search...
Who can help??? How you passed first test? use sort and binary search would timelimit at #11
my code:
[code deleted]
Edited by moderator 22.02.2006 22:05 how about trie tree?
(mle) use sort and binary search would timelimit at #11 Why tle11? Its only: n log n You try to use other sort procedure(not qsort)? Maybe in 11 test qsort works n*n(unreal?)... First I have WA1 but then I found my mistake...
Check this-
+aaaa
+a
?a
Right answer is:
a
a
aaaa My program gives right answer for this test! Re: WA 5? Samsonov Alex [USU] 9 ноя 2005 15:25 Try this test:
+eee
+eef
+eed
?e
answer:
e
eed
eee
eef Try this test:
+eee
+eef
+eed
?e
answer:
e
eed
eee
eef My program get right answer for this test... I dont understand whats wrong... Sorry for post code but i cant find mistake...
Maybe you can???
[code deleted]
Edited by moderator 22.02.2006 22:08 |
| need help! | Roman Nazarkevych | 1414. Астрономическая база данных | 8 ноя 2005 16:43 | 16 |
Please give me some test becouse I always have WA#1! I don't print dots, only spaces! don't shout loudly and show your impatience.
case 1 is frequently similar or exactly the same as sample input. check it carefully, esp. the format.
what's more, you should check if you have put the word "sun" inside your words list.
Of course I remember about the word "sun".
But inspite of it I can't find my mistake! Am I right that (e10<e2)? I just used strcmp in C/C++.
Besides, i really met no trick.. I got AC directly/firstly during the contest I use strcmp too and I can't understand why WA#1. [code deleted]
Edited by moderator 08.11.2005 00:06 You output only one space, but in description:
"Each name must be preceded by two spaces as it is shown in the sample"
Edited by author 05.11.2005 04:28 I print two spaces, but they aren't shown in this page! It is really strange! I tested your code on simple tests with my prg and all outputs are equal...
You need help of author... Your solution outputs last query twice!
Try this
while(cin>>c>>s){
instead of
while(!cin.eof()){
cin>>c>>s;
Thank You!!!
You were right!!!
Edited by author 08.11.2005 16:43 |
| I got AC | [NU GYM] I am get tester... | 1414. Астрономическая база данных | 11 ноя 2017 19:12 | 4 |
I got AC [NU GYM] I am get tester... 30 окт 2005 14:51 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. Re: I got AC Andrew Hoffmann aka SKYDOS [Vladimir SU] 27 июл 2010 21:37 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.
|
| Please help!!! Why I get WA #1??? | [NU GYM] I am get tester... | 1414. Астрономическая база данных | 30 окт 2005 14:46 | 2 |
[CODE WAS HERE]
Edited by author 30.10.2005 14:44 It is terrible bug.
Now I havn't it. |
| give me an answer | Roman Nazarkevych | 1414. Астрономическая база данных | 10 дек 2005 15:04 | 5 |
What is the answer for this test:
+e1
+e2
+e10
?e |
