Hello Codeforces!

On Aug/14/2020 17:35 (Moscow time) Educational Codeforces Round 93 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be **rated for the participants with rating lower than 2100**. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **6 or 7 problems** and **2 hours** to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | Um_nik | 7 | 111 |

2 | tmwilliamlin168 | 7 | 119 |

3 | neal | 7 | 144 |

4 | Farhod_Farmon | 7 | 167 |

5 | zdolny_kaczor | 7 | 178 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | Dorost | 13:-6 |

2 | dcordb | 3 |

3 | KnightKnight | 4:-4 |

85 successful hacks and 696 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem | Competitor | Penalty |
---|---|---|

A | MikMirzoyanov | 0:01 |

B | tamahom1 | 0:02 |

C | IAKWF | 0:02 |

D | shinigami11 | 0:09 |

E | dorijanlendvaj | 0:20 |

F | nikolapesic2802 | 0:08 |

G | tfg | 0:22 |

**UPD:** Editorial is out

Month of contests...... thanks CF <3

14th Aug — educational codeforces round 93

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

16th Aug — codeforces Global round 10

I am really excited!

+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

Google Internship Test, is it online? Can you provide the link?

yaa its online but registration date is over .

Still I would like to just check the link.

Yaa sure but it will show "No job found" as last registration date was 10 aug https://careers.google.com/jobs/results/88346779726029510/

I have registered for it as well, however, I was not informed of any internship test on 16th August. Is this because I was not shortlisted? Or did I miss some e-mail or detail? Can you please tell me your source of this information?

bro, did you get the mail regarding google internship test.Since, I also register for internship but haven't got any mail regarding this.

Not yet but my friends got. I registered at last date so, i guess they are sending email according to registration date

I also registered at last date and didn't get mail.

Yes ,I got the mail..

you forgot to mention this 13 Aug — (CodeChef) Dementia (Rated for Division 2). Set of problems was Awesome.

yeah agreed!

bro it has become unrated

Addition: 16th Aug — Leetcode Weekly Contest 202

thanks to codeforces for back to back contests.

can anyone tell me the soultion approach of codeforces div 2 664 c problem. http://codeforces.com/contest/1395/problem/C

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

but i dont understand the brute force logic

Every element of the array a (i will use the definitions from my code) can be combined with any element from the array b. So for every element with index i from a (i = 0 , N — 1) you create an array arr of M elements where arr[j] (j = 0 , M — 1) = a[i] & b[j]. If i == 0 (we are at the first element of the array) we mark in the bitset as true every element from arr and if i > 0 we will iterate over the bitset and we will mark as true in a new bitset the values val | arr[j] where val is a value from the first bitset which was already marked as true. By doing this at every step i (i = 0 , N — 1) you will have marked in the bitset every possible result for the expression c[0] | c[1] | ... c[i] (c having the meaning from the statement). After that you copy the second bitset in the first one. The bitset from the end will have marked as true every value which is a possible answer for the problem.

PS. 512 is the size of the bitset because the maximum possible answer is 511(2^9-1). I hope that my explanation is decent.

thanks bro

Really nice explanation !!

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

I learned a lot from this book

thanks bro

What thing are you mentioning about?

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

sorry bro

Standard Div2 round vs Educational round , which do you think is tougher ?

div 2 I guess

for me educational rounds are easier than div2

Educational is meant to have more standard problems, so they are generally easier

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.

+1

Hope we would see

cute ! cuter ! cutest !testerhere in ECR93 comment box also!!.I want to upvote testers once again

where is the comment-As a Tester give me a contribution..LOL

what is the scoring distribution?

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

Do all the problems have same difficulty too?

No, generally they are sorted in the order of non-decreasing difficulty.

Lucky month for competitive programmer

good contest

As a participant give me contribution.

I got covid 19, I am on my fourth day of isolation. I'm not feeling very well, but codeforces has helped me a lot to distract myself, wish me luck in this contest

Thanks Codeforces for all the contests in this month

That's sick af.

Literally

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.

