By awoo, history, 10 days 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 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 Geothermal 6 183
2 qpEDop_MuXauJloBu4 6 216
3 hanbyeol_ 6 219
4 tute7627 6 221
5 fastmath 6 287

69 nice successful hacks and 304 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Geothermal 0:00
B Geothermal 0:04
C Geothermal 0:07
D jayeshaw 0:18
E tzc_wk 0:28
F jiangly 0:30

UPD: Editorial is out

• +266

 » 10 days ago, # | ← Rev. 5 →   0 Hoping for a great contest!
•  » » 9 days ago, # ^ | ← Rev. 3 →   +29 Weak pretest of F even do not have cases of disconnected :(
•  » » » 9 days ago, # ^ |   -25 So this is the reason why it was a "good contest" lol
•  » » » 9 days ago, # ^ | ← Rev. 2 →   +10 There were disconnected graphs but no ones with a lot of edges. I personally think it was decent enough for pretests.To be honest, from your solution I'd say it should've been pretty fair for you to assume that it passes only if the tests are weak. Maybe I don't know the estimates on the number or the sparsity of hamiltonian paths in connected graphs, but you do. In that case I'd love to hear why that solution can be fast enough.
•  » » » » 8 days ago, # ^ |   +29 It is such interesting. I also don't know why my code can run so fast :D .But it seems to be slow when it doesn't exist a solution (disconnected or do not have a vaild path).I judged them before my programm and can AC now.
•  » » » » » 8 days ago, # ^ | ← Rev. 3 →   +21 There is a lower bound on the minimum possible non-zero number of hamiltonian paths for some fixed n and m. It seems to be somewhere around $10^5$ for 12 45-48. I guess you are abusing this fact implicitly.Maybe you'll be able to pass any test within given constraints with more optimizations. Feel free to tinker with my generator to make your solution (or my tests :P) stronger. It finds connected graphs with the smallest number of hamiltonian paths, spitting out every improvement (or same answer but not too often) into folder "tests". I run it with "./gen n m k 1e5 0.999", these temperature and cool down rate seem to get you nice graphs fast enough.
 » 10 days ago, # |   +4 Thank you all the people who have put in time and efforts in making this contest for us. Upvoted!
 » 10 days ago, # |   0 What are the score distributions for individual problems?? Looking forward to a great contest!!
•  » » 10 days ago, # ^ |   +13 bruh its icpc style, every problem carries the same score.
•  » » » 10 days ago, # ^ |   +5 OK DWIGHT!! THANNKS FOR REMINDING :)
•  » » » » 10 days ago, # ^ | ← Rev. 2 →   +49
 » 10 days ago, # |   -16 Looking forward to losing my newbie virginity to this contest !
•  » » 10 days ago, # ^ |   +3 Never thought u to be a saint, I believe that u r a slut , haha
•  » » » 10 days ago, # ^ |   -17 u are not my office co-worker. of course u know i am a slut
 » 10 days ago, # |   +24 Is it just me or half of the trickiest problems am not able to solve during practice are always authored by BledDest.?:)Looking forward to it!
•  » » 10 days ago, # ^ |   0 Same here bro!T_T
 » 10 days ago, # |   +11 Ok, new contest, new story, just gotta give virtual rounds of all contests by this author and that's enough practice. Wait...
 » 10 days ago, # |   0 This will definitely be another brilliant contest!
 » 10 days ago, # |   0 Really looking forward to this round. To improve my rating. It sucks.
 » 10 days ago, # |   +65 Our friends at Harbour.Space don't have any messages for us this time?
 » 10 days ago, # |   0 Another brilliant round, i hope this round improve my rating. Upvote for your kind wishes.
 » 10 days ago, # |   -14 Always like Educational Rounds :D
•  » » 9 days ago, # ^ |   0 In fact,Educational Rounds is good for our rating :)
 » 10 days ago, # | ← Rev. 2 →   +3 To be educated in educational round..
•  » » 10 days ago, # ^ |   +58 Tbh, Atcoder ABC's are more educational nowadays.
•  » » » 10 days ago, # ^ |   -13 bro you said Atcoder two times. ABC = Atcoder Beginner Contest. Atcoder ABC = Atcoder Atcoder Beginner Contest.
•  » » » » 9 days ago, # ^ |   -10 He meant problems A, B, C
•  » » » » 9 days ago, # ^ |   +4 Wow so knowledge, much smart.
•  » » 9 days ago, # ^ |   -7 In my experience with educational rounds, the only 'educational thing' with them is that they are not educational :/
•  » » » 8 days ago, # ^ |   0 They are educational because they teach you a lesson.
 » 10 days ago, # |   +15 Nowadays participating in ABC contests is helpful for CF edu rounds lol
 » 10 days ago, # |   -27 After a long time, an educational round is going to be held. I hope the problem set will be interesting and contest will enjoy the round.
 » 9 days ago, # |   +1 shinzou WO Sasageyo...!!
•  » » 9 days ago, # ^ |   0 What is freedom?
•  » » » 9 days ago, # ^ |   0 What is love?
•  » » » » 9 days ago, # ^ |   0 Mikasa.... :)
•  » » » 9 days ago, # ^ |   -25 Freedom is an action governed by nothing but your own free will. Eren Yeager (aka) Hitler2, tatakae yeager, Ereh, Hitler kin, Angry German kid, True Sigma, Suicidal Bastard.
•  » » » » 8 days ago, # ^ |   0 I'm not a fan of Eren but calling him Hilter2 is too far-fetched
•  » » 9 days ago, # ^ |   +1 what is the lie, what is the truth, what to believe
•  » » » 9 days ago, # ^ |   0 The truth is whatever lie you choose to believe...And the truth is that neither of us were able to solve problem C... I choose to believe that if I had some extra time... maybe I could have solved it...PS: This is what I chose to believe, It's not the truth.. the truth is I couldn't have been able to solve it even if I would have dedicated my complete day on it... but I chose to believe that I could have provided that I just had 1 more hour for it.
•  » » » » 9 days ago, # ^ |   0 factorial and mod disasterrrrrr
•  » » » » » 9 days ago, # ^ |   0 They are the true enemy of mankind... They must be annihilated as soon as possible so that the human race may be able to continue for eternity.
 » 9 days ago, # |   +2 This doesn't seem Educational at all. :( Not at all for Div-2 also
