×

# ZCO15001 - 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 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 19●3 accept rate: 0% 0★admin ♦♦ 19.8k●350●498●541

 1 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? answered 03 Sep '18, 07:48 2★jvjplus 81●5 accept rate: 0% Can someone tell this please? (24 Oct '18, 17:55)
 1 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 :-) answered 31 Oct '18, 03:08 5★joffan 948●8 accept rate: 13% Thanks @joffan. (02 Nov '18, 14:15)
 0 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. answered 25 Sep '18, 18:30 1●2 accept rate: 0% 1 I'll have a look in Jan 2020, when the "competition" ends. :-) (31 Oct '18, 03:09) joffan5★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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