I don't really understand why they say "6 or 7 problems". Aren't they sure about the number of problems till the last minutes?

Let us see what are we going to have today, long queue, weak pretest, complicated problem statement, or all of these together.

Educational rounds don't have pretests.

speed forces

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

WA on test case 6 LMFAO

Test 6 failed then try this:

1 3 1

10

8 5 3

12

Expected: 146

my code gives output:146..... but i got WA on 6

Ohh yes now I remeber there is some more issue. I changed my entire approach instead of doing greedy I went to DP.

can you please explain why the greedy logic does not work in problem D

I dont know fully. The test case I mentioned clearly show we have to do some case work when 2 colors with 1 pair and one with more than one remains. So may be some more such case work would be required to make it work. Has anyone solved this using Greedy, if yes please comment your submission id.

Try 2 2 2

2 2

2 2

2 2

ans: 12

Thanks

For those wondering: test 7 could be something similar to

Some greedy approaches print

`32`

, but the answer is`48`

.thx

now i got this . thanks bro

so true, this is something exactly happend with me.

Am I only one who couldn't access codeforces for almost an hour during the contest? (I posted this and got downvoted, idk why).

Yes.

just look at problem G today and you'll find you were wrong.

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

Could you explain your solution? I look at your code but cannot get it. Thanks in advance.

UPD: Nevermind, I understood it now. I think your sieve-like code for handling the largest divisor is so smart.

Will u plz tell , were E and F too boring or among the standard ones ??

They were definitely not standard problems, and for an educational round that wouldn't even be an issue. I didn't really like how E was pretty much an implementation exercise. Looking back, F wasn't actually that bad.

Yup .. Personally i also think that F was good , and also E was heavy implementation (especially for me who did coordinate compression and segment tree) .

It was really an educational round reminded me to study ..

I got problem A wrong, than was stuck on it to realise my initial idea was correct. Skipped B and went to solve C, cause I couldn't improve ranking at that point. Never solved C, I'm starting to believe I am dumb at this point...

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

True inspiration man! I've seen a few people with very slow progress get to the top, but never people who drop that low and rise to blue. Keeps me going, already. :)

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

What a nice contest but I think D is a little easy with typical DP

Could you please explain the states of your dp?

F[i][j][k]=maximum sum from first i largest R, j largest G, k largest B.

I'm not good at explaining things so sorry in advance if people feel my explaination harsh

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

as I said before, you must DP with i largest, j largest, k largest so you must sort three arrays before dp

Yeah, that's why it's not a classical dp. You need to be clever enough to get the idea.

Oh. I tryed to use dp but missed some status trans

Can you explain the state transition also?

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.how to solve C please help

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

Elaborate , coz i still dont get it.

When you subtract 1 from each element, the problem becomes counting the number of subarrays whose sum is 0.

OMFG. There is no way u came up with this during the contest. You had to have solved this type of problem earlier. Anyway,Thanks man!

how i realized it during the contest instead of writing it as

write it instead as

which is equivalent to

This is so beautiful <3

mpily really liked your thought process man... appreciable!!!

I saw the solution and was unable to digest why subtract by 1. Now it's clear. Thanks man.

your explanation is superb

