Alex Stone Alex Stone - 1 year ago 82
C++ Question

Breaking an array of elements into least number of palindromes

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;
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);
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: Its from an ongoing competition, but the competition is only a practice contest for the Zonal Computing Olympiad held in India.

Answer Source

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download