| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | djm03178 | 152 |
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.me/problemset/problem/1398/C
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".