By awoo, history, 6 months ago, translation,

Hello Codeforces!

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 Proszek_na_ludka 7 178

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Amir_Reza 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

• +478

 » 6 months ago, # |   +56 Month of contests...... thanks CF <3
 » 6 months ago, # | ← Rev. 2 →   +71 14th Aug — educational codeforces round 9315th Aug — atcoder beginner contest 175, Facebook hacker cup round 116th Aug — codeforces Global round 10I am really excited!
•  » » 6 months ago, # ^ |   0 +1
•  » » 6 months ago, # ^ | ← Rev. 4 →   0 14th Aug — educational codeforces round 9315th Aug — atcoder beginner contest 175, Facebook hacker cup round 1,Codevita16th Aug — codeforces Global round 10,Google Internship TestBUSY DAY'sMay I couldn't Perform well in these 3 days but i will learn many new things..I am also excited!All the Best
•  » » » 6 months ago, # ^ |   0 Google Internship Test, is it online? Can you provide the link?
•  » » » » 6 months ago, # ^ |   0 yaa its online but registration date is over .
•  » » » » » 6 months ago, # ^ |   0 Still I would like to just check the link.
•  » » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 Yaa sure but it will show "No job found" as last registration date was 10 aug https://careers.google.com/jobs/results/88346779726029510/
•  » » » » » » » 6 months ago, # ^ |   0 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?
•  » » » 6 months ago, # ^ |   0 bro, did you get the mail regarding google internship test.Since, I also register for internship but haven't got any mail regarding this.
•  » » » » 6 months ago, # ^ |   0 Not yet but my friends got. I registered at last date so, i guess they are sending email according to registration date
•  » » » » » 6 months ago, # ^ |   0 I also registered at last date and didn't get mail.
•  » » » » 6 months ago, # ^ |   0 Yes ,I got the mail..
•  » » 6 months ago, # ^ |   0 you forgot to mention this 13 Aug — (CodeChef) Dementia (Rated for Division 2). Set of problems was Awesome.
•  » » » 6 months ago, # ^ |   -14 yeah agreed!
•  » » » 6 months ago, # ^ |   0 bro it has become unrated
•  » » 6 months ago, # ^ |   0 Addition: 16th Aug — Leetcode Weekly Contest 202
 » 6 months ago, # |   0 thanks to codeforces for back to back contests.
 » 6 months ago, # |   -24 can anyone tell me the soultion approach of codeforces div 2 664 c problem. http://codeforces.com/contest/1395/problem/C
•  » » 6 months ago, # ^ |   +1 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 ...
•  » » » 6 months ago, # ^ |   -6 but i dont understand the brute force logic
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   +11 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.
•  » » » » » 6 months ago, # ^ |   +20 thanks bro
•  » » » » » 6 months ago, # ^ |   0 Really nice explanation !! thank you
•  » » 6 months ago, # ^ |   +1 you will find it in Competitive Programmer’s Handbook(by Antti Laaksonen), page no.102.I learned a lot from this book
•  » » » 6 months ago, # ^ |   0 thanks bro
•  » » » 6 months ago, # ^ |   0 What thing are you mentioning about?
•  » » 6 months ago, # ^ |   +14 you should ask this in the editorial part of that round, this is not related to this round.
•  » » » 6 months ago, # ^ |   0 sorry bro
 » 6 months ago, # |   -8 Standard Div2 round vs Educational round , which do you think is tougher ?
•  » » 6 months ago, # ^ |   +20 div 2 I guess
•  » » 6 months ago, # ^ |   +4 for me educational rounds are easier than div2
•  » » 6 months ago, # ^ |   -24 Educational is meant to have more standard problems, so they are generally easier
•  » » 6 months ago, # ^ | ← Rev. 2 →   +17 Don't know which one is tougher. But for me, problems from educational rounds seem to be more interesting.
•  » » 6 months ago, # ^ |   +8 It's different for me, I enjoy solving standard Div 2 more, I usually get pretty upset while solving Educational rounds.
•  » » » 6 months ago, # ^ |   0 +1
 » 6 months ago, # |   -51 Hope we would see cute ! cuter ! cutest ! tester here in ECR93 comment box also!!.
 » 6 months ago, # |   -39 I want to upvote testers once again
 » 6 months ago, # |   -18 where is the comment-As a Tester give me a contribution..LOL
 » 6 months ago, # |   -23 what is the scoring distribution?
