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.
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.