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
Let the discussion begin.
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
If you are familiar with pre reqs then its just -
Maintain persistence trie for each node along with dsu ninja technique.
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?
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.
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 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 ?