ZCO15001 - Editorial

editorial
, , ,
1

PROBLEM LINK

ZCO15001

DIFFICULTY

Easy

PREREQUISITES

Dynamic Programming

PROBLEM IN SHORT

Output the smallest n such that the given array can be broken into n contiguous sub-arrays which are palindromes.

SOLUTION

This problem has a dynamic programming solution. Simply stated, the constraints are small
enough for a O(n^3) solution. If we can somehow find the solution for the sub-array from index i to
(n - 1), and then use it to find subsequent answers - we’ll have a solution.

The simplest way to do this, is to define an array dp, which stores the answers for each i, from 0 to
(n - 1). Also, dp[i] = min(dp[i], dp[j + 1] + 1), if the sequence from i to j is a palindrome, for all j, from i to (n - 1).

This is because, if the sequence from i to j is a palindrome, that’s one palindromic sequence and
thus we add one to the optimal solution for the array from (j + 1) to (n - 1).
Finally, dp[0] is the solution, because it’ll be the optimal solution for the array 0 till (n - 1).

TIME COMPLEXITY

O(n^3) for building the dp array. It can be further optimised to O(n^2) if you find out if the array from i to j is a palindrome using a 2D dynamic programming approach.

EDITORIALIST’s SOLUTION

#include <bits/stdc++.h>
using namespace std;

int n, a[307];
int dp[307];

int isPalin(int i, int j) { // is the sequence from i to j a palindrome - including both i and j
	int length = j - i + 1;
	for (int it = 0; it < length/2; it++) {
		if (a[i + it] != a[j - it])
			return 0;
	}
	return 1;
}

int recur(int cur) {
	if (dp[cur] != -1)
		return dp[cur];
	else {
		int ans = INT_MAX;
		for (int i = cur; i < n; i++) {
			if ( isPalin(cur, i) )
				ans = min(ans, recur(i + 1) + 1);
		}
		return dp[cur] = ans;
	}
}

int main() {
	memset(dp, -1, sizeof(dp));
	scanf("%d", &n);
	dp[n] = 0;
	dp[n - 1] = 1;
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	printf("%d", recur(0));
	//for (int i = 0; i < n; i++)
	//	printf("%d ", recur(i));
	//printf("\n %d", isPalin(3, 4));
	return 0;
}
1 Like
2

Plz discuss the approach of

It can be further optimised to O(n2) if you find out if the array from i to j is a palindrome using a 2D dynamic programming approach.

also. ie how to make 2D table to check palindrome?

1 Like
3

It doesn’t necessarily requires a 2d array…

Such is in this case where the given problem can be solved in O(n2) simply by using bottom up instead of top down approach.

Here’s the link to my submission using the same.

4

Making a table of palindromes in O(n^2) can be done by extending from each entry “upstream” and “downstream”. Note even-length and odd-length palindromes are found separately. Worst case, of all values the same, will give \approx n^2/2 palindromes. Here I tag each palindrome with start element and the element after the end (i.e. to start the next palindrome at)

Then finding the “path” to optimally use those palindromes is here also O(n^2) but could probably be O(n) by working breadth-first.

# https://www.codechef.com/ZCOPRAC/problems/ZCO15001

n = int(input())
seq = list(map(int, input().split()))

ps = [[] for _ in range(n)]

# find all palindromes
for mid in range(n):
    up = dn = mid
    while up >= 0 and dn < n:
        if seq[up] != seq[dn]:
            break
        ps[up].append(dn+1)
        up -= 1
        dn +=1
    up = mid
    dn = mid+1
    while up >= 0 and dn < n:
        if seq[up] != seq[dn]:
            break
        ps[up].append(dn+1)
        up -= 1
        dn +=1
        
#find best set of palindromes for traverse
pto = [n+1]*(n+1)
pto[0] = 0
for fx in range(n):
    for p in ps[fx]:
        if pto[p] > pto[fx] + 1:
            pto[p] = pto[fx] + 1

print(pto[n])

Amusing observation: I used dn as an abbreviation for “down” and noticed that it’s up, upside-down :slight_smile:

1 Like
5

Can someone tell this please?

6

I’ll have a look in Jan 2020, when the “competition” ends. :slight_smile:

1 Like
7

Thanks @joffan.