•  » » 6 months ago, # ^ |   0 In educational rounds, all the problems have same weight-age, therefore there is no scoring distribution.
•  » » » 6 months ago, # ^ |   -13 Do all the problems have same difficulty too?
•  » » » » 6 months ago, # ^ |   0 No, generally they are sorted in the order of non-decreasing difficulty.
 » 6 months ago, # |   -13 Lucky month for competitive programmer
 » 6 months ago, # | ← Rev. 2 →   -22 good contest
 » 6 months ago, # |   -51 As a participant give me contribution.
 » 6 months ago, # |   +148 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
•  » » 6 months ago, # ^ |   0 Thanks Codeforces for all the contests in this month
•  » » 6 months ago, # ^ |   +5 That's sick af.
•  » » » 6 months ago, # ^ |   -21 Literally
•  » » 6 months ago, # ^ |   +12 Just chill!
•  » » 6 months ago, # ^ |   +18 Sorry to hear that man. Good luck today!
•  » » 6 months ago, # ^ |   +9 Hope you get well soon
•  » » 6 months ago, # ^ |   +3 Best wishes to you. I hope you will recover soon.
 » 6 months ago, # |   +33 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?
 » 6 months ago, # |   -62 Let us see what are we going to have today, long queue, weak pretest, complicated problem statement, or all of these together.
•  » » 6 months ago, # ^ |   +7 Educational rounds don't have pretests.
 » 6 months ago, # |   0 speed forces
 » 6 months ago, # |   +31
•  » » 6 months ago, # ^ | ← Rev. 2 →   +4 Can relate, I had WA on test 6 but then got stuck at WA on test 7.
•  » » » 6 months ago, # ^ |   +3 WA on test case 6 LMFAO
•  » » » » 6 months ago, # ^ |   +8 Test 6 failed then try this: 1 3 1 10 8 5 3 12 Expected: 146
•  » » » » » 6 months ago, # ^ |   0 my code gives output:146..... but i got WA on 6
•  » » » » » » 6 months ago, # ^ |   0 Ohh yes now I remeber there is some more issue. I changed my entire approach instead of doing greedy I went to DP.
•  » » » » » » » 6 months ago, # ^ |   0 can you please explain why the greedy logic does not work in problem D
•  » » » » » » » » 6 months ago, # ^ |   0 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.
•  » » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 Try 2 2 2 2 2 2 2 2 2 ans: 12
•  » » » » » 6 months ago, # ^ |   0 Thanks
•  » » 6 months ago, # ^ | ← Rev. 2 →   +16 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.
•  » » » 6 months ago, # ^ |   0 thx
•  » » » 6 months ago, # ^ |   0 now i got this . thanks bro
•  » » 6 months ago, # ^ |   0 so true, this is something exactly happend with me.
 » 6 months ago, # |   0 Am I only one who couldn't access codeforces for almost an hour during the contest? (I posted this and got downvoted, idk why).
•  » » 6 months ago, # ^ |   +13 Yes.
 » 6 months ago, # |   0 It seems nowadays codeforces has better problems than atcoder... — aid just look at problem G today and you'll find you were wrong.
•  » » 6 months ago, # ^ |   0 Why don't you like problem G? For an educational round, it is fine. I dislike E and F much more.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » 6 months ago, # ^ |   0 Will u plz tell , were E and F too boring or among the standard ones ??
•  » » » » 6 months ago, # ^ |   0 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.
•  » » » » » 6 months ago, # ^ |   0 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) .
 » 6 months ago, # |   +3 It was really an educational round reminded me to study ..
 » 6 months ago, # |   +3 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...
•  » » 6 months ago, # ^ |   0 Don't be shy bro. Most of us started like that if you don't want to believe, just check my rating graph
•  » » » 6 months ago, # ^ |   0 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. :)
•  » » 6 months ago, # ^ |   +1 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
 » 6 months ago, # |   +17 What a nice contest but I think D is a little easy with typical DP
