+1

14th Aug — educational codeforces round 93

15th Aug — atcoder beginner contest 175, Facebook hacker cup round 1,Codevita

16th Aug — codeforces Global round 10,Google Internship Test

BUSY DAY's

May I couldn't Perform well in these 3 days but i will learn many new things..

I am also excited!

All the Best

You can just brute force the answer, i was pretty annoyed that i did not manage to solve it during the contest https://codeforces.me/contest/1395/submission/89732090 ...

you will find it in Competitive Programmer’s Handbook(by Antti Laaksonen), page no.102.

I learned a lot from this book

you should ask this in the editorial part of that round, this is not related to this round.

div 2 I guess

for me educational rounds are easier than div2

Don't know which one is tougher. But for me, problems from educational rounds seem to be more interesting.

It's different for me, I enjoy solving standard Div 2 more, I usually get pretty upset while solving Educational rounds.

In educational rounds, all the problems have same weight-age, therefore there is no scoring distribution.

Thanks Codeforces for all the contests in this month

That's sick af.

Just chill!

Sorry to hear that man. Good luck today!

Hope you get well soon

Best wishes to you. I hope you will recover soon.

Educational rounds don't have pretests.

Can relate, I had WA on test 6 but then got stuck at WA on test 7.

For those wondering: test 7 could be something similar to

4 2 2
3 3 3 3
4 4
4 4

Some greedy approaches print 32, but the answer is 48.

Yes.

Why don't you like problem G? For an educational round, it is fine. I dislike E and F much more.

Don't be shy bro. Most of us started like that if you don't want to believe, just check my rating graph

I can relate to this & it even become worse when no one is there for help. Just keep practicing & don't hesitate to look for editorial & video solution. In case you need any help in A & B you can refer this

Could you please explain the states of your dp?

You need to do some greedy before this typical dp. This costed me 2 WA.

I don't think this was an easy problem. Maybe it's not hard to guess that the solution is dp but if you want to be sure that this solution is correct you need to prove that in the maximum total area obtained by using i red sticks, j green sticks and k blue sticks there exists a rectangle with sides (ri, gj) or (ri, bk) or (gj, bk). Maybe I'm missing something but it wasn't trivial and took me a while to prove.

You subtract 1 from every element and it becomes a standard problem. https://www.geeksforgeeks.org/number-subarrays-sum-exactly-equal-k/

first create prefix array then

then this should be true for subarray of (l,r) to be good.

prefix[r] - prefix[l - 1] = (r -l) + 1

l - prefix[l - 1] = r - prefix[r] + 1;

map<int,int> mp;
int ans = 0;
for(int i = 1; i <= n; i++){
    mp[i - prefix[i - 1]]++;
    int val = i - prefix[i] + 1 ;
    ans += mp[val];
}

My solution was a bit more complicated than cote's solution, but I think it is worth sharing. Let $$$p_i$$$ be the sum of the interval $$$a_{1, \ldots i}$$$ for all $$$i$$$ (prefix sums). Now let $$$c_i = p_i - i$$$. Notice that the number of good intervals starting in $$$1$$$ is the number of ocurrences of $$$0$$$ in $$$c_i$$$. For that we will keep a map $$$cnt$$$, where $$$cnt[x]$$$ is the number of ocurrences of $$$x$$$ in $$$c_i$$$. Now, we will "remove" the first element and update the prefix sums and $$$c_i$$$. Notice that all values of $$$c_i$$$ will change by a same value

Then we have that the

. So it is sufficient to keep a variable d and update it in each iteraction (and thre is no need to update $c_i$ or $$$p_i$$$). Submission: 89922879

i think it should be O(n) using hash map or something

After getting the prefix sums
Basically what you need to find is $$$pref[r] - pref[l - 1] = r - l + 1$$$
Equating that it becomes $$$pref[r] - r = pref[l - 1] - l + 1$$$
So at index i you need to count the indices $$$j \lt = i$$$ with $$$pref[i] - i == pref[j - 1] - j + 1$$$

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> prefix(n);
    prefix[0] = s[0] - '0';
    for (int i = 1; i < n; i++)
      prefix[i] += prefix[i - 1] + (s[i] - '0');
    map<int, int> dp;
    long long ans = 0;
    dp[1] = 1;
    for (int i = 0; i < n; i++) {
      if (i)
        dp[prefix[i - 1] - i + 1]++;
      int cur = prefix[i] - i;
      if (dp.count(cur))
        ans += dp[cur];
    }
    cout << ans << '\n';
  }
  return 0;
}

test:

4 2 2

3 3 3 3

4 4

4 4

your ans = 4 * 4 + 4 * 4 = 32

correct ans = 3 * 4 + 3 * 4 + 3 * 4 + 3 * 4 = 48