|
|
Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | TLE #2 & WA #2 | 👨🏻💻 Spatarel Dan Constantin | 2059. Не общие подпалиндромы | 11 июл 2019 03:01 | 1 | First and foremost, is seems to me that there are only two test cases: (1) the sample case (2) an 8MB test case For WA this test helped me: input: 2 bbaadbdcc aadbdbcbadb aadbdbcbadb bbaadbdcc output: Case #1: 3 2 5 Case #2: 5 2 3 For TLE: parse the input I optimized all sorts of things but eventually I ran out of ideas. Then I remembered someone else was mentioning he submitted the same code again and passed got rid of TLE. Also, from my own experience, I noticed there was a sort of "randomness" in the time execution from one submission to another. (I was able to detect it by killing my program after processing 6MB of the input file.) At this point I was seriously considering speeding up the input reading part of my program using custom code instead of stdin.h. I got 760ms for processing 6MB of the input and I said to myself I'm really close: my code should run in 1.040s. And so I decided to parse the input: I got AC in 560ms! A 480ms boost of speed! So... long story short: parse the input! | Stupid hint | Felix_Mate | 2059. Не общие подпалиндромы | 12 авг 2017 01:51 | 1 | If you got TL you can try send same code and to get AC. When I delete 2 string (they are comments) i got AC. | Орфография | Alex Mullabaev`` | 2059. Не общие подпалиндромы | 29 дек 2016 22:41 | 1 | Нас просят найти количество непустНых палиндромов. | What's wrong my algo? I got WA2, always. | xurshid_n | 2059. Не общие подпалиндромы | 28 окт 2016 04:34 | 1 | Let C = A + '$*&' + B for string C build Palindrom Tree. calculate frequency of each palindrom : f(A,p) calculate frequency of each palindrom : f(B,p) x = count(f(A,p)>f(B,p)) y = count(f(A,p)==f(B,p) && f(A,p)!=0) z = count(f(A,p)<f(B,p)) //little code: freq[i][0] ---> f(A,p); freq[i][1] --> f(B,p). for(int i = 0; i < a.size(); ++i){ add_letter(a[i]); freq[last][0]++;} add_letter('$'); add_letter('*'); add_letter('&'); for(int i = 0; i < b.size(); ++i){ add_letter(b[i]); freq[last][1]++;} for(int z = sz-1; z > 0; z--){ v = link[z]; freq[v][0] += freq[i][0]; freq[v][1] += freq[i][1]; } int x=0,y=0,z=0; for(int i = 2; i< sz; ++i)// skip roots { x += (bool)(freq[i][0] > freq[i][1]); y += (bool)(freq[i][0] == freq[i][1] && freq[i][0] !=0); z += (bool)(freq[i][0] < freq[i][1]); } | alphabet | Wroclaw Smurfs | 2059. Не общие подпалиндромы | 27 мар 2016 13:26 | 2 | alphabet Wroclaw Smurfs 11 июл 2015 14:01 Do strings consist of only lower-case letters of latin alphabet ? |
|
|
|