•  » » 6 months ago, # ^ |   0 Could you please explain the states of your dp?
•  » » » 6 months ago, # ^ |   0 F[i][j][k]=maximum sum from first i largest R, j largest G, k largest B.
•  » » » 6 months ago, # ^ |   +4 I'm not good at explaining things so sorry in advance if people feel my explaination harsh
•  » » 6 months ago, # ^ |   0 You need to do some greedy before this typical dp. This costed me 2 WA.
•  » » » 6 months ago, # ^ |   +3 as I said before, you must DP with i largest, j largest, k largest so you must sort three arrays before dp
•  » » » » 6 months ago, # ^ |   +11 Yeah, that's why it's not a classical dp. You need to be clever enough to get the idea.
•  » » » » » 6 months ago, # ^ |   0 Oh. I tryed to use dp but missed some status trans
•  » » » » 6 months ago, # ^ |   0 Can you explain the state transition also?
•  » » 6 months ago, # ^ |   0 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.
•  » » 6 months ago, # ^ |   +47 You subtract 1 from every element and it becomes a standard problem. https://www.geeksforgeeks.org/number-subarrays-sum-exactly-equal-k/
•  » » » 6 months ago, # ^ |   0 Elaborate , coz i still dont get it.
•  » » » » 6 months ago, # ^ |   +10 When you subtract 1 from each element, the problem becomes counting the number of subarrays whose sum is 0.
•  » » » » » 6 months ago, # ^ |   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!
•  » » » » » » 6 months ago, # ^ |   +38 how i realized it during the contest instead of writing it as $\sum_{l}^{r} ( a_i ) = r-l+1$write it instead as $\sum_{l}^{r} ( a_i ) = \sum_{l}^{r}(1)$which is equivalent to $\sum_{l}^{r} ( a_i ) - \sum_{l}^{r}(1) = 0$
•  » » » » » » » 6 months ago, # ^ |   +8 This is so beautiful <3
•  » » » » » » » 6 months ago, # ^ |   +9 mpily really liked your thought process man... appreciable!!!
•  » » » » » » » 6 months ago, # ^ |   +3 I saw the solution and was unable to digest why subtract by 1. Now it's clear. Thanks man.
•  » » » » » » » 6 months ago, # ^ |   +3 your explanation is superb
•  » » » » » 6 months ago, # ^ |   0 to improve my rating i have to solve standard problems from geeksforgeeks or solve [roblem from codeforces,atcoder etc
•  » » » 6 months ago, # ^ |   +1 Could you elaborate more?
•  » » » » 6 months ago, # ^ |   +29 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.
•  » » » » » 6 months ago, # ^ |   0 That was so cool! Thanks.
•  » » » 6 months ago, # ^ |   0 Why are you adding map[cursum] everytime to the answer?
•  » » » » 6 months ago, # ^ |   0 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/
•  » » 6 months ago, # ^ | ← Rev. 3 →   +12 first create prefix array thenthen 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 ownmap 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]; } 
•  » » » 6 months ago, # ^ |   +1 wow! awesome approach!
•  » » » 6 months ago, # ^ |   0 hey, i don't get why do you choose i as l and r?
•  » » 6 months ago, # ^ |   0 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 $d + c_i = c_i - a_0 - (i - 1) \Rightarrow d = -a_0 + 1.$Then we have that the $cnt[x] = cnt[x - d]$. 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
 » 6 months ago, # |   +1 Problem D.... why????
 » 6 months ago, # |   0 Solutiom of C in less than O(n^2)..??
•  » » 6 months ago, # ^ |   0 i think it should be O(n) using hash map or something
•  » » 6 months ago, # ^ |   0 linear solution or n(log n) solution is required
•  » » 6 months ago, # ^ | ← Rev. 3 →   +4 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$ Code#include 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 prefix(n); prefix[0] = s[0] - '0'; for (int i = 1; i < n; i++) prefix[i] += prefix[i - 1] + (s[i] - '0'); map 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; } 
•  » » » 6 months ago, # ^ |   0 You can convert it to pref[r]-pref[l] = r-l
•  » » » 6 months ago, # ^ |   0 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?
•  » » » 6 months ago, # ^ |   0 Why dp[1]=1 ?Thanks
•  » » » » 6 months ago, # ^ |   0 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
 » 6 months ago, # |   0 What was testcase 7 of problem D?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +8 test:4 2 23 3 3 34 44 4your ans = 4 * 4 + 4 * 4 = 32correct ans = 3 * 4 + 3 * 4 + 3 * 4 + 3 * 4 = 48
•  » » 6 months ago, # ^ |   0 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 3The answer to this should be 36 but it gives me 27. I hope this might help.
 » 6 months ago, # | ← Rev. 3 →   +3 Getting AC in D in like 10 mins but not getting any logic whatsoever for C hurts a lot.
•  » » 6 months ago, # ^ |   +4 sum(l,r)=r-l+1sum(l,r)-(r-l+1)=0v[l]-1 + ... + v[r]-1 = 0so just subtract 1 from every element, and find all sub arrays with sum==0
 » 6 months ago, # |   +4 I think C is more difficult than D...T^T.. How to solve C?
