ABCSTR - Editorial

editorial
, , , ,
21

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

22

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

23

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

24

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

25

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

26

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

27

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.

28

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.

29

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