Блог пользователя ayush29azad

Help!!!!!!!
Автор ayush29azad, история, 3 года назад, По-английски

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://mirror.codeforces.com/problemset/problem/1398/C

  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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".

→ Ответить