•  » » 9 days ago, # ^ |   0 Totally agreed...( ﾉ ﾟｰﾟ)ﾉ＼(ﾟｰﾟ＼)
 » 9 days ago, # | ← Rev. 2 →   0 Div-2 C : bool unsolved = true; while(unsolved) { crying due to mod&factorial = true; if(crying due to mod&factorial) unsolved = true; } 
•  » » 9 days ago, # ^ |   0 I too am crying due to the 3rd question... :_)1st problem : combinatorics2nd problem : modulo
•  » » » 9 days ago, # ^ |   +6 Meanwhile me :WA on test 4 ll sub(ll a, ll b){ return (a-b) % mod; } AC ll sub(ll a, ll b){ return (a-b+mod) % mod; } 
•  » » » » 9 days ago, # ^ |   +1 I am really tired ... was unable to solve problem C even after struggling for 1.5 hrs straight.
•  » » » 9 days ago, # ^ |   0 Me after this contest:Change my organization to "Fool of Combinatorics and Number Theory"
•  » » » » 9 days ago, # ^ |   +1 Count me in bro... :_)
•  » » 9 days ago, # ^ |   0 bro, i 've cried over 1hr :((
•  » » 9 days ago, # ^ |   0 what's it？
 » 9 days ago, # |   0 back to newbie
 » 9 days ago, # |   -8 the first testcase in C makes the solution obvious
•  » » 9 days ago, # ^ |   0 But you also need to be careful with other special situation!
 » 9 days ago, # |   +1 How to solve C?
•  » » 9 days ago, # ^ |   +1 SpoilerLet maxi be the index of the maximum element in a, then one of the following conditions must hold for a permutation to be bad. for every i < maxi, a[i]<=a[maxi]-1 for every j > maxi, a[i]<=a[maxi]-2
•  » » » 9 days ago, # ^ |   0 Thanks a lot!
•  » » » 9 days ago, # ^ |   +2 This logic is easy to come up with...I feel the tough part was to calculate bad permutations using combinatorics
•  » » » » 9 days ago, # ^ |   0 Exactly
•  » » » » 9 days ago, # ^ |   0 the tough part is to not mess up the calculation and mod correctly
•  » » 9 days ago, # ^ |   0 the only wrong case might occur iff all the second maximum numbers are behind the maximum number, if there are two maximum numbers then answers is fact[n]. To calculate we can note that the first thing is equal to the non integral solutions to a number. Also the numbers themselves are different so you multiply the factorial of the second maximum also. Rest numbers can be permutated also so we need to calculate the number of permutations with common objects and multiply that also.
•  » » 9 days ago, # ^ | ← Rev. 3 →   +2 The answer will only depend on the largest number, second largest number, and their respective frequencies. I'll denote largest number as $max$ and second largest number as $secmax$. If the count of $max$ is greater than $1$, then the answer will $factorial(n)$ (all possible permutations), because all permutations will be nice in this case. If the difference between $max$ and $secmax$ is greater than $1$, then the answer will be $0$ (since no permutation can be nice in this case).Now the only case remaining is when $max=secmax+1$ and count of $max$ equals $1$. Here, a permutation will not be nice only if $max$ is behind all the $secmax$ in the permutation. So the number of not nice permutations will be $nCr(n,(countmax+countsecmax))*factorial(n-countmax-countsecmax)*factorial(countsecmax)$. The final answer will be $factorial(n)$ — ($no.$ $of$ $not$ $nice$ $permutations$), which we calculated above.
•  » » » 9 days ago, # ^ |   +3 Could you explain the formula for the number of the "not nice"-permutations?
•  » » » » 9 days ago, # ^ | ← Rev. 2 →   +1 I just realized that I complicated the formula a bit. Basically, think of the permutation consisting of $n$ empty spaces. First we need to fill the empty spaces with all the numbers which are smaller than $max$ and $secmax$. There are $nCr(n,(countmax+countsecmax))$ ways to fill the permutation with the smaller numbers and $factorial(n-countmax-countsecmax)$ ways for the smaller numbers to permute. Now we only have to worry about the no. of permutations of all $max$ and $secmax$ in the rest of empty spaces. Since there is only 1 $max$ and it will be placed in the last of the remaining spaces, we only have to find the number of ways to arrange all $secmax$, which is $factorial(countsecmax)$.
•  » » » » » 9 days ago, # ^ |   0 Great explanation. Thanks!
•  » » » 9 days ago, # ^ | ← Rev. 3 →   0 Thanks alot for explanation.I am not able to understand that we have secmax whose count is "countsecmax" ,they all are same value wise, then why are we multiplying factorial(countsecmax) in invalid case.Lets say we have 333 , so to arrange them we only have 1 way right?
•  » » » » 9 days ago, # ^ |   0 The permutation they have asked for is for the indexes (1 to n) and not the values of the permutation themselves.
•  » » » » » 9 days ago, # ^ |   0 ohh , i got it thanks alot!
 » 9 days ago, # |   +2 Problems were hard.
 » 9 days ago, # |   +8 How to solve D
•  » » 9 days ago, # ^ |   +15 I missed the registration, but my guess is Spoilerprefix sums a pair is convenient only if one point lies on vertical and other one on horizontal OR if both points are on vertical then there's atleast one horizontal line between them OR if both points are on horizontal then there's atleast one vertical line between them. sort the points and check.Don't downvote if I'm wrong or I cry :(
•  » » 9 days ago, # ^ |   +6 Just separate the points into two parts one where the x of the point matches with any of the x of vertical roads and other part where the y of the point matches with the y of any horizontal road. these two parts may or may not be disjoint as it is also possible that point's x as well as y matches with any vertical and horizontal road then this point will be the part of both parts.Now solve the answers for both the parts separately ->for 1st part Sort it using a comparater which sorts first according to y and then according to x. Now just iterate one by one on the points since the points are sorted using the above comparater so the points will be divided into groups which lie on the same horizontal line(same y) and this group is also sorted according to x also. Now we can see that the vertical roads divides the x axis into some segments. (x0,x1) (x1,x2) (x2,x3) ........for calculating the answer we will maintain one array f of size (n-1) where ith element represents the number of points that lie in the ith segment and whose y is also less than the current y(on which we are currently at in the iteration).f[i]=number of points which lie in the segment (x[i],x[i+1]) end points not included.for finding the segment-number of a point (a,b) we can easily find it using binary search(using lower_bound in c++)now let us assume we are at a point (a,b) so to find out the pairs that this point will make with other points that are already visited in the iteration we can make use of the array f.first we find the segment to which the point (a,b) lies and then the bad pairs which it makes is equal to f[segment-number]. because f[segment-number] stores the number of points that lie in that segment in the previous horizontal line (yb) then we need to add the point (a,b) to its respective segment(increment value of f[segment-number]) so that it can contribute the points which lie on the horizontal line above it.what we can do is we can maintain a cnt variable which stores the number of points which lie on the same horizontal line and in the same segment of x axis.When we move to next segment then we can just update the value of f[prev-segment-number]+=cnt.for 2nd part-Sort it using a comparater which sorts first according to x and then according to y. It's exactly same the difference is just the change of axis now we will iterate vertical line by line and in increasing order of x.Now the y axis is divided into segments.Link to my code- https://codeforces.com/contest/1569/submission/128325617
•  » » » 7 days ago, # ^ |   0 Thanx
 » 9 days ago, # |   +4 adedalic vovuh BledDest I recently discovered this youtube channel https://www.youtube.com/watch?v=ScJlgbUDMq4, where solutions of the ongoing contest are being shared. I was not able to solve any problem in this contest since I m a newbie but I also don't go for these unethical ways to increase my rating. Can anything be done against this form of cheating?
•  » » 9 days ago, # ^ |   0 These guys now even seem to be crowd-sourcing solutions.
•  » » » 9 days ago, # ^ |   +4 yep, I would be really happy if something could be done against these people
•  » » 9 days ago, # ^ |   0 And then I think why my rating is not increasing for so long!! :(
 » 9 days ago, # |   +95 A very heavy meme :
 » 9 days ago, # |   +1 I might go -200 today , I am not losing hopes
 » 9 days ago, # | ← Rev. 4 →   +6 My soln 128273615 of F should be hackable. I just have an early exit in case a particular assignment of colors finds a palindromic path. It reduces the time taken from 35s (locally) to 1s (on present test cases). 128279840 takes 30s — 40s locally on a complete graph. Update: Hacked by pikmike. Accepted submissions would now get TLE on tc 103 during system testing.Update 2: 128290681 should still be hackable.
 » 9 days ago, # |   +3 Solved C literally a minute after the contest ended damn
•  » » 9 days ago, # ^ |   +9 If it makes you feel better I forgot take mod of the final answer.
•  » » » 9 days ago, # ^ |   0 I forgot to use LL for D, and got two WA at testcase 6. After contest finshed I just realized...
 » 9 days ago, # |   0 Could anyone give me a hint for problem B ? I thought about using backtracking but could not implement it.
•  » » 9 days ago, # ^ |   0 Just try for individual competitions... using brute force suppose there are two players i and j, if any of them is aiming for 1, you can simply draw the match '=', if both are aiming for 2, think... if A has won in any of the previous matches... declare B and the winner and A as the looser, else B as the winner....In the end just check if all of the players were able to achieve their goals or not... the problem is solved...This is my submission... ignore everything above //MARK :- SOLUTION=====...I hope this will help... ;)128236197
•  » » 9 days ago, # ^ |   0 SpoilerHint : For people with expectation 2, they should only win against people with expectation 2 (since those with expectation 1 don't want to lose any games)
•  » » 9 days ago, # ^ | ← Rev. 4 →   0 First of all separate all the players who are satisfied with not losing a single match from those who need to win at least one as games need to be won or lost only in the case of the latter. Now, a valid solution can only exist if the number of unique pairs that can be formed between the players of the second type is greater than the number of players of the second type. Why? SpoilerBecause the pairs represent unique games; and we need at least n unique games between n players so that each player can win at least one. These wins can then be assigned in a very simple manner (1-2, 2-3, ..., n-1).
 » 9 days ago, # | ← Rev. 12 →   0 could problem C be solved using combinatorics? i tried below solution but i got wrong answer let maxValue = maximumValue in the array nextMaxValue = maxValue - 1 maxCnt = # maximum Value in the array nextMaxCnt = # nextMaxValue in the array fact[n] = n! (factorial) comb[n][r] = nCr (n Choose r) case1 if (maxCnt == 1 && nextMaxCnt == 0) answer = impossible case2 if (maxCnt >= 2) answer = fact[n]; case3 if (maxCnt == 1 && nextMaxCnt >= 1) r = maxCnt + nextMaxCnt answer = fact[n-r] * (comb[n][r] * (fact[r] - (fact[maxCnt] + fact[nextMaxCnt]))) ----updates---I got AC. after I use modular inversion when divide it. solution: https://codeforces.com/contest/1569/submission/128287672
•  » » 9 days ago, # ^ |   +1 in the last case, basically its the number of ways to put the maximum element in any spot while there exists atleast one or more nextMax on it's right side you can see my submission here https://codeforces.com/contest/1569/submission/128280479
•  » » » 9 days ago, # ^ |   0 thanks for the sharing. but could you elaborate more? I cannot understand left and right in your solution. or could you provide a related thread for it? Thanks in advance.
•  » » » » 9 days ago, # ^ | ← Rev. 3 →   +1 Yeah sure, so basically for instance in the last test case n = 6 and there's 3 NextMax so NextMaxCnt = 3 and so we have 2 elements that's less than NextMax, right? if we put the Max(which is 4) at any spot from 1 to 3 there's gonna always be a nextMax on it's right side. So the answer is premutation of the 5 spots (all spots except spot of the Max). now from spot 4 to 6, the answer would be the number of ways to have atleast one nextMax or more on the right side of the Max. There's many ways to calculate this but i calculated it by totalnumber of ways to arrange 5 spots subtracted by number of ways to have NO nextMax on the right side of the max. In my case left is just number of ways to order the left remaining spots on the left and right is the number of ways to have NON nextMax values on the right. Apologies if my explanation isn't the best.
•  » » » » » 9 days ago, # ^ |   0 Thanks for the explanation it helps a lot!
•  » » » » » » 9 days ago, # ^ |   0 if you still didnt understand it lmk. But basically the idea is to calculate the number of ways to have atleast one or more nextMax on the right side of the Max given that the max can be at any spot. There's many ways to calculate that i assume
•  » » 9 days ago, # ^ |   0 Well, cases to consider, Suppose maximum number present in array is X and second maximum is Y. i) When are we not going to have any nice permutataion? The case when X-Y>=2. Otherwise, ii) If there are two or more occurrences of X, we can always permute the whole array in any way possible and get a nice permutataion. So, that would be n! ways. or There is just one occurrence of X and some occurrence of Y. In that case, We can try to solve it by finding count of all permutation — permutataion when X comes after all occurences of Y.
 » 9 days ago, # |   +6 Nice problem E. I came up with some backtracking optimizations but couldn't complete it on time :D
 » 9 days ago, # |   0 Waiting for the solutions....
 » 9 days ago, # |   +4 Nice set of problems, got the logic for D but found it implementation heavy, it took all my time, and couldn't make code for it.
 » 9 days ago, # | ← Rev. 2 →   0 In E, is it fast enough to do 2^28 * (some big constant) ? It looked way too slow to me so I didn't code it, but the idea was to brute-force the first three levels of the tournament, bringing the number of contestants from 32 -> 16 -> 8 -> 4, and for the final four to have precomputed in O(32^4*2^4) all the numbers that can be achieved, for every possible quadruple of people playing. (I can see the hash of the first three levels, and substract it from H to get the required hash of the last levels).
 » 9 days ago, # | ← Rev. 3 →   -11 As a contestant solved one problem give me contributions (◕‿◕)
 » 9 days ago, # |   +3 How to do E?
•  » » 9 days ago, # ^ |   +3 For k=5 you just can solve for k=4 (2^15) and get the solution with meet-in-the-middle (2^8).
•  » » » 9 days ago, # ^ |   0 Oh, so for the "upper" part of the tree and the "lower" part of the tree, and you combine them in the final game where the total winner is determined? Or how do you split it
•  » » » » 9 days ago, # ^ | ← Rev. 2 →   +3 If you know winners of first phase(16 matches), 16 teams will remain and it's same as k=4 (You can determine places with O(2^(2^k-1)) bruteforce). To determine winners, you can split first 8 matches, and last 8 matches, and combine the results with meet-in-the-middle.
•  » » » » » 9 days ago, # ^ | ← Rev. 3 →   0 Ok I'm too dumb to understand I'll wait for the editorialEdit: Ok I understand now, thanks. The 2^8 is, for four possibilities of the first 2^16, who will win, and weather he will win once or twice. And same for the second 2^16, teams from [16,32], who will win and will the winner win again or not.
•  » » 9 days ago, # ^ |   +3 I tried to reduce the possibilities of backtracking by fixing the sum of eliminated people for every stages. I believe that will be enough to pass the tests in 4 seconds.
 » 9 days ago, # |   +3 C is just abbreviation for crying
•  » » 9 days ago, # ^ |   +3 It's pretty hard for C, lots of combinatorics
•  » » » 9 days ago, # ^ |   0 can any one give articles on combinatorics ?
 » 9 days ago, # |   0 Solved A , but why does a 2 pointer approach to solving it give TLE ?
•  » » 9 days ago, # ^ |   0 No fast IO?
•  » » » 9 days ago, # ^ |   0 I put fast IO and still TLE
•  » » » » 9 days ago, # ^ |   0 never use endl when printing. use '\n' instead.
•  » » 9 days ago, # ^ | ← Rev. 3 →   0 ? Couldn't it be solved in $\mathcal O(n)$?Here's the approach:First, obviously, if all the characters in the string are 'a' or 'b', there must be no solution. Otherwise, there must be a position $x$ that makes $a_x\neq a_{x+1}$, scan this string directly to find the position $x$. The answer is $x,x+1$. UPD: AC Submission 128343804
•  » » » 8 days ago, # ^ |   +10 Did this problem really worth time of CM?
•  » » » 8 days ago, # ^ |   0 I solved it that way , i was just interested in knowing why my first 2 pointers code didn't work so I can know when to avoid it
 » 9 days ago, # |   -100 All those who cheated in this round I hope you all die due to Covid-19 :).Peace!
•  » » 9 days ago, # ^ |   +1 I guess codeforces has a good system to detect cheaters
•  » » » 9 days ago, # ^ |   -17 Yeah! but still just wanted to say that anyways :)
•  » » 9 days ago, # ^ |   0 Woah bro, chill, there are way worse people who are still alive than those who cheat in online contests.
 » 9 days ago, # |   +6 when the editorial will come out?
 » 9 days ago, # |   0 Hi everyone, thanks for the contest I can't seem to figure out what I have done wrong in problem B. If anyone can provide with a test case so I can understand I would greatly appreciate it. Here's my submission: 128271618Thanks all!
•  » » 9 days ago, # ^ |   0 This fails: 1 5 22222
•  » » » 9 days ago, # ^ |   0 Hey thanks man, just tried it. I get that it fails, but I can't yet understand why? Do you happen to know?Thank you
•  » » » » » 9 days ago, # ^ |   0 Hey! Thanks for putting in the time and effort! Really helped me understand my mistake :) My greedy approach does in fact not work and now I understand whyThanks once again, I would uovote you more if I could
 » 9 days ago, # |   0 In problem C, I found the maximum number in the array and if it exists more than once, the answer should be n!. Because they will go to the end of the discussion together. But if there exists only once, We should put at least one maxi-1 in front of this maximum. - If maxi-1 is not in the array we should print 0 - Else we will permutate other numbers:We will replace other numbers except for maxi and maxi-1 after we have replaced them. Maxi and maxi-1 can be in number_of(maxi-1)! ways. after we have multiplicated them. We will print n! — this.
 » 9 days ago, # |   -43 All those who cheated in this round i hope you loose your genitals. Peace :) !
•  » » 9 days ago, # ^ |   0 He/She won't be in peace after losing them.
•  » » » 9 days ago, # ^ |   -11 That is what I hope for :)
 » 9 days ago, # |   +3 When the editorials will be published?
 » 9 days ago, # |   +3 And tasks were pretty good.
 » 9 days ago, # |   +6 This is the first contest in which I am able to solve problem B
 » 9 days ago, # |   +2 I made submission of Problem D in contest it gives TLE here.But After contest is over I submit same solution with no change it is working fine here . Why this is happening? I wonder if my TLE solution rerun after hacking is over?
•  » » 9 days ago, # ^ |   +4 The AC solution is way too close to time limit and +/- 50 ms is expected natural behaviour imo which depends on judging machine. So there are lot chances it might still tle after systest
 » 9 days ago, # |   0 I have coded the 1st question(That is equal no of 'a's and 'b's) thinking that even finding "ab" is sufficient as they haven't mentioned that the substring should be largest . can anyone please tell me whether I had taken it right because actually I got wrong for that question.
•  » » 9 days ago, # ^ |   +8 Yeah, it's right, but make sure you're also searching for "ba".
 » 9 days ago, # |   0 In problen D I tried to calculate count for points between consecutive 2 x-axis-parallel lines, which were grouped by their y-axis-parallel lines. The same works on y-axis. However the answer might always be little different to the Jurys answer. Any situation I missed or over-counted?
•  » » 9 days ago, # ^ |   0
•  » » » 9 days ago, # ^ |   +10 If a point is on the intersection, you should not count it, it adds 0 to the solution. If a point is on an X line, don't count it in solving for Ys, and vice versa.
•  » » » » 9 days ago, # ^ |   0 My sol had taken them into accout, so I think it may be some sneaky bugs.. Anyway, thanks!
 » 9 days ago, # |   0 That Problem C was simply wow! I did not have this much fun facing a problem in many days. Thank you!
•  » » 9 days ago, # ^ |   0 yeah, I also really enjoyed it!
 » 9 days ago, # | ← Rev. 6 →   +9 Solution for problem C: First sort array $p$. If $p[n] > p[n-1]+1$ then there is no solution. If $p[n] == p[n-1]$ then every permutation is a solution. The only case remaining is $p[n] = p[n-1] + 1$, note that a permutation is a solution in this case, if and only if, $n$ comes before at least one element equal to $p[n-1]$. It is easier to count the complement and subtract from $n!$. So let's count number of permutations where $n$ comes after every element equal to $p[n-1]$. Let $freq$ = count of elements equal to $p[n-1]$. Suppose element $n$ is at position $i$ in permutation. Note that $i>freq$ is necessary. We must choose $freq$ positions in prefix $[1..i-1]$ (binomial coefficient $i-1$ choose $freq$) to place all elements equal to $p[n-1]$ and also permute them between these positions. Remaining elements can go in any remaining position. Thus $ans$ is equal to the sum for all $freq < i < n+1$ of $i-1$ choose $freq$ multiplied by $freq! * (n-freq-1)!$. Note we can group all factors $freq! * (n-freq-1)!$ outside the sum. The sum of $i-1$ choose $freq$ for all $freq < i < n+1$ is equal to $n$ choose $freq+1$ (Hockey Stick Formula).
•  » » 9 days ago, # ^ |   +6 The third case where p[n] = p[n-1] + 1 can be simplified. Let freq = count of all elements = p[n-1]. Then answer simply is (freq*fact[n])/(freq + 1)Please correct me if i am wrong ( may be with an example )
•  » » » 9 days ago, # ^ | ← Rev. 2 →   +5 You are correct. We can simplify the answer = $\frac{n!}{(freq+1)! * (n-freq-1)!}*freq!*(n-freq-1)!$ = $\frac{n!}{freq+1}$ When we subtract this from $n!$ we get exactly what you wrote!!
 » 9 days ago, # |   +1 What is the intended solution for D? Are we supposed to do 6-8 binary searches to find the number of elements in some ranges ?
 » 9 days ago, # |   +6 Observations on Problem D: I could not get AC, but I hope the ideas below can help someone. Note that person $i$ and person $j$ form an incovenient pair, if and only if, they are on roads of the same type (vertical or horizontal) AND there is a road of the other type between them. Therefore, if person $i$ stands on both a vertical AND a horizontal road then this person cannot be in an inconvinient pair. We split set of people in $2$: people in vertical road $vert$ (sorted by $y$) and people in horizontal road $hori$ (sorted by $x$). We solve for each set separately and sum answers. We consider people in $vert$ one by one. Suppose we are considering person $i$. We keep a pointer indicating highest line below $i$. We also keep a queue of people already considered AND above this line. We keep a frequency array for $x$ coordinate of people in queue. In each iteration we update line by moving pointer to the right AND pop elements is queue below line. We add $queue.size() - freq[i.x]$ to answer. Set $hori$ can be solved in the same way.
•  » » 9 days ago, # ^ |   +4 You don't need to use queue. You can get an AC by every Time Binary searching as well.
•  » » » 9 days ago, # ^ | ← Rev. 3 →   +8 I guess the ideia is the same, both solutions explore Monotonicity. The only difference is in complexity analysis. Using pointers and queue we get $O(k*log(k) + k + n + m)$ solution because we sort each array but answer each person in amortized $O(1)$. Using binary search gives $O(k*log(k) + k*log(n) + k*log(m) + n + m)$ because we sort each array ($vert$ and $hori$) and perform binary search for each person in both. Both are ok for time limit.
•  » » » » 9 days ago, # ^ |   +4 Yess you are right.
•  » » 9 days ago, # ^ | ← Rev. 2 →   0 Finally got Accepted on problem D after reading this comment (plus ~2 hours of coding/debug), thanks a lot.
 » 9 days ago, # | ← Rev. 4 →   +3 I don't understand why my solution for problem B fails. For 4 2212 (failing 24th test) on codeforces my solution gives YES X+== -X== ==X= ===X However, on my pc, ideone, and random other compiler my program gives correct output YES X+=- -X=+ ==X= +-=X What have I done wrong???
•  » » 9 days ago, # ^ |   0 Solution for problem B: I will explain a possible construction of solution matrix. If a person wants to not lose any game, then we set all this person's game as DRAW. We store people who want to win at least one game in vector $must_win$. If $must_win.size() > 0$ AND $must_win.size() < 3$ note that solution does not exist. However if $must_win.size() > 2$ consider array as cyclical and let person $must_win[i]$ win against person $must_win[i+1]$. All conditions are satisfied by this construction.
•  » » » 9 days ago, # ^ |   +3 I did exactly that! Except a bit of different way: i marked all 1st type persons as draw between each other, then I gave victory to 2nd type person as soon as possible (and assigning defeat in the correct place, of course), any later game between 2nd types in matrix above the main diagonal is a defeat, below — win. Resulting in a nice right solution. But I dunno why in codeforces last 2nd type person somehow treated as first.
•  » » » » 9 days ago, # ^ |   +4 I looked at your code and I think I know what your mistake is. You need to reset your matrix for each test case. A character '+' or '-' from previous test case can interfere with your current test case!!
•  » » » » » 9 days ago, # ^ |   0 Thanks a lot, that helped!
•  » » 9 days ago, # ^ |   +12 When you create an array (not a vector) inside your main function, it can be filled with some weird values (its contents are undefined). So, when you try to compare $b[j][i]$ with some other values, the result of comparison may vary between different systems or even different launches on the same system.
•  » » » 9 days ago, # ^ |   0 Thanks a lot for the explanation!
 » 9 days ago, # |   0 Can anybody come up with a case where my 128251114 for B fails?
•  » » 9 days ago, # ^ |   0 ans[twos[twos.size() - 1]][0] = '+'; ans[0][twos[twos.size() - 1]] = '-'; Should be: ans[twos[twos.size() - 1]][twos[0]] = '+'; ans[twos[0]][twos[twos.size() - 1]] = '-'; 
•  » » » 9 days ago, # ^ |   0 Thanks for pointing out the error.
•  » » 9 days ago, # ^ |   0 1 5 12221Answer says first row has a minus. However, first item is a '1'. There should be no minus on the first row (1 means zero losses).
 » 9 days ago, # |   +3 When would the editorials be live?
•  » » 9 days ago, # ^ |   +3 After hacking is finished.
•  » » » 9 days ago, # ^ |   +3 Thank You so much for the information.
 » 9 days ago, # |   0 tutorial??
 » 9 days ago, # |   0 It was mentioned that this contest is rated...but it is not. I was unrated and still. Please, tell me if there is a problem. Thank you.
•  » » 9 days ago, # ^ |   0 You will be rated when the hacking is complete and final standings are published.
•  » » » 9 days ago, # ^ |   0 In about 12 hours.
•  » » » » 9 days ago, # ^ |   0 Thank you
•  » » 9 days ago, # ^ |   0 You'll be rated once hacking is finished
•  » » » 9 days ago, # ^ |   +1 Thank you. I have earned the rating. However, I want also to ask about my contribution. It is now -1. What does that mean. Thank you.
 » 9 days ago, # |   +1
 » 9 days ago, # |   0 Can anyone tell me why I'm getting RUNTIME error on TEST CASE — 3 My_B_Code
•  » » 9 days ago, # ^ |   0 try to use char arr[N+1][N+1] instead of string arr[N+1].
•  » » » 9 days ago, # ^ |   0 Can you please explain why is it so ??
•  » » 9 days ago, # ^ |   0 change: string arr[n+1] ; to: //string arr[n+1] ; vector arr(n+1, vector(n+1));
•  » » » 9 days ago, # ^ |   0 Can you pls explain why so ??
•  » » » » 9 days ago, # ^ |   0 string arr[n+1] is a 1-D array of string, which is like a 2-D array of characters. However, each string's length is not specified. You are accessing arr as if it were 2-D array of characters: arr[i][j]. Not specifying each string's length is the problem. It works ok only when n is small. When n is bigger, it is not ok. This code below is similar to the issue, but a bit easier to understand:  cin >> n; string s; for (int i=0; i
•  » » » » » 9 days ago, # ^ |   +3 Thanks Buddy !
 » 9 days ago, # |   0 Can problem C be solved in O(1)?
•  » » 9 days ago, # ^ |   0 It is obvious that the time complexity of the input is $O(n)$ .
•  » » » 9 days ago, # ^ |   0 I meant the solution itself without regard to input, like an $O(1)$ formula
•  » » » » 9 days ago, # ^ |   +1 If you get an algorithm which can solve it in $O(1)$ time without regard to input , that means you can get the answer without using the input numbers (if you use the input numbers , the time of iteration of the input numbers is greater than $O(1)$) . So why we input these numbers ?Can you get the meanings ?
•  » » » » » 9 days ago, # ^ |   0 lol, you're right... Confused C with something else, My bad.
•  » » » » 9 days ago, # ^ | ← Rev. 3 →   +1 There is an O(1) formula but it happens only after you spend 2N time (2 loops of size n each.) More specifically the answer is n! — (n — cnt — 1)! * cnt! * nC(cnt + 1) where cnt is the number of juries with the second largest number of tasks to tell.You can refer to my video and the pinned comment for more clarity on the same.Video Editorial for CCode demonstrating the O(1) idea
•  » » » » » 9 days ago, # ^ |   +3 that's great, here is the same idea, but more simplified.after sorting the array, if last two elements are same, then our answer is n!, means all permutations are nice.otherwise we can just subtract number of not nice permutations, which is eventually n! / (cnt+1), where cnt is count of second largest element.so our answer becomes n! — n! / (cnt+1).Here is my python submission
 » 9 days ago, # | ← Rev. 3 →   -16 I see a lot of contestants haven't received any penalty for wrong submissions before their first correct one! Can somebody kindly clarify?
•  » » 9 days ago, # ^ |   0 Submissions which fail on the 1st test case don't incur any penalty.
•  » » » 9 days ago, # ^ |   0 Thanks for your reply! That's advantageous for some but really disadvantageous for many. For example I managed to check if my code passes the sample testcases locally but one of my friend made 3 wrong submissions which didn't pass those. He is ranked better than me.
•  » » » » 9 days ago, # ^ |   +1 This is how it is (and should be). The first test case acts as an example on which you can test your code (and the compiler of your choice, if there are multiple versions). The question of it being an undue advantage to some users just doesn't arise...
 » 9 days ago, # |   0 Why is education more difficult than ordinary div2 ？
•  » » 9 days ago, # ^ |   0 If I am not able to solve C in the next round (probable), it will be a hat-trick.
•  » » » 9 days ago, # ^ |   0 Come on, boss, I'll watch you
 » 9 days ago, # |   0 Hey, why this contest is not rated, even though it is written it will be rated for the participants with rating lower than 2100. Can please anyone explain this? As I am new to the codeforces and this was my first contest..
•  » » 9 days ago, # ^ |   +3 Be patient, it takes time for the ratings to update.
 » 9 days ago, # |   0 I guess the open hack is over. But the contest rating has not been updated yet and the editorials as well.
•  » » 9 days ago, # ^ |   +6 Please be patient, it takes time to update the rating after checking and removing plagiarism
 » 9 days ago, # |   -36 fuck the rubbish contest
•  » » 9 days ago, # ^ |   0 Keep calm bro.
•  » » » 9 days ago, # ^ |   -39 The C Problem is such a rubbish,isn't it???
•  » » » » 9 days ago, # ^ |   0 And may I know the reason,why?
 » 9 days ago, # |   0 how to solve C?
 » 9 days ago, # |   +1 Where's the editorials?
•  » » 9 days ago, # ^ |   +13 The editorials are somehow a bit slow on "Educational" Rounds . Maybe they want us to think more and be better "Educated" :)Don't vote me back or I will be sad :(It may be just a joke :)
 » 9 days ago, # |   -6 Is everyone else rating changed after the contest? My is still not changed and also contest is not being reflected in my rating graph.
•  » » 9 days ago, # ^ |   +3 Man, this is not your first educational contest, so I am pretty sure you already know how they work. Is it really fun to ask such questions repeatedly? I am also sure that if you scroll a bit before commenting yourself, you will find a similar question, or two.
•  » » » 9 days ago, # ^ |   -12 Lol...it's my first educational round contest
•  » » » » 9 days ago, # ^ |   0 You literally participated in 2 in a row.
 » 9 days ago, # | ← Rev. 4 →   -13 Update : I just misunderstood the contest.Sorry to everyone. :(
•  » » 9 days ago, # ^ |   0 Where did you hear that?
•  » » » 9 days ago, # ^ |   -6
•  » » » » 9 days ago, # ^ |   0 Maybe the rating changes are yet to be done...
•  » » » » » 9 days ago, # ^ |   0 I hope so.
•  » » » » » » 9 days ago, # ^ |   0 I will become pupil , after so long . If it goes unrated, then it will be very sad for me :(
•  » » » » 9 days ago, # ^ |   +1 before rating change it shows like this in every contest :)
•  » » » » » 9 days ago, # ^ |   0 It will be nice.I admit I am a newbie here.
•  » » » » » 9 days ago, # ^ |   0 I realize I just said something stupid.How can I delete it? :(
•  » » 9 days ago, # ^ |   0 Come on man, don't lie. I am about to become expert for the first time.
•  » » » 9 days ago, # ^ | ← Rev. 2 →   -6 I'm looking forward to be an expert again.
•  » » 9 days ago, # ^ |   -14 Man,no one will believe in such a fucking Chinese like you!
•  » » » 9 days ago, # ^ |   0 WTF man , did he do something ?
•  » » » » 9 days ago, # ^ |   0 YES,he lied to us all!
•  » » » 9 days ago, # ^ |   +8 Inb4 you get banned
 » 9 days ago, # |   0 My solution for problem C is just a formula- if(count(max-1)!=1){ print(fact[n]); } else{ int cnt=count(max-1); int ans=fact[n]*cnt/(cnt+1); print(ans); }
 » 9 days ago, # | ← Rev. 2 →   0 Can someone explain me the idea behind B?
