Given a string S which is consisted of characters ‘A’, ‘B’ or ‘C’. Find the number of substrings of S which have equal number of ‘A’s, ‘B’s and ‘C’s.
EXPLANATION:
Let,
Ai = Number of ‘A’s in S between the indexes 1 and i (inclusive).
Bi = Number of ‘B’s in S between the indexes 1 and i (inclusive).
Ci = Number of ‘C’s in S between the indexes 1 and i (inclusive).
Let’s consider the substring Sj…i :
Number of ‘A’-s in that substring = Ai - Aj-1
Number of ‘B’-s in that substring = Bi - Bj-1
Number of ‘C’-s in that substring = Ci - Cj-1
So for that substring to be good: Ai - Aj-1 = Bi - Bj-1 = Ci - Cj-1
Alternatively the following two conditions are enough for that substring to be good:
Ai - Bi = Aj-1 - Bj-1
Ai - Ci = Aj-1 - Cj-1
Go from left to right and for each index i find the number of valid good substrings which ends at i. The number of such substrings would be the number of indexes k (k < i) where (Ai - Bi, Ai - Ci )= (Ak - Bk, Ak - Ck ). That can be obtained if the pair (Ak - Bk, Ak - Ck )for all k are stored in a key-value storage where the key being the pair and value being the number indexes having that difference pair. If using C++, STL Map can be used.
The author did not use a map, instead he computed all the difference pairs and then sorted those and then find the number of equal pairs.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Amazing insight you just showed me with the usage of map I still have a lot of ad-hoc thinking to do, that’s for sure
I tried to use DP to solve this problem…
I used something like:
DP[length_of_substr][start_ind][0] -> number of characters equal to A in substring s(start_ind,start_ind+size)
DP[length_of_substr][start_ind][1] -> number of characters equal to B in substring s(start_ind,start_ind+size)
DP[length_of_substr][start_ind][2] -> number of characters equal to C in substring s(start_ind,start_ind+size)
Then I tried to derive some relationships between these “DP states”, but in the end I was always getting a quadratic solution in the size of the string, i.e. O(|S|^2) and couldn’t figure out a better way of doing it…
I think the problem was that I got stuck on iterating over all sizes and for each size change the start index which would still be a quadratic solution, even if I could compute some states starting from others, for example:
DP[length_of_substr+1][0][0] = DP[length_of_substr][0][0] + 1, if the character at the (length_of_substr+1)th position is A, or we leave it as it is otherwise…
The Editorial is good and so was the problem. what i want to ask is that how we should approach such question during the contests.After two hours of continuous thinking,I was not able to come up with this idea
Hi all Please help me out as for all the test case that i have provided my code is working fine.But here its giving WRONG ANSWER CodeChef: Practical coding for everyone
Then I tried to use the naive method which is suppose to give a TLE but here yet again I am getting the wrong answer.
Here is the link : CodeChef: Practical coding for everyone
If some body can look, It would be of great help. Thanks
In the Tester’s solution, there is a line that increments the count of pair(0,0) -> “cnt[mp(0, 0)]++;”
Why is this done?
I got WA without this. Got AC after adding this line.
I still have a lot of ad-hoc thinking to do, that’s for sure 
