You are not logged in. Please login at www.codechef.com to post your questions!

×

ZCO15001 - Editorial

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;
}
This question is marked "community wiki".

asked 26 Dec '17, 20:15

brahmnoor's gravatar image

2★brahmnoor
193
accept rate: 0%

edited 24 Jan '18, 20:22

admin's gravatar image

0★admin ♦♦
19.8k350498541


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?

link

answered 03 Sep '18, 07:48

jvjplus's gravatar image

2★jvjplus
815
accept rate: 0%

Can someone tell this please?

(24 Oct '18, 17:55) the_extractor4★

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 :-)

link

answered 31 Oct '18, 03:08

joffan's gravatar image

5★joffan
9488
accept rate: 13%

Thanks @joffan.

(02 Nov '18, 14:15) the_extractor4★

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.

link

answered 25 Sep '18, 18:30

darklord_chef's gravatar image

5★darklord_chef
12
accept rate: 0%

1

I'll have a look in Jan 2020, when the "competition" ends. :-)

(31 Oct '18, 03:09) joffan5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×2,214
×427
×74

question asked: 26 Dec '17, 20:15

question was seen: 895 times

last updated: 23 Nov '18, 13:37