•  » » 6 months ago, # ^ |   +8 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.
•  » » » 6 months ago, # ^ |   +1 oh...Thanks for your kind comment.
•  » » 6 months ago, # ^ | ← Rev. 2 →   +47 Here's a nice transformation: \begin{align} & \sum\limits_{i=l}^r a_i = r - l + 1 \\ \implies & \left( \sum\limits_{i=l}^r a_i \right) - (r - l + 1) = 0 \\ \implies & \left( \sum\limits_{i=l}^r a_i \right) - \left( \sum\limits_{i=l}^r 1 \right) = 0 \\ \implies & \sum\limits_{i=l}^r (a_i - 1) = 0 \end{align}Becomes much easier to code because the goal sum doesn't change.
•  » » » 6 months ago, # ^ |   0 wow.......
•  » » » 6 months ago, # ^ |   0 That's a very good solution tbh.
•  » » » 6 months ago, # ^ |   0 I exactly did this .. But took a quite more time
 » 6 months ago, # |   +38 It was really good round, my nickname is lying :)
 » 6 months ago, # |   +3 How to solve E? Can it be solved using set and priority_queue.
•  » » 6 months ago, # ^ |   0 Implemented segment tree and got WA on test 4.
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Coordinate Compression + Segment Tree I saw other peoples' code also and they implemented it using set only but i don't know about it .
•  » » » 6 months ago, # ^ |   0 Can you tell your approach please.
 » 6 months ago, # |   0 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
•  » » 6 months ago, # ^ |   +9 test:4 2 23 3 3 34 44 4your ans = 4 * 4 + 4 * 4 = 32correct ans = 3 * 4 + 3 * 4 + 3 * 4 + 3 * 4 = 48
 » 6 months ago, # |   0 what is test 5 in problem C!!!
 » 6 months ago, # |   0 How to solve C ?
 » 6 months ago, # |   0 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
•  » » 6 months ago, # ^ |   0 also will codeforces tell the failed test case 2 if i submit after the contest has ended?
•  » » 6 months ago, # ^ |   0 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.
•  » » » 6 months ago, # ^ |   0 but I didnt get tle. I got incorrect answer. I can't figure out whats wrong.
 » 6 months ago, # |   -26 Video Editorial for C. Good Subarrays
 » 6 months ago, # | ← Rev. 3 →   +7 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.
•  » » 6 months ago, # ^ |   0 Can you explain a bit elaborate please :)
•  » » » 6 months ago, # ^ | ← Rev. 4 →   +17 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
•  » » » » 6 months ago, # ^ |   0 elegant explanation.
•  » » 6 months ago, # ^ |   +18 In educational rounds problem can be standard it is OK
•  » » 6 months ago, # ^ |   +1 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?
•  » » » 6 months ago, # ^ |   +1 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
•  » » 6 months ago, # ^ |   +6 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.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 for higher values of a[i] algo still works.
•  » » » » 6 months ago, # ^ |   +4 Yes, that 0 to 9 constraint created a lot of confusion for me.
•  » » » 6 months ago, # ^ |   +3 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.
•  » » » » 6 months ago, # ^ |   +3 Yes, that really threw me off. Wasted an hour on C ;_;
 » 6 months ago, # | ← Rev. 3 →   0 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?
 » 6 months ago, # |   +1 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!
•  » » 6 months ago, # ^ |   0 same here bruh
•  » » 6 months ago, # ^ |   0 There is the case where some of the sides are equal.
•  » » » 6 months ago, # ^ |   0 That is not a problem since a square is also considered rectangle as we can understand from the test samples!
•  » » » » 6 months ago, # ^ |   0 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.
•  » » 6 months ago, # ^ |   +2 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 solve(i-1, j-1, k) + r[i]*g[j] solve(i, j-1, k-1) + g[j]*b[k] 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
•  » » » 6 months ago, # ^ |   0 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)
•  » » » » 6 months ago, # ^ |   0 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.
•  » » » 6 months ago, # ^ |   0 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
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 3 2 1 3 4 5 5 6 7
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Check for this testcase2 2 2 5 15 1 4 4 Correct Output (DP) : 41
 » 6 months ago, # |   0 Why greedy does't works for D??
