By awoo, history, 14 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 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!

UPD: Editorial is out

• +271

| Write comment?
 » 14 months ago, # |   +19 Educational rounds are the best always good problems with good ideasGood luck everyone and happy solving
•  » » 14 months ago, # ^ |   +25 Bro why aren't the ratings yet updated?
•  » » » 14 months ago, # ^ |   +5 When will they update ratings?
•  » » » » 14 months ago, # ^ |   +3 I guess we need to make some sacrifice to codeforces god for updating ratings
•  » » » » » 14 months ago, # ^ |   +15 The codeforces god was not pleased with your sacrifice so even the previous ratings are rolled back
•  » » » » » » 14 months ago, # ^ |   0 -40 and -30, i am okay with that
•  » » 14 months ago, # ^ |   +6 When will the Codeforces rating update?
 » 14 months ago, # | ← Rev. 2 →   +79 I always had a question, How do you prepare educational contests so fast? Because creating new problems in one week is so difficult! awoo BledDest
•  » » 14 months ago, # ^ |   +38 They have a lot of experience
•  » » » 14 months ago, # ^ |   +24 I know they are so experienced, But creating a new problem (actually a new hard problem which has standards of CF) is difficult, and I appreciate them for their hard work, Good job !
•  » » 14 months ago, # ^ |   +53 They must have unlimited problem generator AI...
 » 14 months ago, # |   -36 Hoping to become specialist after this :)
•  » » 14 months ago, # ^ |   -30 All the best vro
•  » » » 14 months ago, # ^ |   -26 Peeps on cf downvoting anything ಠ_ಠ, a genuine wish ¯(°_o)/¯
 » 14 months ago, # |   0 A long wait of almost 10 days after this contest : ( Waiting for this contest to be awesome and welcoming the fellow coders to have great competition : )
 » 14 months ago, # |   -21 Educational rounds don't charge penalty points for wrong submissions??
•  » » 14 months ago, # ^ |   +21 The penalty for each incorrect submission until the submission with a full solution is 10 minutes. Maybe read the blog?
 » 14 months ago, # |   +79 As a Romanian, it's pretty cool to participate in a Codeforces round on the National Day of Romania (which is today, December the 1st)! Light-hearted meme
•  » » 14 months ago, # ^ |   +2 Share and subscribe.
 » 14 months ago, # |   0 Why codeforces has become speedforces from past 2 — 3 contests.
 » 14 months ago, # | ← Rev. 2 →   -46 Okay fine D is the best problem I have ever seen, like enough already
•  » » 14 months ago, # ^ |   +42 why?
•  » » 14 months ago, # ^ |   +12 because you didn't solve it?
 » 14 months ago, # |   +31 Just one question... Monocarp is some type of reference or the name of a famous person? I have also seen PolycarpMaybe carp means something that I don't know in english
•  » » 14 months ago, # ^ |   +9 Carp is a large fish that lives in lakes and rivers
•  » » 14 months ago, # ^ |   +131 The name Polycarp (which is a usual Russian name, though an uncommon one) was very commonly used in contests made by authors from Saratov State University, namely MikeMirzayanov and his students. The name Monocarp (which is NOT a usual Russian name) was originally used as a one-time joke for one of the ICPC qualification stages in our region (as a reference to Polycarp), but later on, we chose to make Monocarp the main character of most our problems.
•  » » » 14 months ago, # ^ |   +21 Oh, what a story! I really didn't expected that.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 Was that inspired by Monogon? :)
•  » » » » 14 months ago, # ^ |   +15 The first contest with Monocarp was in 2018, so, actually, Monogon was inspired by Monocarp.
•  » » 14 months ago, # ^ |   +14 I used to read it as PolyCRAP and MonoCRAP
 » 14 months ago, # |   +14 The difficulty gap between C and D is just too much. C is too easy for its position and D is too hard...
•  » » 14 months ago, # ^ |   +5 Also I found B to be easier than A
•  » » 14 months ago, # ^ |   +9 Just try E
•  » » » 14 months ago, # ^ |   0 how to solve E? i was trying bfs from lab vertex is that correct ?
•  » » » » 14 months ago, # ^ |   0 yes. You then just have to check that you don't have more than 1 dot as neighbour.
•  » » » » » 14 months ago, # ^ |   +2 i am doing that ,though getting wa on test 3.
•  » » » » » » 14 months ago, # ^ |   0 What you are doing seems quite complicated, I believe it's you trying to debug your code. my code should show that the approach works and is quite readable (just don't ask me why I converted chars to int to convert it back at the end!)
•  » » » » » » » 14 months ago, # ^ |   0 thanks ,i got the mistake ,it was in the implementation.yeah it was very difficult to debug it ,thats why i was doing multiple submissions
•  » » » » » » » 14 months ago, # ^ | ← Rev. 4 →   +5 Comment partly deleted to reduceit's size since intimidator found his issue. not much value in it anymore and it took plenty of space in the thread
•  » » » » » 14 months ago, # ^ |   0 realized it just after the contest...
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 I had one approach like, mark all the free cell + except the cells that helps in forming a cycle within a matrix. Because, robot just not follow the command and will move in cycle infinitely.Is this a right approach ?
•  » » » » 14 months ago, # ^ |   0 Also you don't need to mark as + vertices that don't have a path to L. And finding all vertices that are on a cycle doesn't look like a very easy task.
 » 14 months ago, # | ← Rev. 2 →   -10 Please list out the 7 sequences for sample test 4 in quest D40 1 2 3which satisfy
