+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.com/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 <= 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

I got WA on test 7 too and couldnt figure out where I went wrong. But then I realized this test case gave me a WA-

3 3 3 3 3 3 3 3 3 3 3 3

The answer to this should be 36 but it gives me 27. I hope this might help.

sum(l,r)=r-l+1

sum(l,r)-(r-l+1)=0

v[l]-1 + ... + v[r]-1 = 0

so just subtract 1 from every element, and find all sub arrays with sum==0

Calculate the prefix sums p[i]. If p[i]-p[j] = i-j, then j+1..i is a good subarray. However, this equation can be rearranged to p[i]-i = p[j]-j. It suffices to find all values of p[i]-i and use some math to calculate the number of pairs.

Here's a nice transformation:

Becomes much easier to code because the goal sum doesn't change.

Implemented segment tree and got WA on test 4.

Coordinate Compression + Segment Tree I saw other peoples' code also and they implemented it using set only but i don't know about it .

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

There are about 10^5 * 10^5 = 10^10 windows of all sizes. 10^10 things to do is too much for this time limit.

Can you explain a bit elaborate please :)

In educational rounds problem can be standard it is OK

I thought of using prefix sums to get sum of range in O(1) but still for every subarray to consider it will be O(N*N), Can you help me in understanding this a bit?

Can you tell me what is the need for a[i] to be between 0 and 9? It confused me a lot and consumed a lot of my time.

There is the case where some of the sides are equal.

I used 3d dp to solve it. Sort all the r, g, b arrays.

Now for state solve(i, j, k) => we can have 3 possibilities

1. solve(i-1, j-1, k) + r[i]*g[j]
2. solve(i, j-1, k-1) + g[j]*b[k]
3. solve(i-1, j, k-1) + r[i]*b[k]

Take max of all the three. You will have your answer.

Here is the link to code using above approach https://codeforces.com/contest/1398/submission/89925922

3 2 1 3 4 5 5 6 7

Check for this testcase

2 2 2

5 1

5 1

4 4

Correct Output (DP) : 41

Check out this test case:
1 2 2
7
5 3
6 2

Greedy gives 52 as an answer, but the correct one is 53.

I tried greedy too but failed miserably.

My Greedy solution for D was taking all the combination of 3 types of triangle. Since there can be 3 types of triangle, there are 200*200*200 combinations to choose from. Each combination tells how many triangles I will make of each type. I only worked with the valid combinations so that I don't get TLE. Then I am greedily taking the maximum product and not taking any more triangles of a type than what my combination says. Can anyone tell me why it does not work?

You can do it with just two sets. First set will contain k largest elements, and second set all other elements.

Treap can easily handle that.

Why k largest elements? Isn't it 2 * (sum of lightning) + sum of fire + maxfire — minlightning and if there is no lightning then simply sum of fire