•  » » 6 months ago, # ^ | ← Rev. 2 →   +6 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.
•  » » » 6 months ago, # ^ |   0 cool. How did you come up with this counterexample?
•  » » » » 6 months ago, # ^ |   0 during the contest, when I kept on getting WA on test 6 (and eventually never got it)
•  » » » » » 6 months ago, # ^ |   +3 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.
•  » » » 6 months ago, # ^ | ← Rev. 3 →   0 A simpler one :1 1 2543 2if we take 5 and 4 we can't include (3 and 2).so optimal answer is 5*3+4*2
•  » » » 6 months ago, # ^ |   0 Could some one explain how come dp doesn't work without sorting the arrays?
•  » » 6 months ago, # ^ |   +2 I tried greedy too but failed miserably.
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 try this 2 1 43 232 2 2 2greedy will give (3*3)+(2*2).But,we get a better answer if we take (3*2)+(3*2)+(2*2)
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 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?
•  » » » 6 months ago, # ^ |   +3 tryed the same dude, now i know its wrong on 4 2 2 3 3 3 3 4 4 4 4Correct output : 48 We got : 32
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 My solution is giving the correct output 48. Still don't why it won't work. Here's my last submission 89977686
 » 6 months ago, # |   0 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.89951160In my submission, vectors are defined as sum -> lightning, sum2 -> fireball, v -> lightning, v2 -> fireball, st1 -> lightning, st2 -> fireball
 » 6 months ago, # |   +11 Really nice Problemset :-)
 » 6 months ago, # |   +6 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.
•  » » 6 months ago, # ^ | ← Rev. 2 →   +3 You can do it with just two sets. First set will contain k largest elements, and second set all other elements.
•  » » » 6 months ago, # ^ |   0 Can you please explain the approach.
•  » » » » 6 months ago, # ^ |   +3 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.
•  » » 6 months ago, # ^ |   +11 Treap can easily handle that.
•  » » » 6 months ago, # ^ |   +4 Thanks. I never used a Treap before
•  » » 6 months ago, # ^ |   0 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
•  » » » 6 months ago, # ^ |   0 My approach definitely wasn't the simplest
•  » » » » 6 months ago, # ^ |   0 I see, I asked why my one is wrong? I am getting WA on test 4 implementing segment tree using this idea
•  » » » » » 6 months ago, # ^ |   0 Sometimes it is optimal to cast lightning, fire, lightning, fire, etc.
•  » » » » » » 6 months ago, # ^ |   0 Got it now. Thanks.
•  » » » 6 months ago, # ^ |   0 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.
•  » » » » 6 months ago, # ^ |   0 Got it man. I was foolish enough to get it.
•  » » 6 months ago, # ^ |   0 https://codeforces.com/contest/1398/submission/89908543 tm william's solution is very neat.
•  » » 6 months ago, # ^ |   0 you can do that offline compressing all values and using segment tree.
•  » » 6 months ago, # ^ |   0 Policy based data structures can also work (but I ended up getting WA for some reason)
•  » » 6 months ago, # ^ |   0 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 functiondef add(val, left, right, vertex = 1): if (left == right) // Base Case count++ sum += val else: mid = (left + right) / 2 if (val <= mid): add(val, left, mid, vertex * 2) else: add(val, mid + 1, right, vertex * 2 + 1) st[vertex] = combine(st[vertex * 2], st[vertex * 2 + 1]) // Combine: add sums, add counts Now, 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 functiondef query(k, left, right, vertex = 1): if (k <= 0): // Trivial case return 0 elif (left == right) // Base case return left * min(k, st[vertex].count) else: mid = (left + right) / 2 if (st[vertex * 2 + 1].count >= k) // Does the right part fulfill all needs? return query(k, mid + 1, right, vertex * 2 + 1) else: return query(k - st[vertex * 2 + 1].count, left, mid, vertex * 2) + st[vertex * 2 + 1].sum The code provided is psuedocode.
 » 6 months ago, # |   +22
•  » » 6 months ago, # ^ |   0 Agreed.
 » 6 months ago, # | ← Rev. 2 →   -6 Ciao Rating !
 » 6 months ago, # |   0 This game really pisses me off
 » 6 months ago, # |   +7 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?
