Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
TL | andreyDagger | 1603. Эрудит | 20 сен 2021 15:25 | 1 |
TL andreyDagger 20 сен 2021 15:25 If you use mask as two-dimensional array you probably will get TLE, instead of this use bitset from STL Edited by author 20.09.2021 15:25 |
stop asking #3 WA - HINT here | melkiy | 1603. Эрудит | 10 май 2020 04:24 | 8 |
To all of you who cannot overcome #3 !!! All the suggestions about redundant '\n' and about that the dictionary may have repeated words have nothing to do with WA #3 (read condition carefully). If you use any kind of backward tracking, be it recursion or DFS, check the "no luck" condition attentively. First i used checking the next letter to be '\0' at the beginning of my recursion function, and if so returned 'true'. This is wrong! You must make word-end check BEFORE you make the next step, otherwise you may get "deadlock" "there is no direction to go" though there is no need to go anymore!!! Test word for the example table rabadaabracabrac: YES (starting from [3,1] in C-like indices). How did you get rabadaabracabrac: YES In the condition there is said,that words could not have self-intersections. But if you don't intersect you will not get this word. My program writes NO on this test Thank you, melkiy! I made the same mistake :( My program got YES on this test, by have WA#3 It's not a test case for WA#3: rabadaabracabrac: YES and it's not working. My reason for WA #3 was that I tried to use 1d char array to store the table and used i -> i - 1 to go left and i -> i + 1 to go right, however, if you are in the first column you can't go left and if you're on the 4th row you can't go right |
You can mix Aho-Corasick and DFS to get very fast solution | Mahilewets | 1603. Эрудит | 15 июл 2017 22:44 | 1 |
Though without Aho-Corasick and without trie and without any optimizations simply DFS with used [i] [j] and backtracking is fast |
After getting TL or WA you might be interested in this not efficient way (java AC 0.5s, 17Mbs) | esbybb | 1603. Эрудит | 31 авг 2015 21:31 | 1 |
i ended up counting all possible Strings can be composed quickly. so preprocessing gives me 552 of the 16 symbols words 27956 of less than 16 symbols words (including those who are 1) |
if you got WA3 | Ahmadjon | 1603. Эрудит | 21 окт 2014 00:04 | 1 |
try this test wydh smdb dmks piwo 3 dhbdmy wsmydd dhbdmy ans: dhbdmy: YES wsmydd: YES dhbdmy: YES |
Does the test#1 coincide with the sample test? | lenny | 1603. Эрудит | 26 апр 2013 14:59 | 1 |
|
TLE 5 | MOPDOBOPOT (USU) | 1603. Эрудит | 4 сен 2012 21:27 | 3 |
TLE 5 MOPDOBOPOT (USU) 25 авг 2012 23:31 I'm using simple DFS from every point and got TLE on 5th test. Wich algo should I use to solve it faster? Re: TLE 5 Andrew Sboev [USU] 27 авг 2012 20:34 Yeah, i also have this problem :) Re: TLE 5 Andrew Sboev [USU] 4 сен 2012 21:27 Got AC, 0.078 :) MOPDOBOPOT, it it a so easy problem, just generate all words that you can get from table, and using this list just check all words. Edited by author 04.09.2012 21:28 |
No subject | MOPDOBOPOT (USU) | 1603. Эрудит | 25 авг 2012 23:31 | 1 |
Sorry for double-posting... Edited by author 25.08.2012 23:33 |
WA #6 | Artem | 1603. Эрудит | 5 мар 2012 20:13 | 1 |
WA #6 Artem 5 мар 2012 20:13 I have WA #6. For all my tests program works correctly. Can you give me some tests? |
hint | Anton | 1603. Эрудит | 21 фев 2012 09:24 | 1 |
hint Anton 21 фев 2012 09:24 Do not rape your brain with this problem:), since constraints are really small, - just run straight dynamic, it's look similar to dfs. After I've corrected some stupid mistakes I've got AC 0.375 124 КБ, without any optimization |
WA #3 Again! | Nurbek_[KTMU MANAS] | 1603. Эрудит | 30 ноя 2010 07:51 | 4 |
Please explain me where is tricky? If you don't want say tricky, give some tests. I use backtracking. Edited by author 06.03.2008 16:22 Edited by author 06.03.2008 16:23 test 3 contains "\n" strings How? I can't understand. Please explain better. test 3 contains "\n" strings This is impossible. In the next N strings follow N words with length between 1 and 16 |
Please look here... wa3 | Crash_access_violation | 1603. Эрудит | 30 ноя 2010 07:49 | 8 |
thanks... I got AC! Edited by author 12.03.2008 04:00 try test with '\n' string: abra adac babr arca 3 abracadabra ababaab ababaaba And how test is right? What a test #3? I know how to solve this task, but test #3... When I used gets() I had wa3 and this test help me to change gets() to scanf(...)) and after that I got ac Test#3 has two words are exactly the same Edited by author 30.11.2010 07:48 Edited by author 30.11.2010 07:48 try test with '\n' string: abra adac babr arca 3 abracadabra ababaab ababaaba This is impossible. In the next N strings follow N words with length between 1 and 16 |
Plese give me test!!!!! | vetal | 1603. Эрудит | 15 мар 2009 23:35 | 1 |
|
WA3 here is my Code Help ME | fuch_prog_er | 1603. Эрудит | 2 мар 2009 00:47 | 1 |
#include <string> #include <iostream> #include <stack> using namespace std; char a[6][6]; int b[5][5]; int i,j,n,o,q,p,r,m; stack <int> si,sj; bool t=false; string s; //****************************************** void inp(){ for(i=1;i<=4;i++) for(j=1;j<=4;j++) { cin>>a[i][j]; } for(m=0;m<5;m++) {a[m][0]=a[0][m]='-1'; a[m][5]=a[5][m]='-1'; } } //****************************************** void copy(){ for(o=1;o<=4;o++) for(q=1;q<=4;q++) b[o][q]=1; } //****************************************** bool check(string buf){ copy(); for(i=1;i<=4;i++){ for(j=1;j<=4;j++){ if(a[i][j]==buf[p]&&b[i][j]==1) {p=0; t=true; si.push(i); sj.push(j); p++; if(p>=buf.length()) return true; b[i][j]=0; } while(!si.empty()){ /*1*/ if(a[si.top()][sj.top()+1]==buf[p]&&b[si.top()][sj.top()+1]==1){ si.push(si.top()); sj.push(sj.top()+1); t=true; p++; if(p>=buf.length()) return true; b[si.top()][sj.top()]=0; } /*2*/ else if(a[si.top()][sj.top()-1]==buf[p]&&b[si.top()][sj.top()-1]==1){ si.push(si.top()); sj.push(sj.top()-1); t=true; p++; if(p>=buf.length()) return true; b[si.top()][sj.top()]=0; } /*3*/ else if(a[si.top()+1][sj.top()]==buf[p]&&b[si.top()+1][sj.top()]==1){ si.push(si.top()+1); sj.push(sj.top()); t=true; p++; if(p>=buf.length()) return true; b[si.top()][sj.top()]=0; } /*4*/ else if(a[si.top()-1][sj.top()]==buf[p]&&b[si.top()-1][sj.top()]==1){ si.push(si.top()-1); sj.push(sj.top()); t=true; p++; if(p>=buf.length()) return true; b[si.top()][sj.top()]=0; } if(!t){ si.pop(); sj.pop(); if(p!=0) p--; } t=false; }//<while(); if(si.empty()) copy(); } } return false; } //****************************************** int main() { inp(); cin>>n; cin.ignore(); for(r=1;r<=n;r++) { cin>>s; if(check(s)) cout<<s<<": YES"<<endl; else cout<<s<<": NO"<<endl; } system("pause"); return 0; } Edited by author 02.03.2009 00:54 |
WA 3 :( help | fuch_prog_er | 1603. Эрудит | 2 мар 2009 00:16 | 1 |
Please tell me what is the test 3? |
Output order !! | OSt [Vologda SPU] | 1603. Эрудит | 5 янв 2009 23:18 | 1 |
In your example order of words in dictionary is same with order of outputing words, but in the problem's text there is no words about it. Fix it , please. |
Why I got WA2?:( | Michail Golubev | 1603. Эрудит | 3 сен 2008 21:51 | 1 |
I`ve got WA2 some times. Test adac babr arca 3 abracadabra ababaab ababaaba my programm doing correctly. Where my bag? |
Want to hear the quick decision of the problem. | ACM.Krupko_Victor[Ivanovo SPU] | 1603. Эрудит | 15 май 2008 21:33 | 1 |
I have solved her My email: victorkr@dsn.ru please! |
I get WA3 | Ilya001(Java) | 1603. Эрудит | 14 май 2008 12:50 | 2 |
I think that made it right. But my program does not pass the test 3. me 2~~~ :) I think that made it right. But my program does not pass the test 3. |
to admins: what is test 11, i can't get it for 10 times! | AndrKonin | 1603. Эрудит | 26 апр 2008 23:34 | 1 |
i use a standart rec function may be something wrong with input (cin >> s;) may be another. Can you give me 7th test to check this? |