•  » » 14 months ago, # ^ |   -8 I wasn't able to find them either
•  » » 14 months ago, # ^ |   +8 [0], [0, 1], [1], [0, 2], [0, 1, 2], [0, 1, 3], [0, 1, 2, 3]
•  » » » 14 months ago, # ^ |   -7 how [0,1,2] is valid?
•  » » » » 14 months ago, # ^ | ← Rev. 3 →   +12 we have b = [0,1,2]i = 1 -> mex(b[1]) — b[1] = mex(0) — b[1] = 1 — 0 = 1 <= 1i = 2 -> mex(b[1],b[2]) — b[2] = mex(0,1) — b[1] = 2 — 1 = 1 <= 1i = 3 -> mex(b[1],b[2],b[3]) — b[3] = mex(0,1,2) — b[1] = 3 — 2 = 1 <= 1Don't forget that mex(x1,x2,...xk) = smallest element that no appear in that sequence, mex != max!
•  » » » » » 14 months ago, # ^ |   0 Ahhh, Got It,Thanks
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   +6 mex(0) = 1; |0 — 1| = 1mex(0, 1) = 2; |1 — 2| = 1 mex(0, 1, 2) = 3; |2 — 3| = 1
•  » » 14 months ago, # ^ |   0 0 1 01 02 012 0123 013
•  » » 14 months ago, # ^ |   -8 Same Doubt
•  » » 14 months ago, # ^ |   +5 00, 10, 1, 20, 1, 2, 30, 1, 30, 21
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 Wasn't it stated in problem description that here you can take any sequence? edit: nvm
•  » » 14 months ago, # ^ |   +5 1) [0]2) [0,1]3) [0,1,2]4) [0,1,2,3]5) [0,1,3]6) [0,2]7) [1]
 » 14 months ago, # |   +34 How to solve F?
•  » » 14 months ago, # ^ |   +52 Let's solve it by inclusion exclusion principle, let's denote $f(x)$ as the number of permutations with at least $x$ edges such that $c_{child} = c_{parent} + 1$. The answer to the problem is $f(0) - f(1) + f(2) - f(3) + f(4)$... up to n.To compute $f(x)$ for some fixed $x$, $x$ nodes should have exactly one child with their value minus one (it is impossible to have more than one since it is a permutation).Let $g(x)$ will be the number of ways to select $x$ edges such that there are no two edges with the same parent node, this can be reduced to a knapsack problem, with the degrees as items, all $g(x)$ can be solved in $O(n\log^2{n})$ with divide and conquer and fft since the sum of all items is up to n.Finally, $f(x) = g(x) \cdot (n-x)!$ since $x$ numbers are equal to the number of their parents minus one, so there are $(n-x)!$ possible permutations.
•  » » » 14 months ago, # ^ |   0 Thank you, can you please clarify a bit more on reducing the problem of selecting X egdes to knapsack problem? And how you can find all g(i) in O(n Log^2n) ?
•  » » » » 14 months ago, # ^ |   +14 For each node, 1) you choose a child that has their value minus one (select one edge) 2) not choose any child (no edge selected) There are (number of child) ways to choose 1). By multiplying (x + number of child) for every node, we can get a polynomial which the coefficient of x^i represents g(N-i). Multiplying N linear polynomial can be done in O(Nlog^2N) using FFT and divide and conquer.
•  » » » » » 14 months ago, # ^ |   0 Beautiful, thank you!
•  » » » 14 months ago, # ^ |   0 How to proof f(x)=g(x)⋅(n−x)!, I just can't notice that...
•  » » » » 14 months ago, # ^ |   +3 Also took me a bit of time to understand this. I think the proof below works.You need to prove that there is a bijection between a valid configuration (i.e. values that satisfy the parent-child constraint for each of the $x$ selected edges) and the relative ordering of non-child nodes (there are $(n - x)!$ relative orderings). Note: with child nodes I mean the children of the $x$ selected edges. If there is a bijection it means that both sets are of equal size, and therefore there are $(n - x)!$ valid configurations.To prove that it is a bijection we need to prove that For each valid configuration there is exactly one corresponding relative ordering of the non-child nodes Proof: Since all values in a valid configuration are unique, the relative ordering of the values of the non-child nodes within the valid configuration is unique. For each relative ordering of the non-child nodes there is exactly one corresponding valid configuration Proof: If we fix the relative ordering of the non-child nodes, then the relative ordering of the child nodes is also fixed. Because for every child node its order must be equal to the order of the parent minus 1. Therefore there is exactly one way to achieve a valid configuration starting from a relative ordering of the non-child nodes.
•  » » » » » 14 months ago, # ^ |   0 thanks!!
 » 14 months ago, # |   -7 how to solve b?
