ABCSTR - Editorial

PROBLEM LINK:

Practice
Contest

Author: Konstantin Sokol
Tester: Gerald Agapov
Editorialist: Tasnim Imran Sunny

DIFFICULTY:

Simple

PREREQUISITES:

Ad-Hoc, Map

PROBLEM:

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.

5 Likes

Is there any other way to do this problem ?

Hi,

Amazing insight you just showed me with the usage of map :slight_smile: I still have a lot of ad-hoc thinking to do, that’s for sure :slight_smile:

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…

I used somewhat similar technique… but it gave TLE!

1 Like

You can subtract A and B from C, for example :smiley:

Yes, maybe there could be some way that uses 10 interval trees and a sufix array, but I believe this is the simplest one.

You call it DP. I call it extremely inefficient prefix sums.

4 Likes

Even i did it using the same approach but i want to know if someone used a different approach cause it took me some time to figure out this approach.

Yeah, makes sense it’s inneficient, since, as I said, I was not managing to make it run in a decent time, and, looking at it again, it makes sense why this is inneficient, is there any way of solving this using a similar approach to the one I was trying to follow?

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

1 Like

What I recommend you is to solve the easier version first. This means you should come up with a solution for the AB strings. Then it’s relatively easy to find the solution for the ABC strings.
The trick to come up with the solution to the easier version is to basically write out every equation you have. For example, the condition is A_j - A_i = B_j - B_i, where A_i - A_j means the number of A characters in the range [i + 1, j]. Now play with the equation, so that we can work with it more flexible. With more experience you will realize that A_j - B_j = A_i - B_i is a good one to work with.

3 Likes

tle…

where is the code based on this implementations…i think it must give tle

you can use hash to solve instead of sort or map…
the complexity is nearly O(N)…
here is my solution: http://www.codechef.com/viewsolution/3642098

Please fix the solution links and tags are not-consistent.

same here …

This code gave me wrong answer…Can someone point out the error??
http://www.codechef.com/viewsolution/3636945

Its giving wrong answer can anyone look up and say the mistake
http://www.codechef.com/viewsolution/3643156

Hi all,

After reading editorial and looking at some of the Accepted solutions, here is my code, using the idea of the editorial:

http://www.codechef.com/viewsolution/3641990

:slight_smile:

Best,

Bruno

2 Likes

what is to be done after sorting the pairs?

Hi, can anyone give the link to the easier version of the problem involving only letters A and B?