ABCSTR - Editorial

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 CodeChef: Practical coding for everyone

I tried to use Z algorithm, it gives me a wrong answer. I can’t find my mistake though.
Here is the link : 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

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

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?

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

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

same here …

@raul1rnjn535_3 : your code gives WA on AABBCCABCABC. it gives 11 while the correct output is 12.

Can anyone explain the intuition behind making those pairs in way specified above and searching it ? What kind of problems require this approach ?

Yes, using segment tree it can be solved with O(nlogn) time and space. Each node holds the following information:

(assume f(subarray) denotes a mapping of the substring containing A, B, C to some triplet (x, y, z) where x = #A, y = #B, z = #C)

  1. Total count of satisfying subarrays in the range
  2. Set of f(subarray) for each subarray starting at the left end of the range
  3. Set of f(subarray) for each subarray ending at the right end of the range
  4. f(range)

The relevant updates are also easy to figure out and allows to solve the whole problem in desired time complexity.

would you please explain your hash i.e. implementation and functionality

mp[make_pair(0,0)]++;

what is the use of this line