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.

7 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

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

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

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?

Why third condition is not important (b[j] - c[j] = b[i-1] - c[i-1])?

I DON KNOW Y MY SOLUTION GIVING WA…
PLZ HELP ME OUT
http://www.codechef.com/viewsolution/6740504

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 http://www.codechef.com/viewsolution/6740605

I tried to use Z algorithm, it gives me a wrong answer. I can’t find my mistake though.
Here is the link : https://www.codechef.com/viewsolution/9951173

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 : https://www.codechef.com/viewsolution/9448590

If some body can look, It would be of great help. Thanks

Hello.

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.

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