Alex Stone - 6 months ago 26

C++ Question

How would you go about solving a problem that states:

A given sequence of integers can be broken up into parts such that

each of them is a palindrome. Consider the sequence 34,45,34,56,34.

This can be broken up into 3 palindrome sequences with 34, 45, 34

constituting the first, 56 constituting the second and 34 constituting

the third. It can also be broken in 5 palindrome sequences each

containing a single number. Thus, there may be many different ways to

break up a given sequence into palindrome sequences. We want to

determine the smallest number C such that the given sequence can be

broken up into C palindrome sequences.

My solution does this: Find the maximum palindrome (palindrome of greatest length) of the array, take the rest of the array besides this maximum palindrome, and try to find its maximum palindrome and so on, while incrementing the count of the number of palindromes.

This is what I have so far:

`#include <algorithm>`

#include <iostream>

#include <vector>

#define print(arr) for(auto pos = arr.begin(); pos != arr.end(); ++pos) cout << *pos << " "; cout << endl;

typedef long long int ll;

using namespace std;

int calc(vector<ll> A, int N) {

int i = N;

vector <ll> t1, t2;

while (i >= 0) {

t1 = vector <ll> (A.begin(), A.begin()+i);

t2 = vector <ll> (t1.rbegin(), t1.rend());

if (t1 == t2) return i;

i--;

}

return 0;

}

int main() {

int N;

ll x;

cin >> N;

vector <ll> A(N);

for (int i = 0; i < N; i++) {

cin >> x;

A[i] = x;

}

int temp = calc(A,N);

int c = 0;

while (temp != 0) {

A = vector <ll> (A.begin()+temp, A.end());

N = (int)A.size();

temp = calc(A, N);

c++;

}

cout << c << endl;

}

However, I'm getting 3 testcases wrong. Realised later that my program outputs 4 instead of 2 for testcase: N=8, {2, 1, 2, 1, 2, 3, 2, 1} It takes the palindromes to be {2,1,2,1,2}, {3}, {2}, {1} whereas it should be {2,1,2}, {1,2,3,2,1}. If I reverse the vector and calculate minimum answer between the two, I will get correct answer 2 for this test case but for others on Codechef I am still getting 2 testcases wrong, probably for the same reason as I am getting this wrong.

Anyway, any idea how I can improve this?

Link to problem on codechef: https://www.codechef.com/ZCOPRAC/problems/ZCO15001 Its from an ongoing competition, but the competition is only a practice contest for the Zonal Computing Olympiad held in India.

Answer

This is a typical problem for dynamic programming. You can solve it easily with `O(N ^ 2)`

complexity, where `N`

is the size of input string.

First of all, you can precalculate all the palindromes with `O(N ^ 2)`

complexity to answer if substring `[i, j]`

is palindrome or not in `O(1)`

(let it be an exercise for you).

Then you can calculate array `dp`

, where `dp[i]`

is the answer for substring `[0, i]`

. To find `dp[i]`

you need to do: `dp[i] = min(dp[i], dp[j] + 1)`

for all `j`

where `j < i`

and substring `[j + 1, i]`

is palindrome. Here you use palindromes precalculation to check if substring `[j + 1, i]`

palindrome or not in `O(1)`

. And `dp[0]`

is `1`

of course.

The answer is `dp[N - 1]`

.

P.S. All indexes are 0-based.