•  » » 14 months ago, # ^ |   +9 x mod y always gives values between [0,y-1] if we choose y as smallest element of the array then it is obvious that our requirements are met (given in the question)
•  » » » 14 months ago, # ^ |   0 Ah wow, how did I not realize this.... :(
•  » » 14 months ago, # ^ |   0 take the smallest number as y in all pairs. since x % y < y it satisfies the conditions
•  » » 14 months ago, # ^ |   0 Just take y as smallest element in array so that remainder is [0 , y-1] which doesnt exists in the array
 » 14 months ago, # |   0 What is test 2 of D ? I cannot figure out the edge case i am missing.
•  » » 14 months ago, # ^ | ← Rev. 2 →   +1 I have failed on this one: 4 0 2 2 0 
•  » » » 14 months ago, # ^ |   0 Is the answer 6?
•  » » » » 14 months ago, # ^ |   +3 It's 9
•  » » » » » 14 months ago, # ^ |   0 [0] [0] [0 0] [0 2] [0 2] [0 2 2]Can you point out the other 3?
•  » » » » » » 14 months ago, # ^ |   0 Don't forget that you can also put '0' after '2' and get another 3 combinations.
•  » » » » 14 months ago, # ^ |   +6 It should be $9$. 0 0 2 0 2 0 2 2 0 0 0 0 2 0 0 2 0 0 2 2 0 These are possible combinations. $0$ can be placed after $2$.
•  » » » » » 14 months ago, # ^ |   0 Ah right! Thanks
•  » » » 14 months ago, # ^ |   0 Thanks! It helps a lot
•  » » 14 months ago, # ^ |   0 same here
 » 14 months ago, # |   +21 Wasted a lot of time in D , could have done E instead.
•  » » 14 months ago, # ^ |   0 Figured out E 3 mins after contest :/
 » 14 months ago, # |   +23 For me, A > B and D > E. In other words, I felt E was easier than D and B was easier than A. Although A was easy too, just some bit of implementation.
•  » » 14 months ago, # ^ |   +9 It was very easy to lose yourself into the implementation details of A and this is why I also felt like A was (much) harder than B.
•  » » » 14 months ago, # ^ |   +2 I guess much of A's implementation can be made easier if you consider x1 and x2 as strings rather than integers!
•  » » » » 14 months ago, # ^ |   +2 That's actually what I did, as I struggled a lot with x1 and x2 implemented as ints, and then I thought: "screw it, I'm gonna do this cheap string trick"
•  » » » » 14 months ago, # ^ |   0 Or you can just subtract min(p1, p2) from p1 and p2, and then if min(p1, p2) + 8 < max(p1, p2), number who has bigger p is bigger, else you can just multiply x1 with 10^p1 and x2 with 10^p2, and check them like usual numbers.
 » 14 months ago, # |   +8 Who thought that E was that hard and even harder than D man, that problem can be even a harder div2C, it's just a bfs.
 » 14 months ago, # |   +12 I love the problem D, the solution is beautiful and it has two of my favorite subjects, combinatorics and DP!
 » 14 months ago, # |   +43 Once again!!
•  » » 14 months ago, # ^ |   0 I found C easier than B , and i think my solution to B is terrible, because i used brute force and depended on the case (f[1]!=0) 137676564
•  » » » 14 months ago, # ^ |   +8 i saw that coming :D (hacked) 137676564
•  » » 14 months ago, # ^ |   +8 Bro C was just binary search. It was easier than most Cs we see in div2. I was surprised at how direct it was actually
•  » » » 14 months ago, # ^ |   +3 My purpose is to tell how hard D is compare to A,B,C :> i'm not telling that C is hard.
•  » » » » 14 months ago, # ^ |   0 Oh i get it now, that's true, i can't even understand the solution of D
 » 14 months ago, # | ← Rev. 2 →   -26 Question C could be solved with iterative binary search (https://codeforces.com/contest/1613/submission/137689165) but was giving TLE(at test case 5) with recursive binary search (https://codeforces.com/contest/1613/submission/137672043). This cost me 3 wrong submissions and a lot of time!