•  » » 6 months ago, # ^ |   0 code without sorting 89945848 give wrong ans. code with sorting 89955750 gives right ans.
•  » » 6 months ago, # ^ |   0 Because you need to find the maximum area this could only be achieved when you consider longest pairs first.
 » 6 months ago, # |   +2 Too sad, I can't implement E in time (in 30 mins) :((. How can I improve my coding speed
 » 6 months ago, # |   +3 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)
 » 6 months ago, # |   +1 It seems testcases are weak on problem E, this slow solution passes. Go ahead and hack it! 89956850
 » 6 months ago, # |   +27 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?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +15 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)).$ The solution was simple but I was not able to prove that time complexity is $O(N(log(N))$ but the the basic proof is that lets in one iteration you are going from $pos$ to $idx1$ where $idx1$ can be $pos+1$ but in the next iteration you will definitely jump from $idx1$ to $idx2$ such that $idx2 >= pos + len$ thus at max total $2 * (N/len)$ iterations will be there for a single $len$.
•  » » » 6 months ago, # ^ |   0 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.
•  » » » » 6 months ago, # ^ |   +3 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$
•  » » 6 months ago, # ^ |   0 Can you elaborate more on this?
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +8 Short proof: \begin{align} & \sum\limits_{i=l}^r a_i = r - l + 1 \\ \implies & \left( \sum\limits_{i=l}^r a_i \right) - (r - l + 1) = 0 \\ \implies & \left( \sum\limits_{i=l}^r a_i \right) - \left( \sum\limits_{i=l}^r 1 \right) = 0 \\ \implies & \sum\limits_{i=l}^r (a_i - 1) = 0 \end{align}
•  » » » » 6 months ago, # ^ |   0 Thanks for this proof
•  » » » » 6 months ago, # ^ |   0 I understood this proof but why we use frequency to calculate the total answer ?
•  » » » » » 6 months ago, # ^ |   0 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$.
•  » » » » » » 6 months ago, # ^ |   0 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 ?
•  » » » » » » » 6 months ago, # ^ |   0 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 :)
•  » » » » » » » » 6 months ago, # ^ |   0 Thanks very much
•  » » 6 months ago, # ^ |   +8 think of the brute force solution then optimize it, you can find the answer for any x in O(n) like this pseudocodedef f(x): i = 0 ret = 0 while i+x <= n: any_ones = #is there any ones between [i, i + x - 1] any_zeros= #is there any zeros between [i, i + x - 1] if any_ones and any_zeros: #can't win the round between i and i + x -1 i += 1 else: #can win the round ret += 1 i += x return ret this 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
 » 6 months ago, # |   +59 could E BE more boring ?
•  » » 6 months ago, # ^ |   0 Well，I think problem E is fine because I consolidated the segment tree from it._(:з」∠)_
 » 6 months ago, # |   0 i see the answer for "C. Good Subarrays" in this content but i still can't understand it can any one help me?
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 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?ideal array with all subarrays with their sum = size of that subarray is 1 1 1 1 ... 1 (up till n) if you subtract 1 from all now you have 0 0 0 0 ... 0 (you can see the change it made right?) now you need to find all the subarray with sum = 0. https://stackoverflow.com/questions/26532723/counting-all-contiguous-sub-arrays-given-sum-zerohere is how to deal with this problem from this perspective
•  » » 6 months ago, # ^ |   +3 $sum_r-sum_l=r-l \implies sum_r-r=sum_l-l$
 » 6 months ago, # |   0 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
 » 6 months ago, # | ← Rev. 2 →   0 W
•  » » 6 months ago, # ^ |   +7 Done
 » 6 months ago, # |   0 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
•  » » 6 months ago, # ^ | ← Rev. 3 →   +5 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.
•  » » 6 months ago, # ^ | ← Rev. 2 →   +3 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.
 » 6 months ago, # |   0 Please provide a test case where Greedy approach in problem D fails
•  » » 6 months ago, # ^ | ← Rev. 2 →   +1 4 2 2 10 10 10 10 11 11 11 11 
•  » » 6 months ago, # ^ | ← Rev. 2 →   +1 Consider this test case: 2 2 25 54 43 3
 » 6 months ago, # |   0 How to solve $G$ without bitsets? Faster than $O(X^2/32)$
•  » » 6 months ago, # ^ |   +13 fft
•  » » » 6 months ago, # ^ |   0 Nice! Karatsuba also works.
•  » » » » 6 months ago, # ^ |   0 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 ?
•  » » » » » 6 months ago, # ^ |   0 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$.
•  » » 6 months ago, # ^ |   0 How to solve G with bitset?
 » 6 months ago, # |   +3 Problem C becomes so beautiful after realizing its logic.
•  » » 6 months ago, # ^ |   +36 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$.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   -10 [deleted]
 » 6 months ago, # |   0 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.