•  » » 9 days ago, # ^ | ← Rev. 3 →   0 First i filled the matrix with '.' , then , if the string has '1' at position i , then the best case for us would be that , he doesn't wanna lose , so we draw all the matches in row i , ie. fill the row i with '=' and fill i = j with 'X'. Now , iterating through the matrix , we check if there are some dots left , if we find dot and the corresponding (corresponding for i,j is j,i) is also filled with'.', then we put a '+' and fill corresponding with '-'. The row i had to win atleast 1 , which he did , so put all the '.' in the current row to '-' and the corresponding to those are replaced by '+'. After all the iterations for checking the case of -1 , what i did was check if the string given in input had 2 but if the row did not have any '+' , then answer is NO, else print the matrix formed. No condition can also be checked using a casework Submission link : https://codeforces.com/contest/1569/submission/128246925
•  » » » 9 days ago, # ^ |   0 Okay, thank you!
 » 9 days ago, # |   -9 Is this a rated contest?
•  » » » 9 days ago, # ^ |   -8 A 2 letter Or 3 letter word would be a great answer :)
•  » » » » 9 days ago, # ^ |   +9 A scroll up with the mouse will be much better ig :))
•  » » 9 days ago, # ^ |   0 YES
 » 9 days ago, # |   0 Why hasn't the result been out yet?
 » 9 days ago, # |   0 not lighthearted meme
•  » » 9 days ago, # ^ |   0 :Sadge:Waiting for -ve delta like :')
 » 9 days ago, # |   0 When rank is rated :(( ?? I look forward a better rank through this contest hmu
 » 9 days ago, # | ← Rev. 2 →   0 For Problem D can someone please tell me how to find points like (2 and 7) in the second test case since I need to subtract these points from my final answer? i.e points which have either same x co-ordinate or y co-ordinate and there is no line which is intersecting between the points.
 » 9 days ago, # |   +20 To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!
•  » » 9 days ago, # ^ |   +3 The comment every newbie was waiting for lmao. I'm not a bad person guysWishing +ve delta for everyone :')
 » 9 days ago, # |   +3 Can someone give some strong test cases for D? I thought of every test case I could and stil couldn't figure out the bug in my code.
 » 9 days ago, # |   0 yamete kudasai
 » 8 days ago, # |   0 Thank you because of this helpful contest!
 » 8 days ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 8 days ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 8 days ago, # |   +4 Contrary to all the comments complaining about problem C, I found solving problem C was very enjoyable. I felt it was a good Combinatorics problem, especially for newbies like me.When I read the statement I instantly realized that the largest element would always be the last to remain, and the same thing for the second largest element. Thus I only need to pay attention to these two. I then tried permutating the 2 elements to see what would happen if the second largest was before the largest, the largest was before the second largest, etc. I later deduced that: If the second largest equals the largest, they will be the last elements in the array together after deletion, so every permutation of that array is a nice permutation. If the second largest is smaller than the largest by 2 or more, we need extra decreases just for the largest element only. Hence, no matter how the array was arranged, the array remained not nice and the answer was 0. Else, the array is nice only if there exists at least one second largest element after the position of the largest element in the array. The first 2 cases could be solved simply by using $std::map$ or sorting. I did struggle with the last case at first since I couldn't come up with any formula to count, but then I found out I could solve it by counting the opposite case when the permutation was not nice. Let's call the largest element $x$ and the second largest one $y$. To start with, I fixed the position of the $x$, so it looked something like this:_ _ _ $x$ _ _In order to make the array not nice, in the last 2 slots, we should choose any elements other than $y$. It means that we need to choose 2 numbers from the set of numbers not including $y$, or $P(k, 2)$ with $k$ is the size of the set of numbers excluding $y$. We can calculate $k$ by subtracting the number of elements in the array (which is $n$) by the number of $y$ and then subtracting it by $1$ (the element $x$ itself). But that's not all, we can continue to permutate the first 3 slots, thus multiplying the answer by $3!$. So the general formula for $x$ at any position $i$ is: $P(k, n - i + 1) * (n - i)!$With $n - i + 1$ is the amount of slots after $x$ and $n - i$ is the amount of slots before $x$. Little note that when $n - i + 1$ is larger than $k$, $P(k, n - i + 1)$ is $0$ instead. I prebuilt a factorial array so I could calculate $(n - i)!$ in $O(1)$, then I used fast exponentation for the modular inverse needed to calculate $P(k, n - i + 1)$, making each position $O(logN)$. Finally I iterated every position from 1 to $n$, so the total complexity is $O(N*logN)$.Unluckily I didn't solve this problem quick enough, so I wasn't able to make a submission before the end of the contest. Still feel pretty bad now :(((
 » 8 days ago, # |   +9 I have earned the rating. However, I want also to ask about my contribution. It is now -1. What does that mean. Thank you.
•  » » 8 days ago, # ^ |   0 Well, that means that you are asking questions that were disliked by the community. The contribution is somehow calculated using the numbers of upvotes and downvotes your comments have.
•  » » » 8 days ago, # ^ |   +9 I got it. Thank you
 » 5 days ago, # |   0 For some reason, it showed plag for a certain question in this contest, they cancelled the contest for me. I'm not that very much concerned about that but are there any further measures?
 » 3 days ago, # | ← Rev. 7 →   0 The comment is hidden due to the large number of negative reviews about it, click here to view it
•  » » 3 days ago, # ^ |   0 Its the second time this happened today.