ayush29azad's blog

Help!!!!!!!
By ayush29azad, history, 3 years ago, In English

Can someone help me in solving this problem?? The problem editorial is tough to understand. It can be solved using hashmap +prefix sum but I am not able to the get the pattern/observation.

C. Good Subarrays Educational Codeforces Round 93 Problem Link :https://codeforces.com/problemset/problem/1398/C

  • Vote: I like it
  • -12
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's suppose the string is "3001..."

We need to have a variable sum which stores the prefix sums.(when i=0 sum=3-1=2)

we'll have a map,(initially the count of map[0]=1 should be 1) whenever we read a character from string we increase the count of sum in the map (when i=0 we increase the count of 3-1=2 in the map).

when i=1 ,sum=2+(0-1)=1 we increase the count of 1 in the map.

when i=2, sum=1+(0-1)=0 we see that mp[sum]>0 so we add mp[sum] in the ans (ans=1) and increase mp[sum]. Now mp[sum] becomes 2.

when i=3, sum=0+(1-1)=0 mp[sum]==2 so we add mp[sum] in the ans (ans=3).

so the ans is 3. "300", "3001" ,"1".

→ Reply