I am solving https://codeforces.com/contest/1556/problem/C. I got an idea to use Stacks and Prefix Sums to find the answer, However, it is failing on test case 13. ↵
↵
<spoiler summary="Submission">↵
[162733730](https://codeforces.com/contest/1556/submission/162733730)↵
</spoiler>↵
↵
My Approach:↵
1. Iterate from left to right and calculate prefix sum of length upto index i. ↵
↵
2. Iterate from left to right and insert extra open brackets in stack with it's location i.↵
↵
3. When we get extra closing, pop the stack and match closing with opening.↵
↵
4. In every iteration insert matching subarray in a list, because we can use this to calculate number of ways to group matching subarrays.↵
↵
<spoiler summary="Submission">↵
[162733730](https://codeforces.com/contest/1556/submission/162733730)↵
</spoiler>↵
↵
My Approach:↵
1. Iterate from left to right and calculate prefix sum of length upto index i. ↵
↵
2. Iterate from left to right and insert extra open brackets in stack with it's location i.↵
↵
3. When we get extra closing, pop the stack and match closing with opening.↵
↵
4. In every iteration insert matching subarray in a list, because we can use this to calculate number of ways to group matching subarrays.↵