By awoo, history, 5 weeks 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 Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Roman Roms Glazov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

• +201

 » 5 weeks ago, # |   -6 Thank you very much awoo for cool contest. We will wait for even more contests from you :)
 » 5 weeks ago, # | ← Rev. 3 →   -18 .
•  » » 5 weeks ago, # ^ |   -29 I think you can check it on the internet
•  » » 5 weeks ago, # ^ |   -14 I checked 99 euros is 8,648.06 rupees. I was glad to help you.
 » 5 weeks ago, # |   +75 Lighthearted Meme
•  » » 5 weeks ago, # ^ |   +16 Have you paid copyright to naman1601 for using that tag?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Hey, I understand that you want to make a point, but don't you think tagging is unnecessary? I believe noone likes to be tagged just to see their meme style being stolen by random people.
•  » » » » 5 weeks ago, # ^ |   +11 What harm did you get from this tag?
•  » » » » » 5 weeks ago, # ^ |   +10 wasn't he joking ? I believe he was just memeing.
 » 5 weeks ago, # |   -27 I wish if div 3's were more frequent...
•  » » 5 weeks ago, # ^ |   +31 when i started, i thought that i can't participate in Div2 because my rating is < 1600))) So i waited for Div3s)
•  » » » 5 weeks ago, # ^ |   0 xd
•  » » » 5 weeks ago, # ^ |   0 I have never participated in contests but it was my first time and I could not do well. when is Div 3 ?
•  » » » » 5 weeks ago, # ^ |   0
•  » » » » » 5 weeks ago, # ^ |   0 thans
•  » » » 5 weeks ago, # ^ |   0 How did you improve so much?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 solved problems and watched videos on Pavel Mavrins YouTube channel
 » 5 weeks ago, # |   +1 Good luck to everyone on this educational :D
•  » » 5 weeks ago, # ^ |   0 u too good luck :D
 » 5 weeks ago, # |   +24 Non-related meme
•  » » 4 weeks ago, # ^ |   +1 my problem b just failed for longlong in this way...
 » 5 weeks ago, # |   0 I hope I can add 50 points
•  » » 5 weeks ago, # ^ |   0 sure you can! if there are any problems, just use calculator!
 » 5 weeks ago, # |   0 LOL! I thought Codeforces Round #752 was going to happen before Educational Codeforces Round 116 [Rated for Div. 2]
 » 5 weeks ago, # |   +9 Glad to see no unusual time.
 » 5 weeks ago, # |   +14 Normal timings be like:
 » 5 weeks ago, # |   0 Notice the unusual time of the round
 » 5 weeks ago, # |   +3 Hey, I have few queries to ask about educational Rounds:1) I heard that all problems have equal points, Is it so?2) If every problem does have equal point, then, Is there any deduction of points after every minutes during contest? If yes, then does it vary for each problem?Thanks in advance.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +19 It is ICPC style contest. There are no points. Only number of solved problems matters. And there is a penalty which breaks a tie between people with the same number of solved problems.Penalty is calculated like this. If you solve any problem, then the minute on which you solved it will be added to the penalty. For example if you solve problem after 1 hour and 23 minutes after the start, then 83(60+23) will be added to the penalty. Also if you had unsuccessful attempts on this problem previously, then each attempt will add 10 penalty points.
 » 5 weeks ago, # |   -8 there are queue in codeforces it will be solved before the contest ??
 » 5 weeks ago, # |   -13 I will AK Edu 116
 » 5 weeks ago, # |   0 A is way more difficult than B
•  » » 5 weeks ago, # ^ |   0 mood
 » 5 weeks ago, # |   0 How to solve E ??
