Is “a”-1 time and “b”-d times is valid solution ! as in this case total distinct solution will be 1*D which seems to satisfy the condition?
The answer was right in front of my eyes and I missed it
Why tf am I so dumb!!!
how did you get 29 and 25 can you show me the calculation
I never figured out how to get better on Ad-hoc constructives like this one, there are apparently no problemsets for getting better at ad-hoc, nor any particular strategy. Solution almost always seems like complete magic to me. Any ideas?
I used Approach 1, I think bojack was the easiest one in this July cook off
Who comes up with such problems anyway? Like wtf
Please someone explain the calculation part of second approach.
Approach 2: AAAAA…(D times) BBBBB…(D + 1 times)
No of palindromic substrings = x + y
where x = No. of palindromic substrings containing only A (eg. A, AA, AAA, …)
= 1 + 2 + …D
= (D) * (D + 1) / 2
Similiarly, y = No. of palindromic substrings containing only B (eg. B, BB, BBB, …)
= (D + 1) * (D + 2) / 2
Now,
No of distinct substrings = p + q + r
where
p = no of substrings containing only a = D (A, AA, …)
q = no of substrings containing only b = D + 1
r = no of substrings starting from a and ending in b = (D) * (D + 1)
Clearly, (p + q + r) - (x + y) = D
In the fourth test case the d was 63 during the contest and now they have changed it to 60 how they can assume people coming up with an adhoc solution while even the test case is not correct.
I was thinking of the approach :
- abcd… (d-different letters without repitition) for triangular values (1,3,6,10,15,…) of d
but could not work out solution for non-triangular values of d in time 
How to solve the same problem for minimum length such interested string or lexographically minimum length string satisfying the given properties!
i will never ever be good enough to solve these kind of problems 
shattered 
1 Like
@rajarshi_basu
please correct me if i am wrong .
we can also make with D =5;
“aaaaab”
in general D times ‘a’ and then ‘b’
observation is no. of total substring (D+1)(D+2)/2).
no of palindromic substring (D(D+1)/2); for D time ‘a’ and for ‘b’ alone is 1.
so total palindromic substring in D*(D+1)/2 + 1.
so, (D+1)(D+2)/2 - (D(D+1)/2 - 1 == D;
The calculations are correct, but that is not what the problem asked for.
The problem asks for the number of distinct substrings (in this case$2D+1$) minus the number of (non-distinct) palindromic substrings (D\cdot(D+1)/2+1).
My life has been lie 
but in que. it was clearly said that if same substring come twice then they are different substring.
i do not understand what ur saying please explain
The number of distinct substrings in S minus the number of palindromic substrings in S equals D. Here, when counting palindromic substrings, a substring that occurs multiple times should be counted multiple times.
For the substrings it contains the word <distinct>, indicating if they are the same sequence of characters they should only be counted once.
For the palindromic substrings there is no <distinct> mentioned. Furthermore they explicitly state <When counting palindromic substrings> before the statement that it should be counted multiple times.
Since many people seem to be confused about how to come up with such a solution, I created a little video on how I reasoned during the competition: