Let the discussion begin.

How to solve " Kira Loves Palindromes"??

P.S. - If you want an introductory story and blah blah hear over to NOV18 - Problem Discussion

# April19 - Problem Discussion

**aryanc403**#1

**kmampent**#3

For the Kira Loves Palindromes problem:

Let S be the input string. Define a table D as follows:

D[i,j] = total number of pairs (i,k), (w,j) where i<=k<w<=j such that S[i…k]S[w…j] is a palindrome. Observe that the result is the sum over all D[i,j].

To find the recurrence for D[i,j], define the following three tables, P, LR, RL:

P[i,j] = 1 if S[i…j] is a palindrome and 0 otherwise

LR[i,j] = total number of palindromes S[i…k] where i <= k <= j. In simple words, you want to count how many palindromes start from S[i] and end in some S[k] where i<=k<=j

RL[i,j] = total number of palindromes S[k…j] where i <= k <= j

Then we have that D[i,j] = 1 + D[i+1,j-1] + LR[i+1,j-1] + RL[i+1,j-1] when S[i] = S[j], 0 otherwise.

The recurrences for P, LR and RL are fairly simple (left as an exercise to the reader :P) but you can find my submission here.

KLPM - Editorial

**aryanc403**#4

Pre Reqs -

https://codeforces.com/blog/entry/44351

https://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems

If you are familiar with pre reqs then its just -

Maintain persistence trie for each node along with dsu ninja technique.

Similar Questions -

https://www.codechef.com/MAY17/problems/GPD

https://www.codechef.com/NOV18A/problems/BINSTR

https://www.codechef.com/problems/MCO16404

**gateway2745**#7

But i am getting WA…Could you please tell me what is wrong …I have spent more than 2 hours trying to find out …

**amitguptapc**#8

just make the egde undirected i.e.

for edge between u - v

add u -> v

as well as v -> u in the adjacency list.

**aryanc403**#11

Can you please share your code using an external link? Instead of copy pasting here??

Long code posted here makes scrolling difficult.

**arjunnn1206**#12

@aryanc403 I’ve used a similar approach, but in Python. Here’s the code if you want to review it. Is there any other way to approach this?

If you restrict the solution set to non-negative, it becomes an extension of subset sums. Looking at the Frobenius problem isn’t really of help.

https://www.pastiebin.com/5cb47b2f9e83c

I used a union to iterate back to the parent. Gives WA for everything except the last test case

**mohanr**#14

I used a segment tree with trie solution but it was giving TLE for subtask 3.Could you tell me where could I further optimize my solution??Here is my solution

**aryanc403**#15

q*logN*logAi was supposed to give tle.

You will have to optimise it to q*logAi

Here logAi = 20.

**kaneki13**#16

I implemented persistent trie and got the maximum value of xor, but then how did you calculate the node whose weight is resulting in that value efficiently?