•  » » 5 weeks ago, # ^ |   0 for dp[n][x], iterate over i = 0 ~ n but i != n — 1, which means i people died in the first round
•  » » » 5 weeks ago, # ^ |   0 The condition to have no winner is to have at least two same max numbers and then the rest of the numbers can be anything less than that. Am I correct?
•  » » » » 5 weeks ago, # ^ |   +4 Countercase: [1, 1, 2]There is only one maximum, but all heroes receive 2 damage in the first round and die, so there's no winner.
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 Thank you for replying! Is this like an edge case? If no, then what was the intended solution?
•  » » » » » » 5 weeks ago, # ^ |   +14 It's not an edge case, there's no way to eliminate these cases easily.We will post an official editorial in 24 hours after the contest.Shortly, the main idea is dynamic programming of the form $dp_{i,j}$ — suppose, after some round, all heroes received $i$ damage, and exactly $j$ of them died, what is the number of ways to make it happen?
•  » » » » » » » 4 weeks ago, # ^ |   +8 sorry but why wait 24 hours for editorial, when hacking ends in 12 hours? its almost as if educational rounds are notorious for slow editorials
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 So maybe just handle such cases alone? My approach was adding all possible combinations with max value <= $min(n-1, k)$.Then for all $i$ bigger then or equal $k$, do what faraz said, at least two same max numbers and then the rest of the numbers can be anything less than that.I didn't implement in time though and unsure if even close to correct.
•  » » » » » » 5 weeks ago, # ^ |   +3 This solution doesn’t cover all cases, and there is no easy way for that. And that’s why you have to do dp
 » 5 weeks ago, # |   +13 Does problem D have an actual clean solution other than sorting the rows and prefix/suffix max/min on four sides?
•  » » 5 weeks ago, # ^ |   0 I did the same thing. 3961ms AC...
•  » » » 5 weeks ago, # ^ |   0 Me too, but only 810 ms. record
•  » » 5 weeks ago, # ^ |   0 Would really like to see the editorial for D
 » 5 weeks ago, # |   -9 :D In C Problem, complier 64bit wrong :D and 32bit AC :D - :D
•  » » 5 weeks ago, # ^ |   +6 Most likely the pow function here is the culprit. Even if both of its arguments are integers, it still works with non-integer types, so it sometimes causes precision issues.
•  » » » 5 weeks ago, # ^ |   +1 tks, I think I need to use my pow function for the next contest.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   -10 Took me 40 minutes to figure that out :')
•  » » » 5 weeks ago, # ^ |   -10 But i used the binary exponential as power still the error is there
•  » » 5 weeks ago, # ^ |   0 Can u please explain how u solved C problem?
•  » » » 5 weeks ago, # ^ |   +3 you can use n = 10^(a[i + 1] — a[i]) — 1 notes for each note. For the largest one, no maximum. Iterate each note from small to large. if k is more than or equal to n then use all the notes, minus n from k and move to next note. if you have k less than n, then use (k + 1) notes and done.
•  » » » » 5 weeks ago, # ^ |   0 Thanks a lot
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 sr, my English is not good. You can following test example: F(59) = 14 / 9s = 59 = 9 * 1 + 5 * 10s = a * 1 + b*10 + c*100 + … + z* 10^9follow k and array A ascending.=> x = 10^(a[i+1] — a[I]) — 1k = k + 1;If (x >= k) => ans += 10^(a[I]) * k => update k = 0 => end program;elseif (x < k) => ans += 10^(a[I]) * x and update k = k — x; and loop when end array or (x >= k)but k maybe not = 0, u need to update ans += k * 10 ^ (a[n-1]) (with a[n-1] = maxArr)
•  » » » » 5 weeks ago, # ^ |   0 Thanks a lot
 » 5 weeks ago, # |   +5 :| How to solve Problem D? :( I can't think of solutions for it.
•  » » 5 weeks ago, # ^ |   0 Hint 1 ... Find the prefix max, prefix min, suffix max, suffix min along each row.
•  » » » 5 weeks ago, # ^ |   -8 Tks, I trying to solve it :D
•  » » 5 weeks ago, # ^ |   +1 If you sort the rows by the first element in increasing order, it turns out that blue rows is a prefix of the matrix.
 » 5 weeks ago, # |   0 I read D wrongly as every red cell in the left matrix contains an integer greater than every red cell in the left matrix; every blue cell in the right matrix contains an integer greater than every blue cell in the right matrix.
•  » » 5 weeks ago, # ^ |   0 Me too, initially. But after looking at the figure, I corrected my understanding.
 » 5 weeks ago, # |   -8 I want to ask all of you, honestly, pls tell me which problem was good for you and why? For me, it was so nonalgorithmic problems :(
•  » » 5 weeks ago, # ^ |   0 All are quite good problems. If you talk about algorithmic, D — F of course are.
 » 5 weeks ago, # |   0 Hi Folks, need help, how can we approach problem A? I tried few ways but my approach is wrong.
•  » » 5 weeks ago, # ^ |   0 first and last symbols must be the same of the string to achieve AB's = BA's
•  » » » 5 weeks ago, # ^ |   0 @ADO thanks valid point, let me think about it and try it out.
•  » » » 5 weeks ago, # ^ |   0 Yes. I spent 19 minutes to realize this simple result...
•  » » » » 5 weeks ago, # ^ |   0 Me too got confused and after 5-6 WA i realized the simple solution :(.
 » 5 weeks ago, # |   0 Why Math.ceil() in java is giving wa on testcase 6 Wa But calculating ceil manually gives ac AC
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 coz I think Math.ceil() will give some precision error while manual ceil gives correct answer. See below: ~~~~~ Input: 1000000000000000000 2 Checker Log wrong answer 2nd numbers differ - expected: '500000000000000000', found: '500000000000000002' ~~~~~. Using Math.ceil(), we will get above error . !!
 » 5 weeks ago, # |   +11 Well that was embarrassing
 » 5 weeks ago, # |   +4 How to solve E?
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +59 Think about how to kill a fighter. His health should be lower than n. So, no winner means all fighters have health less than number of fighters at some time. Pick k players and assign them any health lower than n. C(n, k) * POW(n — 1, k) choices. For the other n — k fighters, health of each of them is decreased by n — 1. So, here is a sub problem: the number of choices when we have n — k fighters with maximum x — n + 1 health point. dp(n, x) = sigma(k = 0 to n, k!=n-1, C(n, k) * POW(n — 1, k) * dp(n — k, x — n + 1))
•  » » » 5 weeks ago, # ^ |   0 Thanks
 » 5 weeks ago, # | ← Rev. 4 →   +3 where is the editorial?
•  » » 5 weeks ago, # ^ |   0 Obviously not during hacking stage, huh?
 » 5 weeks ago, # |   +1 Damn , I solve problem after contest ended by menuties
 » 5 weeks ago, # | ← Rev. 3 →   0 Today I got a lot of WA on third as I was using gnu c++ 64 bit Spoiler4th numbers differ — expected: '999999920999999999', found: '999999921000000000'but after contest friend suggested me to use gnu c++ 17 Spoilerok 4 number(s): "59 778 148999 999999920999999999anyone know why this happen?
•  » » 5 weeks ago, # ^ |   0
 » 5 weeks ago, # | ← Rev. 2 →   +14 No idea how but I just ACed F using $O(n^{\frac{5}{3}})$, actually its $O(nk^2+\frac{n^2}{k})$ with $k=150$. Posting this here hoping someone can hack it somehow. 133531014
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +33 I don't know whether or not it's hackable, but you can very easily improve the $O(nk^2)$ DP part of your solution to $O(nk)$ by simply not visiting useless DP states. Specifically, notice that you can't remove more nodes than you've currently processed, so if you've processed the first $m$ children of some node, and you're about to process ($m+1$)-th, then you have $\min(\sum_{i=1}^m sz_{ch_i},k)$ useful DP states. Proof for how this then becomes $O(nk)$ is here.With this, setting $k=\sqrt{n}$, the complexity becomes $O(n\sqrt{n})$, which comfortably passes in 1s, my code: 133546415
 » 5 weeks ago, # |   0 how to solve c?
•  » » 5 weeks ago, # ^ |   0 First One is Not Accepted During Contest :- WASecond One Accepted After Contest :- AC:( You can feel the pain after looking my code and why it gets rejected while in contest
 » 5 weeks ago, # |   0 When will the system hacking start?
 » 5 weeks ago, # |   +1 So many hacks on problem B. Can anyone give me the edge case?
•  » » 5 weeks ago, # ^ |   +15 Hack Meme :(
•  » » » 4 weeks ago, # ^ |   0 That's not the thing bro ! Any way your solution is going to fail the system testing :( My submission on B is not hacked but fails sys test. Rank drops to 4700+ :(
•  » » » » 4 weeks ago, # ^ |   0 Test cases are added when someone hacks solution of other participant
•  » » » » » 4 weeks ago, # ^ |   0 yeah!!
 » 5 weeks ago, # |   0 can someone tell me whats wrong in my code? https://codeforces.com/contest/1606/submission/133515590
•  » » 5 weeks ago, # ^ |   0 Because 10000 iterations isn’t enough. Answer can be very large and you can’t loop.
•  » » » 5 weeks ago, # ^ |   0 thanks but i thought it grow fast like fibancci sequence so i thought 54 is enough can you explain why this conclousion wrong
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 After copied computers reaches k, each round could only add k more computers.
•  » » » » » 5 weeks ago, # ^ |   0 but i handled that by making a formula to simulate adding k computers every time till reaching n or larger this is the lines /* if (comp >= x) { // cout< comp) { unsigned long long k = ceil(((n - comp * 1.0) / x)) + i - 1; cout<
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 For example n=10^18 and k=1. You can copy to 1 computer at a time
•  » » » » » 5 weeks ago, # ^ |   0 ok now i understand so the answer for this case shoulde be n — 1 i will try it thanks alot
•  » » » » » » 4 weeks ago, # ^ |   0 Yes
 » 5 weeks ago, # | ← Rev. 2 →   0 I have a very simple solution for problem A, can someone tell me if its somehow not good??? https://codeforces.com/contest/1606/submission/133508578
•  » » 5 weeks ago, # ^ |   0 impressive, thats a clean and simple code thanks very much
 » 5 weeks ago, # |   +5 How to solve F? I assume quadratic DP is trivial? Can it be improved or something?
 » 5 weeks ago, # |   +1 It is really an educational contest thanks for writers
 » 5 weeks ago, # |   0 can someone help me with my code https://codeforces.com/contest/1606/submission/133548731. It is giving wrong answer and I don't know why.
•  » » 5 weeks ago, # ^ |   +5 Overflow. Change dp[i+go][k]+=dp[i][j]*(power(go,j-k,mod)*ncr(j,k,mod))%mod; to: dp[i+go][k]+=(dp[i][j]*((power(go,j-k,mod)*ncr(j,k,mod))%mod))%mod;This will solve the WA, but you will get TLE.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 thanks a lot. i think the tle can be fixed by precomputing some stuff.
 » 5 weeks ago, # |   0 How to solve problem E? I'm stuck.
•  » » 5 weeks ago, # ^ |   0 See my comments above.
 » 5 weeks ago, # |   0 It's been more than 8 contests and haven't improved yet, feeling very low and disappointed not able to solve even a single question in this round. Also doing upsolving but not improving any suggestions please
•  » » 5 weeks ago, # ^ |   0 Create a mashup of 4 A(1000 level) problems + 4 B problems(1200 level) and solve them in the virtual contest.
•  » » 5 weeks ago, # ^ |   0 Don't down yourself anytime it evens makes you perform bad in contests.Try practicing questions from a rating range greater than your currrent rating. believe in yourself and one thing nothing can be created in one step Try hard for it and keep all your efforts . I hope you will be fine
 » 5 weeks ago, # |   0 Can someone please explain their approach for Problem D?
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   +6 let mnl[i][j] be min(a[i][k] for 1<=k<=j), mxl[i][j] be max(a[i][k] for 1<=k<=j), mnr be min(a[i][j] for j<=k<=m) and mxr be max(a[i][j] for j<=k<=m). Iterate from column number 1 to column number m-1. Let the current column number be j, let array t contains all the row indices i in ascending order of mxl[i][j]. Now, if we can cut the column into two pieces at column j (j being in the left part), there must be some prefix of t such that max(mxl[k][j] for k belongs to prefix of t)max(mxr[k][j+1] for k belongs to suffix of t). Here, all the indices in prefix are coloured blue and the rest are coloured red.Here is my code. (Ignore the segment tree templates. I initially thought of implementing using segment trees but, later used multisets).
 » 5 weeks ago, # |   0 will this contest be rated for me because when I am seeing my graph after the contest it is showing that this was an unrated contest
 » 5 weeks ago, # |   0 Can anyone tell me what's wrong with my solution? 133471460 For example on this test case : 576460752303423488 288230376151711743Jury's answer is 60 but according to me it should be 59. As, first 59 powers of 2 will give the sum of n-1 and 2 ^ 58 < k here.
•  » » 5 weeks ago, # ^ |   0 Even I got it wrong. The issue is with log2. Instead divide by 2 repeatedly.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Same :(Any way learnt a thing about log2() function that's good for me:)
•  » » » 4 weeks ago, # ^ |   0 Oh, thanks! Never using log2 again :(
 » 5 weeks ago, # |   0 133567594 Can anyone please explain testcase 41 in this problem??
 » 5 weeks ago, # |   +4 How to solve F using segment tree or treap?
 » 5 weeks ago, # |   -11 Hi , i was checking my final standing and i saw i just got wrong answer after the contest and even hack session was over while before that i have got accepted in problem B. So i don't know if they changed the test cases or what but i think it's not fair to change the test cases when the contest is over and changing the test cases should just be allowed while the contest is running.(and i didn't get hacked , i just suddenly got wrong answer on test 30 in problem B).
•  » » 4 weeks ago, # ^ |   0 This a rule in contest which have hacking phase in them. They collect all hack cases and insert them as new tests.
•  » » » 4 weeks ago, # ^ |   +5 oh i didn't know that thanks for responding.
 » 4 weeks ago, # |   0 I am new can anyone share where I can find editorial of this contest.Thankyou
•  » » 4 weeks ago, # ^ |   0 Educational rounds have a 24 hour hackig phase after the coding phase ends and editorial is only published after the end of hacking phase.
•  » » » 4 weeks ago, # ^ |   0 I think hacking phase is of 12 hour.
 » 4 weeks ago, # |   0 In B, I got the value of pow(2,log2(k)) greater than k itself. How is this possible? It was for the testcase: 576460752303423487 576460752303423487
•  » » 4 weeks ago, # ^ |   0 This is a problem with log2() . see this : https://codeforces.com/blog/entry/56975
 » 4 weeks ago, # |   +4 When will the editorials and the ratings get updated?
 » 4 weeks ago, # |   0 Hello Community can somebody confirm that whether rounds #751 and Educational Round 116 were rated or unrated?
 » 4 weeks ago, # |   +23 This is my hack case which kills more than 100 submissions.The issue is numerical error of log or pow in 1e18.see also the editorial of this problem : ABC215-B 13 576460752303423486 576460752303423486 576460752303423487 576460752303423487 576460752303423488 576460752303423488 576460752303423489 576460752303423489 576460752303423490 576460752303423490 576460752303423488 288230376151711743 576460752303423488 288230376151711744 576460752303423488 288230376151711745 576460752303423486 576460752303423485 576460752303423487 576460752303423486 576460752303423488 576460752303423487 576460752303423489 576460752303423488 576460752303423490 576460752303423489  correct output59 59 59 60 60 60 59 59 59 59 59 60 60 
•  » » 4 weeks ago, # ^ |   0 That took me down, welp :(
 » 4 weeks ago, # |   -15 Hi, awoo, and other round coordinatrs. Please check this issue that my solution for problem C is skipped, reason stated that it was coincided with others solution. The solution to the problem is quite intuitive, may be, that's the reason. Please check it. Not this time again.
•  » » 4 weeks ago, # ^ |   +12 can you tell us the number of submission that coindieded with yours??if you can't, you are just another cheater from India -the country of cheaters-.
•  » » 4 weeks ago, # ^ |   +12 The solution to the problem is quite intuitive, maybe, that's the reason, Yes it is so intuitive that you changed your template and coding style on C.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   -7 try to take a quick scan on my previous 3 submission of problem C. I shouldn't reply to you but still.
•  » » » » 4 weeks ago, # ^ |   -11 why does most of the Indians doesn't know any shame?do they think that people from other countries are dumb as them to believe their lies?
 » 4 weeks ago, # |   0 Can someone help me explaining why this solution for E problem is not correct?In my solution winner must have >= n health to win(others n — 1 heroes can have < winner health)Then I subtract from all possibilities win possibilitieshttps://codeforces.com/contest/1606/submission/133586943
•  » » 4 weeks ago, # ^ |   0 I did the same thing but it wasn't working for the fourth sample case. If someone can point out the error in the approach, it would be really helpful.
 » 4 weeks ago, # |   +3 MikeMirzayanov In the Educational round that was conducted yesterday, I have been wrongly flagged for plagiarism. The solution for question C was fairly straightforward in terms of logic and coincidence should have been expected by the problem setters. I assure you I have not indulged in unfair practices. I participated after a fairly long time and was really happy that I performed well. Please return my rating delta. Thanks in advance.
•  » » 4 weeks ago, # ^ |   0 awoo please look into this
•  » » » 4 weeks ago, # ^ |   0 MikeMirzayanov I am once again requesting you to return my rating changes.
 » 4 weeks ago, # |   +22 Was waiting for an educational round for a long time.... Finally had a great contest today and was ranked 858(my first ever under 1000 rank :-) and got a rating boost of +105 :-)
 » 4 weeks ago, # | ← Rev. 2 →   0 When will be the editorial out for this contest? I didn't even get the solution for problem A that why would the answer be s[0] = s[s.size() - 1]` which got accepted.
 » 4 weeks ago, # |   0
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 3 weeks ago, # | ← Rev. 2 →   +12 I haven't been seeing them publishing top 5 winners and top 5 hackers and 1st one to solve the each problem for a while..