ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
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;
}