•  » » 6 months ago, # ^ |   +2 You didn't initialize variable out 89961488
•  » » » 6 months ago, # ^ |   0 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 out and because I used an integer for indexing it works for some reason XD
 » 6 months ago, # |   -18 O(n) solution of C with HashMap 89943214
 » 6 months ago, # |   0 why the greedy solution of D — "pick two largest pair every time" fails?
•  » » 6 months ago, # ^ |   0 Counterexample:R: 3 4 5G: 5 6B: 7If you take 2 biggest elements of different colours you'll end up with: 7 * 6 + 5 * 5 = 67Though the optimal split is: 7 * 5 + 6 * 4 + 5 * 3 = 35 + 24 + 15 = 74
•  » » 6 months ago, # ^ |   +3 9 9 10 10 -> That greedy pairs the both 10 instead of 9,10 + 9,10.
•  » » » 6 months ago, # ^ |   +1 spooky mah boi , why you oscillate between colors so much ?
•  » » » » 6 months ago, # ^ |   +1 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.
•  » » » » » 6 months ago, # ^ |   0 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.
 » 6 months ago, # |   0 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 = 29
•  » » 6 months ago, # ^ |   0 Consider an array full of 1's. In your solution you ignore good subarrays of length more than 9, which is not correct
•  » » » 6 months ago, # ^ |   0 Shit my bad, thanks :)
 » 6 months ago, # |   0 in c i storedd arr[i]-1 for each array and counted the no of subarrays with sum 0 balancing excess with shortage!
 » 6 months ago, # | ← Rev. 3 →   0 why my code for D is giving TLE. It is using same approach as DP solution. code#include using namespace std; #define rng(x) x.begin(), x.end() #define pb push_back #define f first #define s second typedef long long ll; typedef pair pi; typedef pair pl; typedef vector vi; typedef vector vl; typedef vector vvi; typedef vector vvl; typedef vector vb; /*-----------------------------Code begins----------------------------------*/ ll rgb(vl r, vl g, vl b){ int z1=r.size(),z2=g.size(),z3=b.size(); int cnt=0; if(z1==0){cnt++;} if(z2==0){cnt++;} if(z3==0){cnt++;} if(cnt>=2){return 0ll;} if(cnt==1){ if(z1==0){ ll y=g[z2-1],z=b[z3-1]; g.pop_back(); b.pop_back(); ll gb=y*z; return gb+rgb(r,g,b); } if(z2==0){ ll x=r[z1-1],z=b[z3-1]; r.pop_back(); b.pop_back(); ll rb=x*z; return rb+rgb(r,g,b); } if(z3==0){ ll x=r[z1-1],y=g[z2-1]; r.pop_back(); g.pop_back(); ll rg=x*y; return rg+rgb(r,g,b); } } ll x=r[z1-1],y=g[z2-1],z=b[z3-1]; ll rg=x*y,gb=y*z,rb=x*z; ll lr=r[z1-1],lg=g[z2-1],lb=b[z3-1]; r.pop_back(); g.pop_back(); ll ans1=rg+rgb(r,g,b); r.push_back(lr); b.pop_back(); ll ans2=gb+rgb(r,g,b); r.pop_back(); g.push_back(lg); ll ans3=rb+rgb(r,g,b); return max(ans1,max(ans2,ans3)); } void solve(){ int nr,ng,nb; cin>>nr>>ng>>nb; vl r(nr),g(ng),b(nb); for(int i=0; i>r[i];} for(int i=0; i>g[i];} for(int i=0; i>b[i];} sort(rng(r)); sort(rng(b)); sort(rng(g)); ll ans=rgb(r,g,b); cout<>T; while(T--){ solve(); } return 0; } 
•  » » 6 months ago, # ^ |   0 Close enough, but learn dp, you'll see why it fails.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 i have tried to do DP problems but most of the times i fail to think of a DP solution
•  » » » » 6 months ago, # ^ |   0 You are passing whole copy of vector in the function. Just use an integer for index.
•  » » 6 months ago, # ^ |   0 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)
•  » » » 6 months ago, # ^ |   0 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)
 » 6 months ago, # |   +31 My screencast, if you want to enjoy my fingers suffering from typing so much (video solutions for A-E included)
 » 6 months ago, # | ← Rev. 2 →   0 Why are the hacks shown on the hacking page in reverse order, like the most recent hack is at the end?
 » 6 months ago, # |   +1 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
