ganesh_6's blog

By ganesh_6, history, 7 weeks ago, In English

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.

Submission

My Approach: 1. Iterate from left to right and calculate prefix sum of length upto index i.

  1. Iterate from left to right and insert extra open brackets in stack with it's location i.

  2. When we get extra closing, pop the stack and match closing with opening.

  3. In every iteration insert matching subarray in a list, because we can use this to calculate number of ways to group matching subarrays.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ganesh_6 (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

debug yourself

»
6 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

cant actually figure it out.