BOJACK - Unofficial Editorial

Problem: https://www.codechef.com/COOK120A/problems/BOJACK
Editorial:
I just thought the solution can be obtained using two distinct characters. Let’s say, we consider a string with nonzero 'a’s followed by nonzero 'b’s. Number of 'a’s and 'b’s = na and nb respectively.
Number of distinct substrings = na + nb + na * nb.
Number of palindromic substrings = (na * (na + 1)) / 2 + (nb * (nb + 1)) / 2
na + nb + na * nb - ( (na * (na + 1)) / 2 + (nb * (nb + 1)) / 2 )

On simplifying
(na + nb - (na - nb) * (na - nb)) / 2

if na == nb, this simplifies to (na + nb) / 2

So, (na + nb) / 2 = D
na = nb = D / 2

So, answer boils down to D times ‘a’ followed by D times ‘b’.

My Solution:
https://www.codechef.com/viewsolution/35789351

1 Like

After seeing this -

WhatsApp Image 2020-07-20 at 12.48.14 AM

Btw what is the main reason this is harder than “PATHETIC” in div 1 and easier in Div2

4 Likes