April19 - Problem Discussion


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


Also, how to solve XORMIN?


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

Pre Reqs -


If you are familiar with pre reqs then its just -
Maintain persistence trie for each node along with dsu ninja technique.

Similar Questions -


This post was flagged by the community and is temporarily hidden.


it is the correct approach i also used the same one


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


just make the egde undirected i.e.
for edge between u - v
add u -> v
as well as v -> u in the adjacency list.


But how does that make a difference?


i dont know why, but i worked for me.
so i have raised discussion for this.


Can you please share your code using an external link? Instead of copy pasting here??
Long code posted here makes scrolling difficult.


@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.


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


Last test case -
2 is the only child of 1. But you should not consider 1 as leaf.


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


qlogNlogAi was supposed to give tle. :stuck_out_tongue:
You will have to optimise it to q*logAi
Here logAi = 20.


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?


I did a simple dfs. With some modular arithmetic.
Here’s my solution : SJ1


I used segment trees to further find the value of the minimum vertex, see my code…


Just store node no in leaf. Min node no which brings you to that no.


What’s your idea of solving RECTARAN ?