| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 151 |
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.net/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".