•  » » 14 months ago, # ^ |   +3 My recursive binary search solution passed (https://codeforces.com/contest/1613/submission/137671370).
•  » » » 14 months ago, # ^ |   0 Its not recursive is it. You are using while(s<=e) { } The binary search is iterative.
•  » » 14 months ago, # ^ |   +1 The issue is that you added an extra min operation to your recursive function which caused it to keep around a lot of unnecessary info on the stack- your solution passes if you just remove the minhttps://codeforces.com/contest/1613/submission/137709365
•  » » » 14 months ago, # ^ |   +5 Such a small change and it changes the result. Great debugging!
•  » » » » 14 months ago, # ^ |   0 Reason why he is purple :_:
 » 14 months ago, # |   0 This is my first time attending cf contest!Just curious that if I'm currently unrated, would this contest be rated for me?
 » 14 months ago, # |   0 How to solve D?
•  » » 14 months ago, # ^ |   +14 Use dynamic programming. You can get that there are only some types in mex correct sequence. First of all, Thre are a sequence which starts with 0 and looks like 0 0 0 .. 0 1 1 1 .. 1 2 2 .. 2 ...(from 3 to n-1) n n .. n n n. In this case, you can expand this sequence with adding n, n+1, or n+2. Also, there is another type of sequence. which also starts with 0 and like 0 0 0 .... (from 1 to n-1) ... n n n ... n+2 n n+2 n+2 n n n (don't have to alternative, just after all, you should add either n or n+2) In this case, you can exapnd this sequence with adding n or n+2 Finally, you can think about this kind of sequence: which is composed with only 1, like 1 1 1... 1. count first two kinds of sequences with dynamic programming with dp[i][j]=number of sequence which ends with i and type is j(either first or second) and count last one with just counting the number of 1. number of last kind of sequence is 2^cnt-1
•  » » » 14 months ago, # ^ |   +8 I found this observation during contest but couldn't figure out how to implement in dp.Anyway I will now learn, thanks for help
•  » » » » 14 months ago, # ^ |   +4 Once you get that observation, then I think checking with some cases(which are on the above)will be helpful to you. I also struggled with some wrong cases at first.
•  » » » 14 months ago, # ^ |   +4 1 1 1... 1 sequence could be a special case of 0 0 0 .... (from 1 to n-1) ... n n n ... n+2 n n+2 n+2 n n n . So there is only two types of sequences: MEX n with max n — 1, MEX n with max n + 1.
 » 14 months ago, # | ← Rev. 4 →   0 any idea why this is wrong? this is problem C, I did binary search and pretty sure it is correct, but it gives wrong answer, ;_;like I dont even get why 456 is not a correct solution for the last test case of sample tests? I am getting 456 as my answer to binary search and 456<470 (given answer) Help! please
•  » » 14 months ago, # ^ |   0 maybe you should use this: min((i+1
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 Man, you are right!! Thanks a lot!!!! But what is the difference between the two? ;_; I dont think I would have ever been able to debug this.
•  » » » » 14 months ago, # ^ |   0 maybe you read the wrong question，the poison affect is refesh, not stack. And the time to kill dragon may bigger than 1e18
•  » » » » » 14 months ago, # ^ |   0 Can you explain how the answer can be bigger than 1e18. I wanted to hack a solution because of this but could not come up with a case that has ans > 1e18.
•  » » » » » » 14 months ago, # ^ |   +4 I mean the time to kill dragon may bigger than 1e18, not the ans. ans <= 1e18. if n = 1 and h = 1e18 and a[1] = 1e9, than the answer is 1e18 but you will kill the dragon at the moment of 1e18 + 1e9 — 1 which is bigger than 1e18
•  » » 14 months ago, # ^ |   0 a[i+1]-a[i]?Also (int)1e18 will overflow. Use long long.
 » 14 months ago, # |   +39 Nice problemset, I enjoyed solving A-E! Looks like I'll also learn a lot from F once the editorial is published.
 » 14 months ago, # | ← Rev. 3 →   -79 [Deleted]
•  » » 14 months ago, # ^ |   +10 why??everyone knows that endl is slower than "\n"
•  » » » 14 months ago, # ^ |   -51 but not like more than 3 times slower
•  » » » » 14 months ago, # ^ |   +1 actually, it's more than 10 times I guess. After I read this I changed my code from using endl to "\n", and the 2000ms tl become 217ms AC. Really learn a lesson in this problem.
•  » » 14 months ago, # ^ |   +27 You learnt something new! What I would do after something like this, is try to find out why this happens. I would recommend you to do the same ;)
 » 14 months ago, # |   +1 Thanks to this contest that I realise "cout << endl" will get TLE for the first time 137704588 137708870
•  » » 14 months ago, # ^ |   +20 That particular test case you are flushing the console 10^6 times hence TLE
 » 14 months ago, # |   +1 Is there any idea to solve F? I enjoyed A to E but I couldn't get some idea to solve F. I think there should be some combinatorical good theory to solve.
•  » » 14 months ago, # ^ |   +4
•  » » » 14 months ago, # ^ |   0 Thanks a lot!
 » 14 months ago, # |   0 Does anyone knows why my submission for A is getting WA? As far as I know, it's mathematically correct but I can't figure out a test case that breaks it, thanks a lot. (The idea behind the solution is to represent both numbers as x+(10^p) and then take it log10 to reduce its size and compute the number) (also note that lli is defined as double)
•  » » 14 months ago, # ^ |   0 you use a and b as length, but then when you compare them, if you have a = b, you print equality, although this is equality of lengths, not numbers
 » 14 months ago, # |   +17 For those struggling with TLE at test case 16 in E , when printing out the grid change from $endl$ to \$n$ and TLE will be gone
 » 14 months ago, # |   +124
•  » » 14 months ago, # ^ |   +14 Your AC code scared me
•  » » 14 months ago, # ^ |   +4 At the cost of increasing your endurance to solve hard problems
•  » » 14 months ago, # ^ |   +4 You are a beast for coming up with a solution, no matter the cost! Congratz!
•  » » 14 months ago, # ^ |   +3 GAWD LEVEL
•  » » 14 months ago, # ^ |   +6 Wow I wish i could have endurance like you during contest :).
 » 14 months ago, # |   +3 Can someone help me better in understanding what i could have done better to avoid wrong answer for problem C?Here is my solution -> https://codeforces.com/contest/1613/submission/137670768
•  » » 14 months ago, # ^ |   +3 In check function value will get overflow when n = 100
•  » » » 14 months ago, # ^ |   +1 not really.He has added n+1-th element too.See in the main function
•  » » 14 months ago, # ^ |   +2 v.pb(1e12);Here,because h can up to 1e18..that's why you are getting wrong answer
•  » » 14 months ago, # ^ |   +2 v.pb(1e12) and h = 1e18 => ans maybe > 1e12"wrong answer 1st numbers differ — expected: '433940482775969078', found: '1'"
•  » » 14 months ago, # ^ |   +5 Add 1e18 to your array instead of 1e12.
•  » » » 14 months ago, # ^ |   +5 Adding just 1e18 to the array wouldn't be enough, see https://codeforces.com/contest/1613/hacks/773649This contest offered so many amazing hacking opportunities. Weak pretests made the hacking stage very entertaining. And it's still not over, because the incoming system test (with all hacks included) is likely to claim even more victims.
 » 14 months ago, # |   -25 E. 2000ms for 1e6 input == Downvote
 » 14 months ago, # |   +13 I am not a detective, but this group of contestants looks sus fifijonil nexoxogoc ybgbsydvh ouhtek robot_bobot
•  » » 14 months ago, # ^ |   0 as well as these two submissions 137693885 137674037
 » 14 months ago, # | ← Rev. 2 →   0 Could someone explain why my submission to A fails? I am converting both numbers to scientific notation and then comparing the numbers. Does it have something to do with errors regarding precision?Update: Well I did not know about such precision issues. But it turns out the error in my program is actually in the while loops because I was not converting numbers to scientific notation. In my old solution, I have > 10 when it is should be >= 10. Here is an accepted solution of converting the numbers to scientific notation.tldr: converting to scientific notation seems to be a valid solution to A.
•  » » 14 months ago, # ^ | ← Rev. 3 →   0 Indeed it haseg. if I run this codedouble x = 0.1;cout << (x * 3 == 0.3) << endl;result is 0 (false) for me
 » 14 months ago, # |   0
•  » » 14 months ago, # ^ |   0 you can't compare numbers after mod operation, order is lost.(7 mod 5) > (10 mod 5), but 7 < 10
 » 14 months ago, # |   0 Is there any standard concept for solving problems like C?
•  » » 14 months ago, # ^ |   +9 Binary search on answer.
 » 14 months ago, # |   0 As this is a DIV 2 contest, why does nothing change, when ticking the box "show unoffical". Do I miss something?
•  » » 14 months ago, # ^ |   0 Div1 participants also appear in the standings table
 » 14 months ago, # |   0 Any hints for dp states of problem D?
•  » » 14 months ago, # ^ | ← Rev. 2 →   +12 Spoilerdp[x][2]dp[x][0] -> no of subsequences ending at x — 1, such that mex is xdp[x][1] -> no of subsequences ending at x + 1, such that mex is xEdit: For thorough explanation: See my video explanation
 » 14 months ago, # |   0
 » 14 months ago, # |   0 How does https://codeforces.com/contest/1613/submission/137705083 work but https://codeforces.com/contest/1613/submission/137689153 WA on Test 10? Is this a thing with Python, or specifically with the math module in Python?
•  » » 14 months ago, # ^ |   0 h can be up to 10^18. Numbers above 2^53 cannot all be represented exactly by floats, so you lose precision.
 » 14 months ago, # |   +3 E was pretty easy compared to D..the setters should try to place problems at the right place.A good contest btw
 » 14 months ago, # |   0 The heart is too anxious to miss green name. Too many penalties。 But the experience is better
 » 14 months ago, # | ← Rev. 2 →   0 Why don't you let $O(n\sqrt n\log n)$ pass F?upd: I try my best to make it $O(n\sqrt n)$ and it finally passed.
•  » » 14 months ago, # ^ | ← Rev. 2 →   +9 [deleted]
 » 14 months ago, # |   0 Hope not to be heacked……
•  » » 14 months ago, # ^ |   0 Maybe it is "hacked", not "heacked".
•  » » » 14 months ago, # ^ |   0 I'm poor in English……
 » 14 months ago, # |   -6 Where are the editorial for the problems?
•  » » 14 months ago, # ^ |   0 Just wait
•  » » » 14 months ago, # ^ |   0 Still waiting
 » 14 months ago, # |   0 Need help in question E.Getting WA.My approach was as follows.1)Start BFS from Lab3)While traversing push the co-ordinates of the cell which is free, only if at max there are 2 direction in which you can go(one of which will lead to lab).Please tell what is wrong with my approach
•  » » 14 months ago, # ^ | ← Rev. 5 →   0 try this testcase: 1 5 5 ##.## ..... .#.#. .#.#. ..L.. All the . should be + in answer.
•  » » 14 months ago, # ^ |   0 Not max 2 but max 1, you should replace '.' with '+' after each steps to reduce it down to 1 (if possible)
 » 14 months ago, # |   +1 I love problems like F. It requires unique ideas and has simple implementation(if you have the code for FFT).
 » 14 months ago, # |   0 I'm surprised that everyone uses BFS for problem E.
•  » » 14 months ago, # ^ |   +11 Why? Looks like it's obvious solution
•  » » » 14 months ago, # ^ |   +1 I use DFS actually, I thought everybody did so, but no.
 » 14 months ago, # |   0 why my java code is giving tle for 'D' problem, it's giving AC in c++ 137748948
 » 14 months ago, # |   0 Just a small question, DFS on E gives runtime error while BFS passes. So in c++, cant we make 1 million nested function calls ? Does anyone know approx. what is the maximum number ?
•  » » 14 months ago, # ^ |   0 You can get passed with DFS on E, check my submission: 137662230
 » 14 months ago, # |   0 O(NlogN) for N<=100 solution C instead of expected O(Nlog10^18) https://codeforces.com/contest/1613/submission/137680384
 » 14 months ago, # | ← Rev. 2 →   0 Update: Ok it got hacked
•  » » 14 months ago, # ^ |   +6 input1 3 31 ############################..# .............................L. ############################..#  output############################++# +++++++++++++++++++++++++++++L+ ############################++# 
 » 14 months ago, # |   -12 When will we get editorials?
•  » » 14 months ago, # ^ |   +1 I guess it will be similar to past educational rounds? I don't get why people who have already participated in educational rounds keep asking the same sort of questions again and again? Do y'all run some script which posts some preset comments on recent blogs?
•  » » » 14 months ago, # ^ |   0 you should learn how not to overreact on things unnecessarily
•  » » » » 14 months ago, # ^ |   +20 I agree, maybe I could have stated my point a tad bit more politely. However, I am still curious as to why you posted the comment you did. Were you hoping for early editorials this time? If yes, then why? If no, then why the comment?
•  » » » » » 14 months ago, # ^ |   -21 every person in the world has rudeness hidden inside them but you don't express it everywhere + everything you write don't have to be extremely pre-thought that whether it will have any affect or not.Suppose if a round gets delayed by 10 minutes, does a comment of some people make the round held earlier???No,but it is human instinct to write comments at that time, why delayed!!!And it would be foolish to react on those sorts of comments
 » 14 months ago, # |   0 So when are the ratings coming?
•  » » 14 months ago, # ^ |   +4 Have patience bro and do upsolving because hope you was not able to solve all the problem.
 » 14 months ago, # |   +8 Here are the video Solutions to the first 5 Problems in case you are interested.
 » 14 months ago, # |   +1 Submitted problem D twice, the only difference was in one line (I commented out "cerr << ..." in the second submission). Got idleness limit exceeded in the first submission. Can anyone tell me why this happened? And why did the idleness limit exceed on test 2, not test 1? Should it maybe be rejudged?
•  » » 14 months ago, # ^ |   0 Even though cerr output is not interpreted as the answer and does not get rejected as WA, it still causes a significant slowdown. The only mystery is why was this failed submission reported as "Idleness limit exceeded" instead of TLE?
 » 14 months ago, # |   +14 Why aren't the ratings still updated?
 » 14 months ago, # | ← Rev. 2 →   0 My submissioncan anyone find the flaw in my idea for problem D it passes 2 test cases and give WA on 3rd my idea I used dpthe required sequence can be only of three types 0->0,1,2,3(consecutive) 1->0,1,3 (one skipped) 2->0,1,3,1,3,1,.....(alternating after one skipped)so i created a dp[n+1][3] where first state corresponds to ending number of a sequence and second corresponds to type of sequence my transitions for i>=2 dp[i][0]=(dp[i][0]+dp[i][0]+dp[i-1][0]); dp[i][1]=dp[i][1]+dp[i][1]+dp[i-2][0] dp[i][2]=(dp[i][2]+dp[i][2]+dp[i+2][2]+dp[i+2][1]+dp[i-2][2]) for i==0 dp[0][0]=(dp[0][0]+dp[0][0]+1) dp[0][1]=0; dp[0][2]=(dp[0][2]+dp[0][2]+dp[2][1]+dp[2][2]) for i==1 dp[1][0]=(dp[0][0]+dp[1][0]); dp[1][1]=dp[1][1]+dp[1][1]+1; dp[1][2]=(dp[1][2]+dp[1][2]+dp[3][2]+dp[3][1]+dp[2][2]); can anyone explain why this is wrong
•  » » 14 months ago, # ^ |   0 And what is the result? sum of all dp[][] values?
•  » » » 14 months ago, # ^ |   0 yes
•  » » 14 months ago, # ^ |   +3 There is one main thing you are missing in this transition in $i==0$ case,$dp[0][2]=(dp[0][2]+dp[0][2]+dp[2][1]+dp[2][2])$Now, $dp[2][2]$ will store count of sequences ending at 2 and which are of the alternating form. There are two such sequences,1. 0 2 0 2 0 2....2. 0 1 2 4 2 4 2....But, you can append 0 to only the first type not to the second one by the definition of Mex-Correct sequence.You will have to change these transitions in $i>0$ cases as well because of this logic.One thing you can do is to make 2 separate $dp$ arrays(or increase the second dimension) to store these two types of alternating sequences.
•  » » » 14 months ago, # ^ |   +3 ohh now i understood what i was missing thanks for your reply Enigma20:).
•  » » » » 14 months ago, # ^ |   0 UPD: Finally got AC by using another dp2[n+1][2] this is to calculate alternating sequences of type 3.where first is the ending number of sequence and second specifies whether the ending number is increasing number of alternating sequence or decreasing number of alternating sequence.for example 1. 0 2 0 2 0 2.... 2. 0 1 2 4 2 4 2....here 2 is increasing number in alternation for sequence of type 1 and 2 is decreasing number in alternation for sequence of type 2Finally AC
 » 14 months ago, # | ← Rev. 3 →   0 How to solve E?EDIT: I tried it to some extent but couldn't end up with a correct solution. My main observation was that a cell will be only + if there are only two or one way to exit this cell for example x,y is a free cell and x+1,y is blocked and x-1,y is blocked so this cell can be a '+' provided it leads to the labso I ran a bfs starting from the lab. I enter only those cell which has only two ways or 1 way to exit it and I turn it into '+'.But this solution is giving WA!is my observation flawed or am I missing anything?
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 you should compare the number of neighbors that is '+' or 'L' with the number of exit this cell, not just check the number of exit this, e.g.#...L....although a[2][3] has three exit directions, it is '+'
 » 14 months ago, # | ← Rev. 3 →   0 can anybody help me? In problem D I have a solution based on dp[i][j] the number of sub sequece that i is the last number of Mex-correct subsequece and j is a type of Mex-correct (if j = 0 then mex of subsequece must be i — 1 otherwise of j = 1 then mex shuld be i + 1).thus we have dp[i][0] = 2 * dp[i][0] + dp[i-2][1] and dp[i][1] = 2 * dp[i][1] + dp[i-1][1] + dp[i+2][0] but I got WA.here is code
•  » » 14 months ago, # ^ |   0 check sequence "0 2 0" answer should be 5
•  » » » 14 months ago, # ^ |   0 ok it's 5
 » 14 months ago, # |   +6 Why Ratings are still not updated?
•  » » 14 months ago, # ^ |   0 Cause sys tests were still pending
•  » » » 14 months ago, # ^ |   +2 I think it's the most late rating update ever
 » 14 months ago, # |   +8 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 14 months ago, # |   0 Today is 2021，1202, which is a palindrome. we should celebrate it. wait for 20：21 in your time zone and see what will happen.(maybe a rating update)