•  » » 6 months ago, # ^ |   0 Hope this helps https://codeforces.com/contest/1398/submission/89925922
•  » » » 6 months ago, # ^ |   0 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
 » 6 months ago, # |   -28 #include using namespace std; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); #define pb push_back #define fi first #define se second const int mod = 1e9 + 7; typedef vector vi; typedef pair ii; typedef vector vii; typedef long long ll; typedef vector vll; typedef double ld; const int N=210; int a, b, c; vll arr(N,0), brr(N,0), crr(N,0); ll dp[N][N][N]; ll func(int i,int j,int k) { if((i>=a and j>=b) || (i>=a and k>=c) || (j>=b and k>=c)) { return 0; } if(dp[i][j][k]!=-1) return dp[i][j][k]; return dp[i][j][k]=max(arr[i]*brr[j]+func(i+1,j+1,k), max(arr[i]*crr[k]+func(i+1,j,k+1), brr[j]*crr[k]+func(i,j+1,k+1))); } int main() { fastio #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif memset(dp,-1,sizeof(dp)); cin >> a >> b >> c; int len=max(a,max(b,c)); for (int i = 0; i < a; i++) cin >> arr[i]; for (int i = 0; i < b; i++) cin >> brr[i]; for (int i = 0; i < c; i++) cin >> crr[i]; sort(arr.begin(), arr.end(), greater()); sort(brr.begin(), brr.end(), greater()); sort(crr.begin(), crr.end(), greater()); cout<
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 Here is my code that passes everything: CODE#include using namespace std; typedef long long ll; ll r, g, b; vector ar, ag, ab; ll dp[205][205][205]; ll solve(ll i, ll j, ll k) { if (dp[i][j][k] >= 0) return dp[i][j][k]; return dp[i][j][k] = max({(i >= r || j >= g) ? 0 : ar[i] * ag[j] + solve(i + 1, j + 1, k), (j >= g || k >= b) ? 0 : ag[j] * ab[k] + solve(i, j + 1, k + 1), (i >= r || k >= b) ? 0 : ar[i] * ab[k] + solve(i + 1, j, k + 1)}); } int main() { cin >> r >> g >> b; memset(dp, -1, sizeof dp); ar.resize(r); ag.resize(g); ab.resize(b); for (ll i = 0; i < r; i++) cin >> ar[i]; for (ll i = 0; i < g; i++) cin >> ag[i]; for (ll i = 0; i < b; i++) cin >> ab[i]; sort(ar.begin(), ar.end(), greater()); sort(ag.begin(), ag.end(), greater()); sort(ab.begin(), ab.end(), greater()); cout << solve(0, 0, 0) << endl; } I 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.
•  » » » 6 months ago, # ^ |   0 Yaa I got Your point. Thanks!!:D
 » 6 months ago, # |   0 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 23 3 3 34 44 4This test case results in correct answer for my solution.
•  » » 6 months ago, # ^ | ← Rev. 3 →   +4 3 3 32 8 5 1 10 5 9 9 3 Correct answer : 10*9 + 8*9 + 5*5 + 2*3 = 193Your answer : 182
 » 6 months ago, # |   +5 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.89940459The 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 :)
 » 6 months ago, # |   0 Why we use frequency in problem C ?
 » 6 months ago, # |   0 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.
 » 6 months ago, # |   +16 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 #5Link to visual editorial here
 » 6 months ago, # |   0 how to check the time it takes for the submission when hacking?
 » 6 months ago, # | ← Rev. 2 →   -8 I love problem D very much!!
•  » » 6 months ago, # ^ |   +8 How to solve E?
•  » » » 6 months ago, # ^ |   +1 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.)
•  » » » » 6 months ago, # ^ |   0 Well, I am having tough time to understand this.
•  » » » 6 months ago, # ^ |   0 Maybe my expression is not clear, but you can find ideas from it. It must be feasible because I passed after the contest.
 » 6 months ago, # |   0 any news about the tutorial?
 » 6 months ago, # |   +8 why this code 89922404 for problem C won't get TLE
•  » » 6 months ago, # ^ |   0 The first three lines makes the code really fast.
 » 6 months ago, # |   0 Why are Educational Rounds always so late with editorials?
•  » » 6 months ago, # ^ |   0 Because of the 12 hour open hacking phase, I guess.
 » 6 months ago, # |   0 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?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +5 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).
•  » » » 6 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » 6 months ago, # ^ |   0 $dp_{i,j,k}$ stands for the state where we have already used first $i$ values of first array, first $j$ values of second array and first $k$ values of third array.The value of $dp_{i,j,k}$ is the maximum area we can obtain using remaining values of these three arrays in this situation.