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

×

RKABOL08 - Editorial

PROBLEM LINK:

Practice
Contest

Author: ravikiran0606
Editorialist: ravikiran0606

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

DP,STRINGS, STRINGS SUFFIX STRUCTURES

PROBLEM:

In this problem, we need to find the number of ways to split a string S to substrings such that if there are k substrings (p1, p2, p3, ..., pk) in partition, then pi = pk-i+1  for all i (1 ≤ i ≤ k) and k is even.

EXPLANATION:

Let n be the length of the string s. Consider the string t = s[0]s[n - 1]s[1]s[n - 2]s[2]s[n - 3]...s[n / 2 - 1]s[n / 2]. The problem can be reduced to finding the number of ways to partition string t into palindromic substrings of even length.

Proof: Let k be the total number of partitions. Let pi = pk - i + 1 = x1x2x3...xm where m denotes length of pi and xj denotes jth character of pi. The part of string t corresponding to these two partitions is x1xmx2xm - 1...xm - 1x2xmx1 which is an even length palindrome. Similarly, the converse is also true.

Dynamic programming can be used to solve the problem. Let dp[i] be the number of ways to partition t[1...i] into even length palindromes. Then, where t[j + 1...i] is an even length palindrome. Of course for odd i, dp[i] = 0.

As discussed in this blog, we can use an eertree to implement the solution. On the other hand, we can avoid the use of any suffix structure by following the algorithm described in this paper.

Complexity: O(|s|log|s|)

AUTHOR'S SOLUTION:

Author's solution can be found here

This question is marked "community wiki".

asked 14 Mar, 01:16

ravikiran0606's gravatar image

4★ravikiran0606
41
accept rate: 0%

edited 15 Mar, 13:36

admin's gravatar image

0★admin ♦♦
19.3k348495534

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,006
×1,880
×1,161
×346
×19
×19
×19
×14

question asked: 14 Mar, 01:16

question was seen: 177 times

last updated: 15 Mar, 13:36