Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Wa19 | capitan.ARA.code | 1635. Мнемоника и палиндромы | 27 окт 2022 10:09 | 1 |
Wa19 capitan.ARA.code 27 окт 2022 10:09 bonnon Answer b onno n Edited by author 27.10.2022 10:18 Edited by author 27.10.2022 10:19 |
solution | Anton | 1635. Мнемоника и палиндромы | 19 ноя 2021 02:17 | 1 |
might it is very complicated but i use hash and dp to solve this problem |
If you have MLE. | wiwi | 1635. Мнемоника и палиндромы | 22 ноя 2020 16:44 | 1 |
I had MLE on test 33. I just changed int to short and 1,0 to bool Sorry if this is too obvious Edited by author 22.11.2020 16:48 |
Simple question | qwe (Dmitry) | 1635. Мнемоника и палиндромы | 4 мар 2020 13:00 | 5 |
consider follow string: ABZZBBBZZA. 2 polindroms: ZZBBBZZ and ABA - correctly for this problem? i think answer is 3 polindroms: AB ZZBBBZZ A I thin its 4 palindromes A B ZZBBBZZ A Смотрю с любовью на свои более 10-летней давности попытки решать задачи. Спасибо, ACM.Timus! |
Please tell me how to solve it.... | Asyamov Igor | 1635. Мнемоника и палиндромы | 10 фев 2020 00:19 | 3 |
I have got WA 23, but I know that my algo will have TLE... What is the right algo??? Accepted!!!! BFS - very good thing!!!! #include <iostream> #include <algorithm> #include <string> unsigned counter = 0; void printPalindroms(unsigned short *splitIndex, unsigned short i, const std::string& str){ if(splitIndex[i] == 0){ std::cout<<str.substr(0, i+1)<<" "; }else{ printPalindroms(splitIndex, splitIndex[i]-1, str); std::cout<<str.substr(splitIndex[i], i + 1 - splitIndex[i])<<" "; } } int main() { std::string strr; std::cin>>strr; const char* str = strr.data(); unsigned length = strr.size(); unsigned arrSize = (length*length + length)/2; bool *pArrData = new bool[arrSize]; bool **pArr = new bool*[length]; unsigned short *splitWeights = new unsigned short [length]; unsigned short *splitIndex = new unsigned short[length]; std::fill(pArrData, pArrData + arrSize, false); std::fill(splitWeights, splitWeights + length, length +2); std::fill(splitIndex, splitIndex + length, 0);
unsigned offset = 0; for(unsigned i = 0; i<length; ++i){ pArr[i] = pArrData + offset; offset += length - i; } // init the first row std::fill(pArr[0], pArr[0] + length, true); //init the second row for(unsigned i = 0; i<length - 1; ++i){ if(str[i] == str[i+1]){ pArr[1][i] = true; } } for(unsigned i = 2; i < length; ++i){ for(unsigned j = 0; j< length - i; ++j){ if(pArr[i-2][j+1] && str[j] == str[j+i]){ pArr[i][j] = true; } } } for(unsigned i = 0; i < length; ++i){ if(pArr[i][0] == true){ splitWeights[i] = 0; splitIndex[i] = 0; }else{ for(unsigned j = 1; j <= i; ++j){ if(pArr[i-j][j]){ unsigned short temp = splitWeights[j-1] + 1; if(temp < splitWeights[i]){ splitWeights[i] = temp; splitIndex[i] = j; } } } } } std::cout<<splitWeights[length -1] + 1<<std::endl; printPalindroms(splitIndex, length - 1, strr); delete[] splitIndex; delete[] splitWeights; delete[] pArr; delete[] pArrData;
return 0; } |
No subject | CU_PROBABILITY | 1635. Мнемоника и палиндромы | 22 авг 2018 12:25 | 2 |
I am getting wrong answer.Please give me some test case. My solution: #include<iostream> #include<string.h> #include<string> #include<stdlib.h> #include<stdio.h> #include<vector> #include<algorithm> using namespace std; string line; bool check(int s,int e) { string temp; for(int i=s; i<=e; i++) temp.push_back(line[i]); string temp2=temp; reverse(temp.begin(),temp.end()); if(temp==temp2) return true; return false; } int dp[4005][4005]; int palindrome(int s,int e) { if(s>=e) return 0; if(dp[s][e]!=-1) return dp[s][e]; int ans=(1<<30); for(int i=s; i<e; i++) if(check(s,i)) { ans=min(ans,1+palindrome(i+1,e)); } return dp[s][e]=ans; } vector<string>anss; void print(int s,int e) { int b=palindrome(s,e); if(b==1) { string temp; for(int i=s; i<e; i++) temp.push_back(line[i]); anss.push_back(temp); return; } for(int i=s; i<e; i++) if(b==1+palindrome(i+1,e)) { string temp; for(int j=s;j<=i;j++) temp.push_back(line[j]); anss.push_back(temp); print(i+1,e); break; } } int main() { cin>>line; int len; len=line.size(); anss.clear(); memset(dp,-1,sizeof dp); cout<<palindrome(0,len)<<endl; print(0,len); len=anss.size(); for(int i=0;i<len-1;i++) cout<<anss[i]<<" "; cout<<anss[len-1]<<"\n"; } Ответ aper 22 авг 2018 12:25 Ошибка где-то тут: string line; bool check(int s,int e) { string temp; for(int i=s; i<=e; i++) temp.push_back(line[i]); string temp2=temp; reverse(temp.begin(),temp.end()); if(temp==temp2) return true; return false; } int dp[4005][4005]; int palindrome(int s,int e) { if(s>=e) return 0; if(dp[s][e]!=-1) return dp[s][e]; int ans=(1<<30); for(int i=s; i<e; i++) if(check(s,i)) { ans=min(ans,1+palindrome(i+1,e)); } return dp[s][e]=ans; } vector<string>anss; void print(int s,int e) { int b=palindrome(s,e); if(b==1) { string temp; for(int i=s; i<e; i++) temp.push_back(line[i]); anss.push_back(temp); return; } for(int i=s; i<e; i++) if(b==1+palindrome(i+1,e)) { string temp; for(int j=s;j<=i;j++) temp.push_back(line[j]); anss.push_back(temp); print(i+1,e); break; } } int main() { cin>>line; int len; len=line.size(); anss.clear(); memset(dp,-1,sizeof dp); cout<<palindrome(0,len)<<endl; print(0,len); len=anss.size(); for(int i=0;i<len-1;i++) cout<<anss[i]<<" "; cout<<anss[len-1]<<"\n"; } Edited by author 22.08.2018 12:26 Edited by author 22.08.2018 12:26 |
If you have WA20 | mikeweat | 1635. Мнемоника и палиндромы | 15 авг 2018 21:17 | 1 |
Try this abacabadabacab. The problem is in hash. Answer is : a bacabadabacab Edited by author 15.08.2018 21:18 |
WA42? | shota | 1635. Мнемоника и палиндромы | 30 сен 2017 16:48 | 2 |
WA42? shota 30 сен 2017 12:39 Re: WA42? Mahilewets Nikita [BSUIR] 30 сен 2017 16:48 It is something unique I have had WA20, WA23, TLE32, MLE56 But never WA42 |
wa24 help | Grandmaster | 1635. Мнемоника и палиндромы | 5 фев 2017 04:22 | 1 |
nvm accepted Edited by author 05.02.2017 04:33 |
WA on test #23 | Александър Гьорев | 1635. Мнемоника и палиндромы | 11 май 2016 03:56 | 5 |
Can anyone give me some test cases because I really don't know where my program is wrong ? Nevermind, this test case helped me find my mistake: "ababbaa" Me too. Thanks nice test. |
WA#19 | Maksim | 1635. Мнемоника и палиндромы | 24 фев 2016 16:20 | 1 |
WA#19 Maksim 24 фев 2016 16:20 pls help Edited by author 24.02.2016 16:20 |
If WA #5 | Accelarator | 1635. Мнемоника и палиндромы | 3 дек 2015 08:18 | 1 |
try this: aaaba is 2 aa aba not 3 aaa b a |
WA #7 can anyone help plz? | Rahul Agarwal | 1635. Мнемоника и палиндромы | 3 дек 2015 07:56 | 3 |
WA #7 can anyone help plz? using simple dp you are probably considering to get rid of palindromes as early as possible for example, consider the case "aabba" if you say it is 3 palindromes: "aa", "bb", and "a", then you are wrong, since it can be "a" and "abba" |
hint | ASK | 1635. Мнемоника и палиндромы | 22 ноя 2015 20:44 | 4 |
hint ASK 21 ноя 2010 22:06 Build a data-structure which allows O(1) test that s[from..to] is a palindrome. The structure is a 2 x s.size() array: even/odd length times possible center point. typedef vector<int> V; string s(4001, ' '); int n; V mpl[2]; // maximum palindrome length around i (even and odd lengths) inline bool is_polindrome(int from, int to){ assert(0 <= from and from < to and to <= n); int eo = (to - from) % 2, c = (from + to) / 2; return mpl[eo][c] >= c - from; } One can think like that: Let a(k) be the amount of palindromes in [0,k]. Then we have recursion: a(k)=MIN{ 1 if [0,k] is pm , MIN (from i = 0 to k -1) OF a(i) + 1 if [i,k] is pm} { 0 else a(i) + k-i else } I consider ASK to be absolutely right concerning data structure He proposed.
Considering each character as a pivot, expand on both sides to find the length of both even and odd length palindromes centered at the pivot character under consideration and store the length in the 2 arrays (odd & even). Time complexity for this step is O(n^2) |
finally accepted | Evgeny | 1635. Мнемоника и палиндромы | 22 ноя 2015 20:37 | 4 |
maybe it will be useful (or at least interesting) for somebody. at first i tried to make simple DP with O(n^3). i tried in java (and i received TLE in 32th test). after that i tried to realize greed algorithm and understood that this idea is wrong (simple antigreed test is: "abzzbbbzza") aand finally i've made O(n^2) DP. little hint: try to precalc d[l][r]: d[l][r] = true, s[l..r] - palindrom d[l][r] = false, s[l..r] - not palindrom whats the ans for 'abzzbbbzza'? i didn't get it how it will become n^2 because for l=1 to l=n is one loop and for r=l to r=n is inside loop and for checking it is palindrome is another loop so i don't get how it will be n^2 can you please explain me i am very confused here please help me |
WA #1 | GongLiangqi | 1635. Мнемоника и палиндромы | 22 ноя 2015 19:34 | 5 |
WA #1 GongLiangqi 27 мар 2013 18:15 Can you tell me why I always WA #1? Beacause I have tested all those samples in the board, and I pass them all... OK...I have got it...in Ural...in C...You must write like boolflag == 1...You can not write like boolflag,which works in my computer... aaaabaaa correct answer is 2 a aaabaaa your example is very good ! |
WA 12 | buea | 1635. Мнемоника и палиндромы | 23 окт 2015 07:18 | 2 |
WA 12 buea 23 окт 2015 06:59 Stuck at test case #12 Per reply in 2008, someone suggested testing with axayaaxa I don't know whether this is the real #12. But I tried anyway. My program answers a x aya axa And another possible answer is axa y a axa Both with 4 palindromes. Question says output any is correct. Suggestion? Thanks in advance! I spotted a bug. Will fix it first and try again. |
WA #59 | Nik | 1635. Мнемоника и палиндромы | 24 мар 2015 20:32 | 1 |
|
WA 19! Somebody, help me, please! | ONU_Antananarivu | 1635. Мнемоника и палиндромы | 19 авг 2013 13:38 | 2 |
Edited by author 08.09.2011 17:57 Give me your code ! I also WA 19,but I find write wrong dp[i]>dp[j-1]+1 to dp[i]>dp[j]^…… |
Why TLE??? | Accepted | 1635. Мнемоника и палиндромы | 24 мар 2013 18:46 | 1 |
I test my code at my computer,I got a test which is filled by period string "abcde" and its length is 4000,and my program run only 0.25s. My computer is: Memory:3GB System:Windows XP CPU:1.66GHZ But I got tle at #32...Why??? Here is my code. var i,j,xx,ox,t,l:longint; s:ansistring; f,x:array [1..4010] of longint; o:array [0..4010] of boolean; function pdhw(l,r:longint):boolean; var i:longint; begin if l=r then exit(true); for i:=l to (l+r)>>1+1 do if s[i]<>s[r+l-i] then exit(false); exit(true); end; begin readln(s); l:=length(s); for i:=1 to l do begin f[i]:=maxlongint; if pdhw(1,i) then f[i]:=0 else for j:=1 to i-1 do if (f[i]>f[j]+1)and(pdhw(j+1,i)) then begin f[i]:=f[j]+1; x[i]:=j; end; end; writeln(f[l]+1); xx:=l; repeat ox:=xx; xx:=x[xx]; if ox=l then o[xx+1]:=true else o[xx+1]:=true; until xx=0; o[1]:=false; for i:=1 to length(s) do if o[i] then write(' ',s[i]) else write(s[i]); end. |