to improve my rating i have to solve standard problems from geeksforgeeks or solve [roblem from codeforces,atcoder etc

Could you elaborate more?

The problem asks you to count the number of subarrays whose sum equals to its length right. So imagine if we subtract 1 from every element of that subarray, we end up subtracting the length of the subarray from the sum of its elements! If that subarray satisfy the condition of the problem statement then this new sum must be 0. That is why after subtracting 1 from all elements we count the number of subarrays whose sum is 0. Hope it helps.

That was so cool! Thanks.

Why are you adding map[cursum] everytime to the answer?

It is actually Map[cursum-0] which counts the number of prefixes ending before the current position. This number is equal to the number of subarray ending at the current position whose sum is 0. You could read the following article: 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;`

try to understand this part on your ownwow! awesome approach!

hey, i don't get why do you choose i as l and r?

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

dand update it in each iteraction (and thre is no need to update $c_i$ or $$$p_i$$$). Submission: 89922879Problem D.... why????

Solutiom of C in less than O(n^2)..??

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

linear solution or n(log n) solution is required

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$$$

CodeYou can convert it to pref[r]-pref[l] = r-l

pref[i] — i = pref[j-1] — j+1 pref[i] — i = pref[j-1] — (j-1) So basically find such pairs i & j (i!=j) such that this is tru?

Why dp[1]=1 ?Thanks

Notice for all $$$i$$$ I increase $$$pref[i - 1] - i + 1$$$

So for $$$i = 0$$$ $$$pref[i - 1] = 0$$$ and $$$pref[i - 1] - 0 + 1 = 0 - 0 + 1 = 1$$$

So basically I increase for $$$i = 0$$$ at the beginning

What was testcase 7 of problem D?

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.

Getting AC in D in like 10 mins but not getting any logic whatsoever for C hurts a lot.

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

I think C is more difficult than D...T^T.. How to solve C?

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.

oh...Thanks for your kind comment.

Here's a nice transformation:

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

wow.......

That's a very good solution tbh.

I exactly did this .. But took a quite more time

It was really good round, my nickname is lying :)

How to solve E? Can it be solved using set and priority_queue.

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 .

Can you tell your approach please.

please anyone tell what's wrong in my solution in D (it's giving WA on test#7)

https://codeforces.com/contest/1398/submission/89953351

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

what is test 5 in problem C!!!

How to solve C ?

can anyone help me out? I can't figure out why i failed test case 2 for problem c. I have created a consecutive sum array(i dont remember the actual name) and then checked for windows of all sizes.89943421

also will codeforces tell the failed test case 2 if i submit after the contest has ended?

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.

but I didnt get tle. I got incorrect answer. I can't figure out whats wrong.

Video Editorial for C. Good Subarrays

C is a standard problem often asked at AtCoder beginner rounds.[the idea is just to use prefix sums]

Edit: finally question reduces to find (i,j) pair such that j>i && pre[j]-pre[i]=j-i which can be easily solved using map.

Can you explain a bit elaborate please :)

Let $$$sum_{i}$$$ be the sum of elements till position $$$i$$$.

If you have two positions $$$i$$$ and $$$j$$$, $$$i \lt j$$$, if $$$sum_{i} - i = sum_{j} - j$$$, re-arranging the terms we see that $$$sum_{j} - sum_{i} = j - i$$$, i.e, the sum between their positions is clearly equal to the distance between them. So we just need to keep track of the count of elements with equal $$$sum_{i} - i$$$.

Now we note that since between all pairs with the same $$$sum_{i} - i$$$ the sum of elements must be equal to the distance between them, if the cnt of $$$sum_{i} - i$$$ occurs $$$k$$$ times, we have $$$k - 1$$$ subarrays which are adjacent to each other from which we want to form a subarray. So there are $$$k - 1$$$ ways of choosing $$$1$$$ continous subarrays, $$$k - 2$$$ of $$$2$$$ continous subarrays and so on, which is just the sum of the first $$$k -1$$$ natural numbers, or $$$\frac{(k - 1) \times k}{2}$$$ possible subarrays.

My submission: 89890437

elegant explanation.

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?

What you need is pre[r] — pre[l-1] = r — l + 1. You can rewrite this equation as pre[r] — r = pre[l-1] — (l-1), so for every good subarray, pre[i] — i is constant at the ends of it. Now you just have to make pairs

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.

for higher values of a[i] algo still works.

Yes, that 0 to 9 constraint created a lot of confusion for me.

There is no need. I think it was just to throw you off... All that mattered was subtracting 1 from every element and then doing prefix sums, and checking for 0.

Yes, that really threw me off. Wasted an hour on C ;_;

Any idea what is test case 2 of E or what is wrong with my idea?

My idea was as follows:

If after any operation we have $$$k$$$ lightning spells, then we need to keep track of the sum of the $$$k$$$ most powerful spells, while ensuring at max $$$k - 1$$$ of those are lightning spells (use a fire spell of power 0 as a dummy spell if needed). We can maintain the non-doubled spells using multisets in descending order and the doubled ones using multisets in ascending order for both types of spells. Change in sum can be tracked at the time of transistion of elements between these sets. Is the idea wrong or did I go wrong somewhere in implementation?

Hello, what was the idea in problem D? I assumed that it's always optimal to choose the first two biggest sides of different collor and add the area to the answer. I am really curious to know the problem since I got wrong answer on test 6!

same here bruh

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

That is not a problem since a square is also considered rectangle as we can understand from the test samples!

Suppose the largest side lengths in red and green are both 6. Do you take the pair from green or the pair from red? This decision may have an effect on the final answer, and it is not necessarily clear which one to pick just using a greedy algorithm.

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

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

This is a great idea, thank you. Probably my mistake was that I haven't found any counterexample during contest so I assumed that there is no need for backtraching stuff. (Or 3d dp)

using greedy is wrong because by doing so you might end up with a lesser number of rectangles ,which in turn might reduce the final output. For example lets say we have red array of size 20, green of size 20 and blue of size 190, using greedy u might use all the elements of red and green arrays first (resulting in just 20 rectangles) but there is a possibility of having 40 rectangles if u also choose elements from the blue array.

do we need to sort the array if i apply this logic, 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] 4. solve(i-1,j,k) 5. solve(i,j-1,k) 6. solve(i,j,k-1)

89945848 mine logic without sorting, can u point out where am i going wrong

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

Why greedy does't works for D??

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.

cool. How did you come up with this counterexample?

during the contest, when I kept on getting WA on test 6 (and eventually never got it)

I kept getting WA on test 6 too but I couldn't think of any counter example. So I believed that greedy algorithm should work. I spent 40 min staring at my code trying to find stupid implementation mistake xD.

A simpler one :

1 1 2

5

4

3 2

if we take 5 and 4 we can't include (3 and 2).

so optimal answer is 5*3+4*2

Could some one explain how come dp doesn't work without sorting the arrays?

I tried greedy too but failed miserably.

try this 2 1 4

3 2

3

2 2 2 2

greedy will give (3*3)+(2*2).But,we get a better answer if we take (3*2)+(3*2)+(2*2)

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?

tryed the same dude, now i know its wrong on 4 2 2 3 3 3 3 4 4 4 4

Correct output : 48 We got : 32

My solution is giving the correct output 48. Still don't why it won't work. Here's my last submission 89977686

What's the test 4 for problem E? I was using two sum segment tree one for lightning spells with twice the value of d and another for fire spell for value d. Also tracked minimum of lightning spells and maximum of fire spells by set and then computed the answer. Resulting WA on test 4.

89951160

In my submission, vectors are defined as sum -> lightning, sum2 -> fireball, v -> lightning, v2 -> fireball, st1 -> lightning, st2 -> fireball

Really nice Problemset :-)

In E I had to query the sum of the k largest elements. Is there a data structure that supports this?

I used a messy combination of segment and fenwick trees and the fact that we know all elements before.

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

Can you please explain the approach.

Since k can change by at most one, you will need to remove\add only 1 element. Also after inserting element you need to swap elements if minimum of first set is smaller than maximum of second set.

Treap can easily handle that.

Thanks. I never used a Treap before

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

My approach definitely wasn't the simplest

I see, I asked why my one is wrong? I am getting WA on test 4 implementing segment tree using this idea

Sometimes it is optimal to cast lightning, fire, lightning, fire, etc.

Got it now. Thanks.

Is it so? Consider the case where you have 3 lightning spell with damage 1,2,3 and 3 fire spell with damage 10,20,30. I believe the maximum damage should be 126 but your formula evaluates to 101.

Got it man. I was foolish enough to get it.

https://codeforces.com/contest/1398/submission/89908543 tm william's solution is very neat.

you can do that offline compressing all values and using segment tree.

Policy based data structures can also work (but I ended up getting WA for some reason)

You can write a Segment Tree for this. Main an a segment tree with each node having 2 attributes --> Sum and Count. Initially mark sum = 0 and count = 0.

Code for Add functionNow, since you have stored sum and count in each vertex, you can binary search of over it to find the sum of first k largest elements:

Code for query functionThe code provided is psuedocode.

Agreed.

Ciao Rating !

This game really pisses me off

In question D, why do we have to sort the arrays before applying DP, i code it without sorting but it was giving wrong ans but after sorting with same logic it was giving right ans?

code without sorting 89945848 give wrong ans. code with sorting 89955750 gives right ans.

Because you need to find the maximum area this could only be achieved when you consider longest pairs first.

Too sad, I can't implement E in time (in 30 mins) :((. How can I improve my coding speed

About problem C: Let's consider s[l], s[l+1], .., s[r] so if s[l]+s[l+1]+..+s[r] = r- l + 1 then s[l..r] is good s[l]+s[l+1]+..+s[r] = 1 + 1 + 1 + .. + 1 (r — l + 1) s[l] — 1 + s[l+1] — 1 + ... = 0 so the problem switches to finding the number of subarr (after decreasing by 1 each element) which has sum = 0 (can be easily done by map)

It seems testcases are weak on problem E, this slow solution passes. Go ahead and hack it! 89956850

Here's a simple alternate for C: Decrease all the values in the array by 1, and now you need to find the number of subarrays which has sum equal to 0.

Btw, how to solve F?

Let's try to find the answer for each len $$$l$$$.

Let $$$f(pos, len)$$$ = maximum possible number of sets that could have already finished considering $$$s[pos::]$$$ and number of contiguous rounds required is $$$len$$$.

Now, If $$$s[pos], s[pos+1] ...s[pos+len-1]$$$ doesn't contains both $$$1$$$ and $$$0$$$ then $$$f(pos,len) = 1 + f(pos+len, len)$$$.

Otherwise, find the minimum index $$$idx$$$ in $$$(pos, pos+len-1)$$$ such that $$$s[idx], s[idx+1]..s[pos+len]$$$ doesn't contains both 1 and $$$0$$$ and then $$$f(pos, len) = f(idx, len)$$$.

The time complexity of the solution will be $$$O(N+N/2+N/3...) = O(Nlog(N)).$$$

How do you perform step 3?

I use Segment Tree, so the total complexity is O(n*log(n)^2), and my submission runs in ~1.9s, nearly TLE.

For every index, Calculate the previous index such that it has one and also the previous index such that it has zero.

$$$if(s[pos+len]== ?)idx = min(prev_zero[pos+len], prev_one[pos+len]) +1$$$

$$$if(s[pos+len]==1)idx = prev_zero[pos+len] + 1$$$

$$$if(s[pos+len]==0)idx = prev_one[pos+len] + 1$$$

Can you elaborate more on this?

Short proof:

Thanks for this proof

I understood this proof but why we use frequency to calculate the total answer ?

The goal is to find all possible $$$l$$$ s for our current $$$r$$$.

Let $$$prefix(i) = A[1] + A[2] + ... + A[i]$$$. Suppose our current prefix sum $$$prefix(r) = x$$$. Since $$$prefix(r) - prefix(l-1) = A[l] + A[l+1] + ... + A[r-1] + A[r]$$$, then for all $$$j < r$$$ such that $$$prefix(j) = x$$$, we know $$$prefix(r) - prefix(j) = 0$$$. We keep the frequency of every $$$prefix(j)$$$ to search for how many of them are equal to $$$x$$$.

Thanks very much . i understood this approach very will.. but in general how can i know like these proofs by myself in the contest !? any suggestions to improve my skills ?

The trick with using prefix sums to calculate subarray sums is very common because it has so many uses. This particular problem is one that comes up every so often. You just need to keep practicing so that you'll learn these new techniques and remember them for future contests :)

Thanks very much

think of the brute force solution then optimize it, you can find the answer for any x in O(n) like this

pseudocodethis obviously takes $$$\mathcal{O}(N^2)$$$ but we can make it $$$\mathcal{O}(N * log(N))$$$, first for each i compute X[i] = biggest x such that $$$[i, i + x - 1]$$$ doesn't contain both 1s and 0, this can be done in O(n log n) using binary search and prefix sums, now in the loop above replace i += 1 by i = find(i, x) where find(i, x) returns the first j > i and X[j] >= x, this can be done using disjoint-set (initialize the parent[i] as first j > i with X[j] > X[i]) and modify the find function slightly

could E BE more boring ?

Well，I think problem E is fine because I consolidated the segment tree from it._(:з」∠)_

i see the answer for

"C. Good Subarrays"in this content but i still can't understand it can any one help me?if you just subtract 1 from all the elements, you will have little different array.

but now, you need to find all the subarrays with count 0.

Why?https://stackoverflow.com/questions/26532723/counting-all-contiguous-sub-arrays-given-sum-zero

here is how to deal with this problem from this perspective

$$$sum_r-sum_l=r-l \implies sum_r-r=sum_l-l$$$

Can anybody tell me what i'm missing in Problem D , Locally on G++ 17 all sample test case gave right answer but on CF it is giving WA on 2nd testcase while using G++ 14 and WA on 3rd test case while using G++ 17 . Link to the Code for Problem D : https://ideone.com/i0idJr

W

Done

In problem D why is it important to sort. . . . My thinking, If I'm using exhaustive search using dp, it should give the optimal answer, int this case max area, without even sorting. Please clarify this for me. Thanks

Let's say we have two pairs of one type with lengths $$$a_1, a_2 (a_1 \le a_2)$$$, and two pairs of another type with lengths $$$b_1, b_2 (b_1 \le b_2)$$$, then it's optimal to create a rectangle of sides $$$a_2, b_2$$$ and a rectangle $$$a_1,b_1$$$. This is easy to prove.

So, after sorting once we pair $$$i$$$ on first array with $$$j$$$ on second array, we'll never pair $$$k < i$$$ on first array with $$$z > j$$$ on second array. So we keep a classic DP.

$$$dp[i][j][j]: $$$max total area using pairs till $$$i$$$ on first array, till $$$j$$$ on second array and till $$$k$$$ on third array.

If I'm using exhaustive search using dpNo we are not doing exhaustive search , if we are pairing one from red and one from green , they must be of highest length in there category .

Did you asked yourself how transition will take place (i.e how we will find $$$dp[i][j][k]$$$ with the help of some lower $$$i,j,k$$$) ?

$$$dp[i][j][k] = max(dp[i-1][j-1][k]+A_i*A_j,dp[i][j-1][k-1]+A_j*A_k,dp[i-1][j][k-1]+A_i+A_k)$$$

while taking $$$A_i*A_j$$$ , we will take the maximum ones and thus we need to sort.

Please provide a test case where Greedy approach in problem D fails

Consider this test case: 2 2 2

5 5

4 4

3 3

How to solve $$$G$$$ without bitsets? Faster than $$$O(X^2/32)$$$

fft

Nice! Karatsuba also works.

Can you please explain your complete approach ?...

I know that if we have (a[i] — a[j] == t) for some i,j(i > j) and t then we can use an approach similar to sieve and solve... but not getting the fact what is the exact purpose of using fft ?

FFT can be used to get these values $$$t$$$. For this we should calculate $$$(x^{a_0} + x^{a_1} + ... + x^{a_N})*(x^{-a_0} + x^{-a_1} + ... + x^{-a_N})$$$. If coefficient at $$$x^{t}$$$ $$$!=0$$$, then there are exist $$$i$$$ and $$$j$$$ such that $$$a[i]-a[j]==t$$$.

How to solve G with bitset?

Problem C becomes so beautiful after realizing its logic.

One more solution to solve such types of problems.

Let $$$pref[i] = s[1] + s[2] ... + s[i]$$$

Thus required subarrays $$$(s[L...R])$$$ will follow this property,

$$$pref[R] - pref[L-1] = R-L+1$$$

$$$pref[R] - R = pref[L-1] - (L-1)$$$

Or, Basically you can choose any two index such that their $$$pref[i]-i$$$ is samefor both of them. Now, it's basic $$$O(N)$$$ task, using $$$C(freq, 2)$$$ for every frequency of $$$pref[i]-i$$$.

[deleted]

I have submitted 2 identical solutions for problem C. Solution A: 89960181 Solution B: 89960214 The only difference between the two is on line 22: In one approach I use an integer to represent the index while in the other I use a long long. I also use in both cases a long long to represent an index in line 53.

Why does one solution pass while the other doesn't? I've already read many forums regarding the indexing on arrays in C++. Nowhere did I found that it says that a long long will cause problems when indexing with it.

You didn't initialize variable out 89961488

Thnx dude I mean I broke my head to figure it out. It is weird thought the fact that 89960214 gets AC. I mean I do not initialize

outand because I used an integer for indexing it works for some reason XDO(n) solution of C with HashMap 89943214

why the greedy solution of D — "pick two largest pair every time" fails?

Counterexample:

R: 3 4 5

G: 5 6

B: 7

If you take 2 biggest elements of different colours you'll end up with: 7 * 6 + 5 * 5 = 67

Though the optimal split is: 7 * 5 + 6 * 4 + 5 * 3 = 35 + 24 + 15 = 74

-> That greedy pairs the both 10 instead of 9,10 + 9,10.

spooky mah boi , why you oscillate between colors so much ?

The crazy problem setters create weird problems ;)

No seriously, one limitation for me is the ability to concentrate, I am sometimes not able to implement simple tasks, like todays C, even if I know how it works.

When you fell from CM to specialist, I just thought that you are trying to get a record of biggest rating change.

Yeah, problem setters set such problems that if you get some WA, debugging would take a lot of time. This affects me too.

Why is my approach for C failing?

My approach:Every good subarray should start with some index, so i'll brute force for every index checking it for lengths (1,2,...9) . Time complexity O(9*n). It failed for many, example => s = "11140000000090000000002111" , correct ans = 37 , my ans = 29Consider an array full of 1's. In your solution you ignore good subarrays of length more than 9, which is not correct

Shit my bad, thanks :)

in c i storedd arr[i]-1 for each array and counted the no of subarrays with sum 0 balancing excess with shortage!

why my code for D is giving TLE. It is using same approach as DP solution.

codeClose enough, but learn dp, you'll see why it fails.

i have tried to do DP problems but most of the times i fail to think of a DP solution

You are passing whole copy of vector in the function. Just use an integer for index.

I think

`rgb()`

is called for same vectors several times. It's same as when you find the nth element of Fibonacci sequence by iterative method or recursive method.The other thing is that whenever you call

`rgb()`

it will copy all data from current vector to the next function but in DP no.(Sorry for my bad English)

ok i will try to implement DP solution then. my bad i couldn't think of it during contest(sad emoji)

Spoiler(Sorry for my bad English)

My screencast, if you want to enjoy my fingers suffering from typing so much (video solutions for A-E included)

Why are the hacks shown on the hacking page in reverse order, like the most recent hack is at the end?

If anyone has used memoization for D pls do share your code.It would be a great help for a beginner like me as i am learning dp . Thanks in advance

Hope this helps https://codeforces.com/contest/1398/submission/89925922

Thank you broh once again ..this was my first time asking help on cf comment section and IAM really hopeful that the people here will help throughout my journey in becoming a good coder

what is the problem in my code for D question? can anyone help me?

Here is my code that passes everything:

CODEI believe your mistake is this line:

`if((i>=a and j>=b) || (i>=a and k>=c) || (j>=b and k>=c)) return 0;`

Instead using ternary operators, like I did solves it. Why? Here's an example. If we take this line into consideration:

`arr[i]*brr[j]+func(i+1,j+1,k)`

We only care if either i or j is greater than a or b in your case. This means that we should not check for (i >= a && j >= b), but for (i >= a || j >= b), since one element is already out of bounds and there is no solution but your code cares only whether both elements are out of bounds, that allows space for error.

Yaa I got Your point. Thanks!!:D

Got WA on Test 6 in Question D. The 6th test case given is not intuitive.Can anyone help me out with a intuitive test case similar to the test which is used in testing.My solution is a greedy approach, but not a general one.So test cases such as the below test case will result in correct answer.This is my solution 89953296.

4 2 2

3 3 3 3

4 4

4 4

This test case results in correct answer for my solution.

3 3 3

2 8 5

1 10 5

9 9 3

Correct answer : 10*9 + 8*9 + 5*5 + 2*3 = 193

Your answer : 182

I guess people are making fake ids just to hack those submissions afterwards. Deliberately a stupid if case is added to be hacked afterwards XD.

89940459

The hacked guy likes 78788 a lot I guess. One more of his solutions from another contest using his fake id Noob_is_back got hacked. See this 87193319 and you'll find 78788 again in the code. The hackers are still grey :)

Why we use frequency in problem C ?

My hack has been on "waiting" since this morning. It's not just when I'm logged in, it shows up like that on an incognito tab as well.

In the meantime before editorial is published and for those interested, here is the 3Blue1Brown styled visual editorial for Problem C, visualizing tmwilliamlin168's code (89883985). I have also given a somewhat formal proof before visualizing 1st input of Test Case #5

Link to visual editorial here

how to check the time it takes for the submission when hacking?

I love problem D very much!!

How to solve E?

I use the line segment tree (weighted segment tree). In fact, it is easy to find that the answer to problem E each line:ans = the sum of the largest number in the first K + the sum of all the numbers (here K refers to how many numbers can be doubled)

Then we read all the values first, sort them (discretize them), and then read the input of the problem again (which has been changed by array storage in advance)

We maintain the weighted line segment tree every time, that is, we ask the sum of the top k numbers in the 1-n interval every time. For example, to find the sum of the top 4 numbers, I will first ask whether the number of the right subtree (because the number stored on the right is larger than the number on the left) is less than 4. If so, enter it directly and return the sum of the top 4 numbers under the right subtree. If not, directly Select the sum of the prior numbers of the right subtree and add the sum of the first k = 4-num [RS] numbers under the left subtree (Num [RS] represents the first number of the right subtree),and then return it.

In short, the answer is to ask the sum of the top k numbers on the line segment tree and add the values of all the current numbers

(PS: but note that if the minimum value of all the numbers that can be doubled is greater than the maximum value of the number that can't be doubled, we can't simply choose the top k, but we should choose the top K + 1 and subtract the minimum value of the double number, because one can't double itself.)

Well, I am having tough time to understand this.

Maybe my expression is not clear, but you can find ideas from it. It must be feasible because I passed after the contest.

any news about the tutorial?

why this code 89922404 for problem C won't get TLE

The first three lines makes the code really fast.

Why are Educational Rounds always so late with editorials?

Because of the 12 hour open hacking phase, I guess.

Can someone help me in D. I used a 3d dp approach, which finds the maximum value using 6 cases. However, it failed on test 5. Here is the failed submission, while here is the one that passes. What does sorting do?

It's always optimal to chose pairs with the maximum product. So we sort those three lists in decreasing order and take pairs from top of them. But when we have multiple options for pairs with the maximum product we don't know which one we should take without looking at the next values and that's why we do dp.

$$$dp_{i,j,k} = max(dp_{i,j+1,k+1},dp_{i+1,j+1,k},dp_{i+1,j,k+1})$$$ = maximum area we can achieve when we have already taken first $$$i$$$, $$$j$$$ and $$$k$$$ values of the first, second and third array (according to $$$0$$$ based indexing).

I found your explanation easy to understand, can you tell what does

dp[i] [j] [k]stands for i.e what is the meaning of each cell of dp, can you please elaborate it more.