ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1635. Mnemonics and Palindromes

Please tell me how to solve it....
Posted by Asyamov Igor 21 Nov 2008 20:16
I have got WA 23, but I know that my algo will have TLE...
What is the right algo???
Re: Please tell me how to solve it....
Posted by Asyamov Igor 24 Nov 2008 22:44
Accepted!!!!
BFS - very good thing!!!!
Re: Please tell me how to solve it....
Posted by Игор 10 Feb 2020 00:19
#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;
}