April19 - Problem Discussion


#1

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


#2

Also, how to solve XORMIN?


#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
#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


#5

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


#6

it is the correct approach i also used the same one


#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 …


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


#9

But how does that make a difference?


#10

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


#11

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


#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


#13

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


#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


#15

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


#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?


#17

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


#18

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


#19

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


#20

What’s your idea of solving RECTARAN ?