April19 - Problem Discussion


#21

I didnt attempted it. :slight_smile:


#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 :joy::joy:
vijju123 gave max score… :smiley:


#25

You didn’t used @tarini_1407. :angry: :angry: :angry:


#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 ifs_i{s}_{i+1}......{s}_{j-1}s_jis a Palindrome else isPal[i][j] = 0 ( DP? )

Still got Doubt? Ask in comments! :slight_smile:

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 :frowning:


#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 :neutral_face::joy:


#33

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


#34

Good!! :stuck_out_tongue:


#35

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


#36

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