April19 - Problem Discussion

#21

I didnt attempted it.

#22

Can anyone tell me why this solution for FENCES gives AC for subtask 2 but not for 1?

#23

how do you know there will not be repetition of s1 s2

#24

@vijju123 as well as @taran_1407 (the setter) helped me in that problem…

I gave their names as a seed in the random function
vijju123 gave max score…

#25

You didn’t used @tarini_1407.

#26

My solution to `KLPM ( KMP? )`

Let me present my solution through an example.

Approach - For each pair of indices 1≤ i < j ≤ n ,find the number of ways of finding string `s1` and `s2` such that `s1 + s2` is a palindrome and `s1` start at i and `s2` end at j. Then we can just loop over all i and j and sum up to find our answer.

But HOW ?

Lets think inductively ( DP? )

Now consider this example
s = `abcdecba`

Consider i = 1 & j = 8
`a bcdecb a`

Now since, s_i == s_j implies it is possible to find such `s1` and `s2` ( Why? )

Clearly one such possibility is `s1 = "a"` and `s2 = "a"`

Next lets check for other ways :

• Case 1 : `s1 = "ab.."` and `s2 = "..ba"`. Clearly the number of ways of doing so is equal to number of ways of finding `s1` and `s2` with i = 2 and j = 7
• Case 2: `s1 = "ab.."` and `s2 = "a"`.
Aha! Now we arised with a problem, how many such strings are possible?
Should I loop and find out in O(n^3)?
Lets check what we actually need!
`Requirement 1` - Number of Palindromic substrings starting at i + 1 ( Isn’t it? )
• Case 3: `s1 = "a"` and `s2 = "..ba"`.
Kinda similar to Case 2!
Same requirement?
Nope! But similar!
`Requirement 2` - Number of Palindromic substrings ending at j - 1 ( Similar? )

Now, Our Target is to find these 2 requirements in O(n^2)

Requirement 1
For each pair 1 \le i \le j \le n Find the number of substrings ofs_i{s}_{i+1}......{s}_{j-1}s_j” which start with s_i and is a palindrome! ( Right? )

Similarly for Requirement 2

How?

`Hint: Make isPal[i][j] where isPal[i][j] = 1 if`s_i{s}_{i+1}......{s}_{j-1}s_j`is a Palindrome else isPal[i][j] = 0` ( DP? )

Link to My Solution KLPM ( KMP? )

#27

Hey @aniket_sanghi , what does FPal and BPal stores here?

That makes me not to understand how the ans dp is calculated

#28

FPal --> Requirement 1
BPal --> Requirement 2

#29

Hi aryanc403
If you have time can you please post an editorial of XORMIN show that a beginner like me can also understand, as the official editorial is very unclear to me and to the community as well.

Whats is the “dsu ninja technique” which you mentioned as a part of solution to XORMIN?

#30

Thanks! Aniket for your explanation and code, I am able to follow.

#31

How do you solve SONIQUE?

#32

Tried… It gave very less score

#33

I posted 3 pre req. One of them is on DSU.

#34

Good!!

#35

@l_returns How much score @taran_1407 + @tarini_1407 gives??

#36

I think now I know how to get max score in challenge problem!!