•  » » 14 months ago, # ^ |   +1 Well it's 22:21 actually
 » 14 months ago, # |   +4 What has happened to Codeforces? The system testing is not over yet?
 » 14 months ago, # |   0 During contest time I submitted my code and it was accepted on the second attempt. But after system testing I found WA because of TLE in the 7th test case. I found no reason behind it. Plz help me. Here is my submission link https://codeforces.com/contest/1613/submission/137660678
•  » » 14 months ago, # ^ |   0 Your code only passed weak pretests during the contest time. Then there was a 12 hours long hacking stage and people could freely submit their own stronger testcases (also known as hacks) to exploit various bugs and vulnerabilities in incorrect solutions. The final system test included all these extra testcases. Your solution failed to pass them.I suggest to look at the input data of the 7th test case and try to figure out what exactly killed your solution.
•  » » 14 months ago, # ^ | ← Rev. 4 →   0 Imagine a test case of $t = 10^4$ and in each case $p1 = 1, p2 = 1000000$. In this case your code will run $10^6 . 10^4 = 10^{10}$
 » 14 months ago, # | ← Rev. 2 →   +18 Ok so carrot is predicting +79 and i need +81 rating for cm. I dont think my copium can handle this.
•  » » 14 months ago, # ^ |   0 What is carrot? I also want to predict my rating
•  » » » 14 months ago, # ^ |   +8 its an extention, check your prefered browser's extension store and search for it
•  » » 14 months ago, # ^ |   +3 In this dire moment, I have nothing to say to you, except hello.
•  » » » 14 months ago, # ^ |   0 carrot was predicting +35 for you(before this thing)
•  » » 14 months ago, # ^ |   +8 :D
•  » » » 14 months ago, # ^ |   0 Lol, both you and Naman got it)) Congrats
 » 14 months ago, # |   0 Will anyone please help me that why my solution for the question is getting tle in the 16th testcase. First I thought that in my code there is some infinite loop. So, to check it I changed my code specifically for case 1)m=1 2)n=1 and since, in this we only have to go in both directions from 'L'= lab until we encounter '#' or we have reached to the end of string. So I Directly use the while loop for that and still, I am getting tle. Its not clear to me whats the problem is. Link to my code.
•  » » 14 months ago, # ^ | ← Rev. 3 →   +4 Just use '\n' instead of $endl$.And a good advice for the future, use $endl$ only in the case you want a flush, otherwise use \n
•  » » » 14 months ago, # ^ |   0 yuppp! Thanks for your help.
 » 14 months ago, # |   +11 Is this Rated?
 » 14 months ago, # |   0 Rating is not updated yet. Moreover, previous contest ratings also has been rolled back. What's going on?
•  » » 14 months ago, # ^ |   +8 Maybe someone in the headquarters was sleepy and instead of clicking on rating update he clicked on rating roll back . ( Not trying to disrespect anyone )
•  » » 14 months ago, # ^ |   +17 You have been around long enough to know the drill. The only missing thing is a banner at the top of the site with a notification about temporary rating rollbacks.Looks like the plagiarism checks for the earlier Deltix round are almost complete and the scoreboard will be finalized soon with recalculated ratings. And then preliminary rating updates for the current round will become available too (followed by a rollback and finalization at a later date).
 » 14 months ago, # |   +2 Rating ??
 » 14 months ago, # |   +3 Kindly Update Ratings
•  » » 14 months ago, # ^ |   +22 Mike: and I took it personally.
 » 14 months ago, # |   0 Div. 1 participants got a delta rating as well xD
 » 14 months ago, # |   +50 Educational Codeforces Round [Rated for Div1 + Div2]
•  » » 14 months ago, # ^ | ← Rev. 2 →   -8 It was a glitch . :)
 » 14 months ago, # |   +8 Hurray! new rating!
 » 14 months ago, # |   0 I guess there's something wrong with rating changes cause I should've got +147 delta according to cf-predictor but only got +71
•  » » 14 months ago, # ^ |   +10 as you said , it is "predictor"
•  » » » 14 months ago, # ^ |   0 looks like this trouble is not only mine so I believe predictor works fine with possible plus minus 15 delta diff
 » 14 months ago, # |   0 Is Mike high today?
•  » » 14 months ago, # ^ |   +1 He just pressed some wrong buttons ig. Come on, everyone loves to play with buttons
 » 14 months ago, # |   +9 Why aren't the problems still allotted to their difficulty rating ?
 » 12 months ago, # |   0 Recently i came across the problem "Long Comparison" . Since i am new to competitive programming , i am solving more new questions to build my problem solving ability . Now when i submitted solution to this problem with my own approach , it gave "Run Time Error" with "Exit Code 3" . Can anybody tell me what is going wrong with the approach which i have submitted .Problem : 1613A - Long Comparison My Submission : 146344211Please give your precious advice .