Why third condition is not important (b[j] - c[j] = b[i-1] - c[i-1])?
@raul1rnjn535_3 : your code gives WA on AABBCCABCABC. it gives 11 while the correct output is 12.
I DON KNOW Y MY SOLUTION GIVING WA…
PLZ HELP ME OUT
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
Can anyone explain the intuition behind making those pairs in way specified above and searching it ? What kind of problems require this approach ?
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
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.
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)
- Total count of satisfying subarrays in the range
- Set of f(subarray) for each subarray starting at the left end of the range
- Set of f(subarray) for each subarray ending at the right end of the 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