By awoo, history, 4 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 and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Hey, Codeforces!

We are pleased to announce the second “Hello Muscat 2023” ICPC programming bootcamp, the continuation of the “Hello” bootcamp series, organised by Harbour.Space University, in collaboration with PhazeRo, Gutech, UK Oman Digital Club, Leagues of Code, Gutech CS Club and Codeforces!

Quite exciting, isn’t it? Now it's time for you to dive deeper into the competitive programming world with the 8 days intensive Hello Muscat 2023. It will take place in Muscat, Oman and online from March 8th to March 16th, 2023, both participation formats are available. As always, we can’t wait to see you there to learn, practice and compete on the international stage, smoothing your road towards the joined World Finals 2022 and 2023 in Egypt!

Our coaching line-up combines talent and experience, featuring ICPC world champions winners and finalists, as well as legendary names from the field of competitive programming: Mike Mirzayanov MikeMirzayanov, Yahor Dubovik 244mhq, Artem Plotkin Rox, Maksym Oboznyi MaksymOboznyi and Nikolay Budin budalnik.

The Bootcamp will be split into three divisions:

• Division A. Division A will be a mirror of the Petrozavodsk Programming Camp. Suitable for teams who already qualified for the world finals ICPC or are aiming that high.
• Division B. Designed to help teams prepare for the next season of ICPC regional competitions. Appropriate as an introduction for teams and students just getting their foot in the door of the world of ICPC and competitive programming competitions in general.
• Division C. Designed for newcomers to the world of ICPC competitive programming.

Types of participation: On-Site and Online

We believe that participation in our Bootcamp should be accessible by all teams wherever they are and that is why we made onsite and online types of participation. 20% Early Bird Discount is offered to universities and participants who register and pay before Jan 31st 2023.

• On-site:

Price: 1500 € — 1200 €

What is included: training, contests, access to the recordings of the lectures, accommodation for 9 nights in a 4 star hotel Mysk, breakfast and lunch, transfer from hotel to venue every day, leisure, entertainment and welcome pack.

• Online:

Price: 100 € — 80 €

What is included: training, contests, access to the recordings of the lectures.

Good luck with the round!

UPD: Editorial is out

• +89

 » 4 weeks ago, # |   0 Best of luck everyone . As a participant I am going to give my best in this contest.
 » 4 weeks ago, # |   0 Good luck everyone. Hope i can solve problem C
•  » » 4 weeks ago, # ^ |   +39 I didn't solve the problem C
•  » » » 4 weeks ago, # ^ |   -6 did you solve b?
•  » » » » 4 weeks ago, # ^ |   0 Yes! I solved it when there were 5 minutes left before the end of the competition.
•  » » » » » 4 weeks ago, # ^ |   +2 B was quite hard for a Div 2 B problem. Man it's really hard to improve in competitive programming, I feel like im stuck. Being stupid also doesn't help.
•  » » » » » » 4 weeks ago, # ^ |   0 Only two words: More Practice
•  » » » » » » » 4 weeks ago, # ^ |   0 Only one word: repeat
•  » » » » » » » » 4 weeks ago, # ^ |   0 Thanks for the words i guess. Planning to reach 1700 by the end of the year is it realistic if I work hard?
•  » » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Thanks for the words i guess. Planning to reach 1700 by the end of the year is it realistic if I work hard?
•  » » » » » » » » 4 weeks ago, # ^ |   -8 Idk but one thing I would say Enjoy the process!
•  » » » » » » » » 4 weeks ago, # ^ |   0 This is a good goal. I would also like to go up to 1600 a year. And I understand that this is real if you regularly work and solve problems not only that are easy for you, but also that are higher than your current level, in order to learn how to solve them.
 » 4 weeks ago, # |   0 Hope to get good rank at contest which I am not able to do so in previous rounds
•  » » 4 weeks ago, # ^ |   +6 Not able get good rank again
 » 4 weeks ago, # | ← Rev. 5 →   -53 ;)
 » 4 weeks ago, # |   -13 I am sure everyone will be successful in this competition. You can! Good luck!
•  » » 4 weeks ago, # ^ |   -21 I also wish everyone that no one could hack their solution! I wish everyone +100 or more than 100 to the rating of everyone!
•  » » » 4 weeks ago, # ^ |   -23 Mathematically its not possible because if you want to get + rating changes some one has to get the negative.
•  » » » » 4 weeks ago, # ^ |   -9 BiG BrAiN
 » 4 weeks ago, # | ← Rev. 2 →   +2 i still remember awoo's favourite problem
 » 4 weeks ago, # |   0 Good luck to everyone!!! (I hope that I can solve at least one problem :>)
 » 4 weeks ago, # |   +35 Wow, I'm back after a year and comments are as cringe as ever. Joining in.
 » 4 weeks ago, # |   +26 Good luck everyone . Hope I can solve at least one problem.
•  » » 4 weeks ago, # ^ |   +17 oh c'mon, you are a lgm. Just solve all :)
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   -26 .
•  » » » » 4 weeks ago, # ^ |   +11 I think that was a joke...
•  » » » » » 4 weeks ago, # ^ |   0 yes..
•  » » » » » 4 weeks ago, # ^ |   0 oh thanks
 » 4 weeks ago, # |   +65
•  » » 4 weeks ago, # ^ |   0 😮
 » 4 weeks ago, # |   0 good luck have fun
 » 4 weeks ago, # | ← Rev. 2 →   0 Hope to become cyan, and good luck to everyone in this contest.
 » 4 weeks ago, # |   -6 hmm, why I has the conbutrition? can anyone explain??
•  » » 4 weeks ago, # ^ |   0 You might have gotten an upvote.
 » 4 weeks ago, # |   -9 This Contest is very beauty-full
 » 4 weeks ago, # |   -39 me after solving a&b :
•  » » 4 weeks ago, # ^ |   0 true :) couldn't even understand what's happing with c :/
 » 4 weeks ago, # |   +6 Classic Mathforces
•  » » 4 weeks ago, # ^ |   0 not mathforces, just constructiveforces
 » 4 weeks ago, # |   0 oh yes I saved the previous non-blue profile pic somewhere else and I am getting to use it now
•  » » 4 weeks ago, # ^ |   0 I should find a matching green one aswell, given the amount of times I have dropped right after reaching cyan T-T
 » 4 weeks ago, # |   +7 Any proof for B?
•  » » 4 weeks ago, # ^ |   +54 Pretty straightforward after trying to solve for a 1d array instead of matrix
•  » » » 4 weeks ago, # ^ |   0 Thanks man! I wrote the solution after so many hit and trials. I need to improve my observation skills for such problems
•  » » » 4 weeks ago, # ^ |   +5 Thanks man....it was really helpful....I complicated this problem unnecessarily
•  » » » 4 weeks ago, # ^ |   0 lol i did a snail
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 There are $n^2-1$ possible differences $(1\dots n^2-1)$. And the chain $1, n^2, 2, n^2-1, \dots, \left\lfloor\dfrac{n^2}{2}\right\rfloor, \left\lfloor\dfrac{n^2}{2}\right\rfloor+1$ (chain ending correct modulo parity), contains all differences and has $n^2$ terms, for $n^2-1$ differences.
•  » » » 4 weeks ago, # ^ |   +1 nice profile
•  » » 4 weeks ago, # ^ |   0 I code brute force as the max difference can be (n*n-1). Try to create all differences from (n*n-1) to 1.
•  » » 10 days ago, # ^ |   0 If I have understood it correctly, the proof is:Let's solve this problem for a 1D case, then we will extend it to 2D. Say, n = 3. So, the values are: 1, 2, 3, 4, 5, 6, 7, 8, 9 (from 1 to n*n) Here, the minimum value is 1 and the maximum value is 9, so, no matter what, the absolute difference will be at most 8 (when |9-1|) and the minimum absolute difference will be 1 (when |9-8|), and the other values will be in between. Our target is to maximize the total various types of such absolute differences. If we order the numbers in the following way: 9, 1, 8, 2, 7, 3, 6, 4, 5 then the target can be maximized. As in this case we are getting these all kinds of absolute differences we could ever get from them taking side-adjacent values. That are: 8 (i.e, |9-1|), 7 (i.e, |8-1|), 6 (i.e, |8-2|), ..., 1 (i.e, |5-4|)Two numbers in an array are side-adjacent when they are positioned one after another either in the same row or in the same column. For example, for a 5x5 matrix, the indices are as follows: (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) (2, 1) (2, 2) (2, 3) (2, 4) (2, 5) (3, 1) (3, 2) (3, 3) (3, 4) (3, 5) (4, 1) (4, 2) (4, 3) (4, 4) (4, 5) (5, 1) (5, 2) (5, 3) (5, 4) (5, 5) So, the side adjacent to position (3, 3) are (3, 2), (3, 4), (2, 3), and (4, 3) positions. We have to find all possible side-adjacent positions for each position and take absolute differences of corresponding values and count how many unique absolute difference values we get. And obviously, we have to find an arrangement in such a way, that the number of possible such values maximizes.Going back to 3x3 cases (for better manageability), a deterministic solution is to arrange the 1D array (which maximizes the result in 1D case, i.e: 9, 1, 8, 2, 7, 3, 6, 4, 5), in a zig-zag fashion. So, the solution is: 9, 1, 8 3, 7, 2 6, 4, 5 which follows the following pattern: --->---- | v ---<---- | v ---->--- This will work because the zig-zag pattern is nothing but the same 1D array (just in an entangled fashion). But the values which were side-adjacent in 1D cases are still side adjacent in 2D cases (if we just follow this path). Obviously, as it is now in 2D, there will be more side-adjacent pairs that are not shown in the path (each position can have at most 4 side-adjacent positions, namely: left, right, up and down position), but we simply don't care for them, as we already have maximized the result and the other side-adjacent values will just create duplicate absolute difference values which we already found while traversing the path.
 » 4 weeks ago, # |   +55 seriously, what is the point of problems like B, where you have to find some stupid pattern on a grid?
•  » » 4 weeks ago, # ^ |   +5 I wasted time thinking that question is asking for only border elements.
•  » » 4 weeks ago, # ^ |   +3 Why do you think that is a silly thing to do? It trains observational skills. Regardless, its not like patterns in grids of numbers are a meaningless or trivial thing to study. There are a ton of problems that can be represented as patterns in grids of numbers.. Doing regression in data analysis for example.
•  » » 4 weeks ago, # ^ |   0 its not stupid instead you can find the logic behind the pattern. though i wasn't able to solve the problem i found its quite intuitive after contest... since there will be in total 2*(n*(n-1)) adjacency relationship and also maximum diff between any two adjacent could be n*n-1 < 2*(n*(n-1)), we can always generate pattern such that from 1 to n*n-1 all diff got generated. now take the maximum diff i.e., n*n-1 we cannot make it a adjacent diff between two big values so adjacent relationship can be between big and small values, like n*n and 1, 1 and n*n-1 like that. If we solve that for 1D array of length n^2 we have total n^2-1 adjacency relation so just making a spiral out of it to make the n^2 length array to a n x n matrix would suffice.
•  » » 4 weeks ago, # ^ |   0 Yes i did it using Spiral Traversal :)
 » 4 weeks ago, # |   0 Too much penalty >:( and I thought the condition in problem B is $a_i + a_j$ instead of $|a_i - a_j|$.
•  » » 4 weeks ago, # ^ |   0 how did you solved B?
•  » » » 4 weeks ago, # ^ |   +4 There's at most Unable to parse markup [type=CF_MATHJAX] distinct value so we started from Unable to parse markup [type=CF_MATHJAX] and apply it to a zig zag path on the matrix.
 » 4 weeks ago, # |   0 so my approach for problem C was since the nth player can at max have n wins . so a win against him would increase my chances of having a lesser rank . i tried defeating maximum players from the end. and then sort the number of wins for each player in decreasing order and decide my rank why wouldn't this logic work ?here's my submission https://codeforces.com/contest/1783/submission/188487469
•  » » 4 weeks ago, # ^ |   +1 See this testcase: 1 3 5 2 3 5 
•  » » » 4 weeks ago, # ^ |   0 ufff my bad . thanks for the help.
•  » » 4 weeks ago, # ^ |   0 Even i tried a similar approach. 1. Try defeating players from last. 2. Sort and try to defeat as many as possible. Then print the minimum of the two ranks. But it failed on TC 2.
•  » » 4 weeks ago, # ^ |   0 I was also thinking the same but this will not work because we are concerned more about the total number of wins by "me".even if we win against last person but our time left is 0, our total win is only 1 so players before last one (like p=2 or 3) can win and our rank will fall.
 » 4 weeks ago, # |   +30 People asked for binary search, dp, segment tree problems aand... here we ended up
•  » » 4 weeks ago, # ^ |   +8 I think C was a beautiful problem , though B was little annoying to me
•  » » 4 weeks ago, # ^ |   +23 SpoilerD is a dp problem. C can be solved with binary search (or can be solved without it). So, what's the matter?
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 I didn't mean that, C, D, E are very much algorithmic problems, but many of my friends complained about them being too hard ( I think they are easy)
•  » » » 4 weeks ago, # ^ |   0 You need some testers for educational round too lol. There are so many ups (and lots of downs) in the quality of these contests
•  » » » 4 weeks ago, # ^ |   0 how to solve c?
•  » » » » 4 weeks ago, # ^ |   +13 SpoilerThe $i$-th opponent has either $i-1$ or $i$ wins, and the $i$-th opponent will never be better than $(i+1)$-th. So, if we want to get at least the $k$-th place, we need to be not worse than the opponent $(n+1-k)$. That means, we either win $(n+1-k)$ games, or we win $(n-k)$ games, but one of our wins is against that opponent. In the first case, just win these games against the opponents we need to prepare the least amount of time (so, we need $(n+1-k)$ minimums from the array $a$). The second case is similar — we need the time to prepare to the $(n+1-k)$-th opponent, and $(n-k-1)$ other opponents with the minimum preparation time.Now we can either iterate on the place we take and compute these values efficiently with prefix sums, or do binary search on $k$.
•  » » » 4 weeks ago, # ^ |   0 i tried binary search But not Know how to write function correctly Plzz share some hint
•  » » 4 weeks ago, # ^ |   0 Most of the good contests I participated in had at least one of them
 » 4 weeks ago, # |   +28 Problem B was annoying :(
 » 4 weeks ago, # |   +1 How to solve B?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 some pattern based try for n = 4 it will be like1->16->2->1513->4->14->35->12->6->119->8->10->7
•  » » » 4 weeks ago, # ^ |   0 how to solve c?
•  » » » » 4 weeks ago, # ^ | ← Rev. 3 →   +3 You can solve C by sorting the array and finding the maximum number of people you can defeat with the given m, let's denote it by wins.1) if wins = 0 or wins = n , then your position will be n-wins + 1 (last or first).2) If wins >=1 and wins <= n-1, if you could defeat person with a [wins] index (his total wins are equal to wins or wins+1), your position would become one better, so the answer would be n-wins, otherwise n-wins+1. (You could go 1 position higher by having total wins equal to that person.) 188489483
•  » » » 4 weeks ago, # ^ |   0 Thanks I overcomplicated it too much
•  » » » 4 weeks ago, # ^ |   0 how did you come up with the pattern?
 » 4 weeks ago, # |   +42 As always Educational rounds are worst.
•  » » 4 weeks ago, # ^ |   0 The whole point of them is to learn (standard) algorithms, not to solve interesting tasks. And I think that $A$, $B$, $F$ and $G$ are great for that ( educational ) matter.
•  » » » 4 weeks ago, # ^ |   +2 what does one learn from B?
•  » » » » 4 weeks ago, # ^ |   0 What Wind_Eagle has said before, how to prove theorems in mathematics. Asking for a construction in CP means that one cannot randomly guess the answer, but must be aware of the proof. And I think it is an okay problem, requiring some basic implementation which is, in fact, useful. I understand that many find it annoying though, which doesn't necessarily make it bad.
•  » » » » » 4 weeks ago, # ^ |   0 Asking for a construction in CP means that one cannot randomly guess the answer, but must be aware of the proofInfact the reverse is the case, it is very easy to guess the pattern for problems like this without knowing the proof. I'm pretty sure for this problem, people just randomly guessed patterns that gave $n^2 - 1$ as difference, and only a few actually proved the patterns or derived it mathematically.
 » 4 weeks ago, # |   +1 is problem c Segtree or vector of priority queues since ai<=1000 or I completely overcomplicated ?
•  » » 4 weeks ago, # ^ |   +5 It has to be on Binary Search but this mf B wasted an hour and my mind went blank coz of that so couldn't even think properly about C
•  » » » 4 weeks ago, # ^ |   0 same
•  » » 4 weeks ago, # ^ |   +8 Key observation is because each player plays each other the other players will have 1, 2, 3, 4... wins... If you can beat the player with exactly 1 more win than you while still maintaining the optimal number of wins than your place is (n-wins+2), else it is n-wins+1
 » 4 weeks ago, # |   +21 GOODBYE EXPERT!! These hit and trial B's are the worst
 » 4 weeks ago, # |   +35 Rounds like these make me wish there was an un-register button on Codeforces just like on Atcoder. Wtf was problem B???
 » 4 weeks ago, # | ← Rev. 2 →   0 How to solve D? Spent most of my remaining time trying to solve it...
•  » » 4 weeks ago, # ^ |   0 Try thinking about $dp_{i,s} := \textrm{the number of possible suffixes of the array starting at } i\textrm{ having } a_{i+1} \textrm{ equal to } s$.The transition will be something like $dp_{i,s} = dp_{i+1,a_{i+1}+s} + dp_{i+1, a_{i+1}-s}$ depending on whether $s = 0$.
•  » » » 4 weeks ago, # ^ |   0 are we trying to find how many different types of sum are possible at end position after applying all operations. eg. if array is a1,a2,a3,a4, at max answer can 4 with 4 different sum a4+a3+a2,a4+a3-a2,a4-a3+a2,a4-a3-a2 possible at the last position?
•  » » » 4 weeks ago, # ^ |   0 Bro I did same as yours appraoch but getting TLE on test 18, can you please see and help me how to avoid it. Link to solution : Solution
•  » » » » 4 weeks ago, # ^ |   0 I would suggest doing it iterative instead of recursive. Moreover, you have an extra dimension that you can skip (see the explanation of Saul)
•  » » » » » 4 weeks ago, # ^ |   0 Yup now got AC by iterative Code : Iterative SolutionThank you Saul-Goodman
 » 4 weeks ago, # |   0 Can we solve C using Binary search?
•  » » 4 weeks ago, # ^ |   0 I too want to know this, I got an intuition but couldn't mold it in any kind of solution.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I did it using binary search on the number of people we rank at least as low as. So to beat $k$ people, I pick the $k$ weakest opponents (in terms of $a_i$), if their sum of $a_i$ is less than $m$, we can rank $n-k+1$, there's also another small detail but this is mostly the idea.
•  » » 4 weeks ago, # ^ | ← Rev. 4 →   +10 Yes, we can binary search answer. When we check mid, we know that we can't lost the n — mid + 1 opponent. Let t = n — mid + 1. So we do it greedily to beat as many opponent as possible. Now there are 2 case : If the number we can beat >= t, we always win because player t can win at most t games. Else(number we can beat = t — 1) if we can beat player t, we can win too because now t win t — 1 games. 188457382
•  » » 4 weeks ago, # ^ |   0 Yes.You can see my submission.
 » 4 weeks ago, # |   0 Did we have to check only from prefixes and suffixes in the C problem? Like we try to win against only suffixes or only prefixes or some prefixes and suffixes combined? (for the sorted array)
 » 4 weeks ago, # |   0 Is D even DP ? 💀
•  » » 4 weeks ago, # ^ |   +4 Yes
 » 4 weeks ago, # | ← Rev. 7 →   +23 A: If min==max no solution, else {min, max, (anything)} is a solution.B:[1, n^2, 2, n^2-1, 3, n^2-2...] arranged along any path of the matrixC:Sort the array and you will get an almost-best solution. But it needs an extra check to get the best solution. When you've checked first k opponents with least time to prepare, look for whether you've prepared for the opponent with index k+1. If not, check whether you can remove a prepartion and prepare for (k+1)th opponent.D:Consider for every possible value of sum(ai*sign_i), where sign_i = 1 or -1. There are at most 180000 different values, and run dp for an O(n*A^2) solution.E:Seemingly easy inequality problem, but naive implementation will get TLE. For certain k, if all multiples of k are not in any range [bi,ai-1], then k is good. We need a segment tree to check all values of [1,n] in O(n*log(n)).
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +5 [E] You don't need a segment tree. Just do range sum using prefix arrays and iterate over all multiples of k for every k.
•  » » » 4 weeks ago, # ^ |   +5 Ohhhhh I missed itI just thought about "How to set a range in O(log(n))" and implemented with segment tree
•  » » 4 weeks ago, # ^ |   0 Do I check whether I can prepare for the k+1th opponent in the sorted array or in the orignal array?
•  » » » 4 weeks ago, # ^ |   0 Original
•  » » » » 4 weeks ago, # ^ |   0 Please correct me if I am wrong.The logic is: If I can beat any k opponents it means I will rank alongside the k+1th person in the rankings right? So I check if I can add a preparation for the next highest opponent which I have not prepared for and remove prep for the lowest index which I have prepared for so as to beat k+1th opponent right? Such that my number of preparations always remain the same so I beat the opponent removed on total number of wins anyway.
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 If you don't prepare at all, the wins of each other player is their index (1-indexed).In fact, if the number of preparations is fixed at k, you win k matches, and for each other players with index i, their number of wins will be i-1 (you prepared for it) or i (otherwise). Notice that if i < k+1, then i<=k and i-1<=k, which means whether you prepare or not, the number of wins of i-th player cannot be larger than you. It's similar for i>k+1 (their number of wins will be always larger). So only i=k+1 will matter.
•  » » » » » » 4 weeks ago, # ^ |   0 Ohh I understand it now. Thank you very much!
 » 4 weeks ago, # |   0 Worst contest for me!
•  » » 4 weeks ago, # ^ |   -6 B is easy than usual
 » 4 weeks ago, # |   +9 Through this edu round,I know a fact that I'm a totally trash.Maybe I can never be an expert.
 » 4 weeks ago, # |   +9 Very surprised by number of B and and C solves, B confused me while C seemed like a trivial sorting problem
•  » » 4 weeks ago, # ^ |   0 Likewise
 » 4 weeks ago, # |   -6 Worst B ever. Period.
•  » » 4 weeks ago, # ^ |   +13 I didn't solve B, but I liked it. It tests one's observation ($n^2-1$ upper bound) and simplification (solve it for 1d array first) skills.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 That is because you didn't find a key idea of it,so your code was very long.If you found that $1 \sim n^2-1$ must be able to express,you could know that $n^2$ must be adjacent to $1$,easily we could expand it into an easy solution.
 » 4 weeks ago, # |   +4 How to approach problems like B? I solved it by randomly guessing stuff.
•  » » 4 weeks ago, # ^ |   +1 Have you ever solved tasks from mathematical olympiads?
•  » » » 4 weeks ago, # ^ |   0 No. How would that be useful to tackle such problems?
•  » » » » 4 weeks ago, # ^ |   0 These problems aren't random guessing, it's just math.
•  » » » » » 4 weeks ago, # ^ |   +15 how exactly do you approach B mathematically?
•  » » » » » » 4 weeks ago, # ^ |   -20 This is the type of question like "how mathematicans prove theorems" or even "how tourist solve CP tasks".
•  » » » » » » » 4 weeks ago, # ^ |   -39 just noticed your round is the next cf round, rofl. with this type of shitty opinions of yours, I pity whoever participates in that round.
•  » » » » » » » » 4 weeks ago, # ^ |   -16 True, He better not include these kind of problems. B pissed me off and I left contest within 20 minutes to play CSGO
•  » » » » » » 4 weeks ago, # ^ |   +87 The process "find the strictest lower/upper bound for the answer and then show that it's reachable" is common in math competitions (not only that, it also frequently appears in algorithm correctness proofs). This is the first step to the solution: it's quite easy to see that the answer is bounded by $n^2-1$ (all differences are positive, and the maximum difference cannot be greater than $n^2-1$).Then, to actually find the way to reach this bound, you need to try some common techniques to solve problems. You can take a look at MikeMirzayanov's post on these techniques. From these, we have already used "Bold Hypothesis". The "From Specific to General" (with a twist, since we actually change the problem partially instead of just simplifying it) may help us as well: 2D sounds too complex, what if the problem is in 1D instead? This case sounds way stricter: we have only $n-1$ adjacent pairs, and all of them should be distinct. Believe it or not, but having stricter constraints actually makes the solution easier, inventing a construction on one-dimensional array is not that hard. Spoiler$[m, 1, m-1, 2, m-2, \dots]$, where $m$ is the maximum valueAll that's left is to convert the 1D solution to 2D, which means that we should go through the matrix visiting all its cells, which is a common math/programming problem. SpoilerThere are many ways to do this, one of the most well-known is to make a "snake" path: traverse the first row from left to right, go down, traverse the second row from right to left, go down, traverse the next row from left to right, and so on. Other solutions also exist, like making a "spiral" path.Note that our process of solving the problem used something like "try to apply a concept and then see if it works" multiple times, and this is very common in both math problems and harder programming problems. So getting familiar with these concepts and methods will not only help you solve some constructive and/or ad-hoc problems, but also the more difficult ones, where you have to mix it with some standard data structures and algorithms.
•  » » » » » » » » 4 weeks ago, # ^ |   0 I had to tinker around with some randomly put together constructions till I came across the solution. Proving it seemed easy once it was clear. Definitely not appropriate for problem B, but it's an edu round and technically the order doesn't matter, so whatever, ig.
•  » » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 My opinion on the quality of Problem B has changed after reading this commentThanks
•  » » » » » 4 weeks ago, # ^ |   +1 what's math in that?
•  » » » » » » 4 weeks ago, # ^ |   0 Well it was not total math problem, but yes there was a quite neet observation, that is the maximum ans is always n^2 — 1, from there you can make the matrix multiple ways.
•  » » » » » » » 4 weeks ago, # ^ |   0 I got that observation but still it felt like massive hit and trial to me
•  » » » » » 4 weeks ago, # ^ |   +8 But I think, here intended solution was random guessing!:(
•  » » 4 weeks ago, # ^ |   0 Thats how you solve it, xD
 » 4 weeks ago, # |   +13 After failing to submit E in the last 10 seconds the last time(Jan 6), this time I found the solution of E in the last 5 minutes and got AC just 5 minutes after the contest ended... [Sad]
 » 4 weeks ago, # |   -22 B spoily my mood and I gave up after 20 minutes
 » 4 weeks ago, # | ← Rev. 2 →   0 Hi there! I try to help people by upsolving contest problems and post them after the contest on my channel — https://www.youtube.com/@grindcoding . I have been trying hard to help people by solving daily challenges across platforms and also the contest problems. Please provide me suggestions on what I can improve. Have uploaded problem C of this round already and would upload others as required by anyone of you. Any advice is appreciated :).P.S. not the channel who promote leaking solutions during live contests. I know it provides better growth with the huge amount of cheaters, but I understand it's detrimental and against the overall spirit :) happy coding :) Soon would be making a good data structures and algorithms course to help beginners (though not a pro myself but want to contribute as I grow).
 » 4 weeks ago, # |   +1 A tough contest to me :(((problem B needs a lot of observation :((((
 » 4 weeks ago, # |   0 Any hints to approach problem 'C'?Really reject stopping solving problems regularly T_T SpoilerI reached to the basic point where all i need is sort the array get the max sum <= m then nearlly this our final total wins.., then what?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +6 Hint 1: Without considering your training, each other player has a unique amount of winsHint 2: What 1 other player's ranking can you affect that could also improve your ranking?
•  » » 4 weeks ago, # ^ |   0 Hi! yes! there's one case you need to consider, can you defeat the person who has wins==wins_you_have+1, I have uploaded a editorial video on my channel you can check this here- https://www.youtube.com/@grindcoding
•  » » 4 weeks ago, # ^ |   0 Let's say I want to reach a specific position Xth, what's needed? Once you've figured that, bold hintbinary search ^^
 » 4 weeks ago, # |   0 got stuck with b and no time left to think about c .. uff time to go back to green
 » 4 weeks ago, # |   -19 Participate in post contest discussionwww.peer2peer.social
 » 4 weeks ago, # |   +9 Wow, I really enjoyed the problemset! Problem F is just otherworldly *_*Huge thanks to the developers of the contest! <3
 » 4 weeks ago, # |   0 Nowadays the problems in the contest are not properly sorted in the order of their difficulty. Sometimes the problem B is made very hard, whereas sometimes it is made as easy as A, and in this case the C problem is made very very Hard.It would be nice if the difficulty order would be made moderately increasing.
•  » » 4 weeks ago, # ^ |   0 problem C isn't hard. it's just sorting and a simple observation.
 » 4 weeks ago, # |   0 Welp this was a waste of time.
 » 4 weeks ago, # |   0 was anyone able to get the solution to E with $n√n$ time complexity?
•  » » 4 weeks ago, # ^ |   0 O(n*log(n)) is enough. You just need to check for eack 1<=k<=n, if any multiple of k is in range [bi,ai-1] for some i which ai>bi.
•  » » 4 weeks ago, # ^ |   0 it was hard but yes 188516731
 » 4 weeks ago, # | ← Rev. 2 →   +17 Tips for PythonIn Python, you can put negative indices in a list (A[-1] means A[len(A)-1]). This makes it easy to implement dynamic programming with negative indices. When the index can take values from -L to L, prepare a dp array of length at least 2*L+1. In this array, information on positive indices can be placed in the first half of the list, and negative indices in the second half ([0, 1, 2, 3, ..., L, ... , -L, ..., -3,-2,-1]).Source Code for D: mod = 998244353 n = int(input()) a = list(map(int, input().split())) dp = [0] * 2 * 10**5 dp[a[1]] = 1 for i in range(2, n): ndp = [0] * 2 * 10**5 for j in range(-90010, 90010): ndp[j + a[i]] += dp[j] if j != 0: ndp[j - a[i]] += dp[j] dp = [j % mod for j in ndp] print(sum(dp) % mod) 
 » 4 weeks ago, # |   0 188508171 Please show me a case where my submission for problem C get the wrong answer :((((
•  » » 4 weeks ago, # ^ |   +1 Can't understand vietnamese variable names...
•  » » » 4 weeks ago, # ^ |   0 Okay :((( Thank you a lot :(((( I just sort the array and an extra check to get the best solution for the k-th opponent :((( Sorry Because my code is just like a mess :((
•  » » 4 weeks ago, # ^ |   +5 Take a look at Ticket 16685 from CF Stress for a counter example.
•  » » » 4 weeks ago, # ^ |   0 Oh thanks alot :(
 » 4 weeks ago, # | ← Rev. 2 →   0 The hack channel for problem C is ridiculous. If I set t to 1 and n to 500000, it will show generator crashed, which means it is hard to hack it tle！！！！！！！！！！！！！！！
 » 4 weeks ago, # | ← Rev. 2 →   0 Quite an ambiguous definition+example of the side adjacency for problem B. In the 2x2 example almost any nonsense one may come up with yelds same answer. For example if you define side adjacent elements as "elements on the same matrix edge". After the clarification it gets better, but still there's a chance you keep solving the wrong task on impulse.Any ideas how this "insanely misinterpreted" problem can be solved by the way?Once again. Same task: find the most beautiful matrix, but the adjacency definition is:Two different matrix elements $a[i_1][j_1]$ and $a[i_2][j_2]$ are adjacent iff ($i_1 = i_2 = 1$ or $i_1 = i_2 = n$ or $j_1 = j_2 = 1$ or $j_1 = j_2 = n$) ?
•  » » 4 weeks ago, # ^ | ← Rev. 4 →   0 1 n 2 (n-1) 3 (n-2) 4 (n-3)Look at this like and all will be clear(first row of matrix)
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 Thanks, but that's the solution to the original problem, but doesn't seem like a solution to the problem I mention.I'm interested in filling these so that the size of the set made of absolute difference of any two elements from first row or last row or last column or first column has max size. * * * * * * * * * * * * * * * * * * * * * * * * 
 » 4 weeks ago, # |   0 can anyone tell me how to solve E?I Just know that for every a[i]>b[i],then check k is ok if and only if (a[i]+k-1)/k==(b[i]+k-1)/k (i.e. ceil(a[i]/k)==ceil(b[i]/k)). but this get TLE as expected. how to get a faster solution? i cant understand the solution in the front row
•  » » 4 weeks ago, # ^ |   +11 $\left \lceil{a[i]/k}\right \rceil \neq \left \lceil{b[i]/k}\right \rceil$ if and only if there exists a number divisible by $k$ in range $[b_{i}, a_{i}-1]$.Therefore, we can mark all numbers in this range (for example, by using a segtree) and for each $k$, check if there is a marked number divisible by $k$.
•  » » » 4 weeks ago, # ^ |   0 Thanks
 » 4 weeks ago, # |   0 In problem C, does NlogN pass? I didn't want to take a risk and made an O(n+maxA) solution.
•  » » 4 weeks ago, # ^ |   0 My n log n passed with 1500ms
 » 4 weeks ago, # |   0 can anyone help me understand in problem C if the test is 8 6 2 2 2 2 2 2 2 2 so if I win against the 8 and 6 and 4 so 1 1 win 2 2 win 3 3 win 4 3 win 5 5 win 6 5 win 7 7 win 8 7 win I 3 win so I should rank 3 why is the answer 5 I don't understand I got stuck in this problem for that
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +2 just because there are 4 people whose win count strictly larger than you (i.e.5,6,7,8),let the count called k. and the answer is k+1. I guess you misunderstood the computing method of the rank within this question.
•  » » » 4 weeks ago, # ^ |   +1 Ty I think so the solution is much easier than i think ಥ⁠‿⁠ಥ
•  » » » 4 weeks ago, # ^ |   0 Brooooooooo, will re-read question 10 times now while solving.
•  » » 4 weeks ago, # ^ |   0 Because rank is the no. of people with more wins than you + 1. Your win count is $3$ but $8$ and $7$ both have won $7$ and $6$ and $5$ both have won $4$, hence the no. of people with more wins than you is $4$. Therefore, your rank is $5$
•  » » » 4 weeks ago, # ^ |   0 Yeah i understand that they group people with the same win so that i should minimize the number of group
•  » » 4 weeks ago, # ^ |   +1 It's optimal to beat the any 2 players and the 4th player which results in 3 wins.Bracketed players are the ones we beat. So 2 2 2 [2] 2 2 [2 2] And then if we count the number of wins and also consider the players we lose to we get our answer. 1st player will have 0+1 wins 2nd player will have 1+1 wins 3rd player will have 2+1 wins... 4th player will have 3 wins 5th player will have 4+1 wins 6th player will have 5+1 wins... 7th player will have 6 wins 8th player will have 7 wins... We ourselves have 3 wins. Order looks something like this then P(i) = 1 2 3 4 Us 5 6 7 8 Wins: 1 2 3 3 [3] 5 6 6 7 Our rank is 5.
 » 4 weeks ago, # | ← Rev. 2 →   +1 BledDest Can anyone explain problem C?For this test case4 41 2 2 1Since we have 4 minutes I can defeat Opponent 1,2. But why in the explanation it is mentioned we can win against only opponent 1 and we have no time to prepare
•  » » 4 weeks ago, # ^ |   0 That's the 5th test case.
•  » » » 4 weeks ago, # ^ |   0 Oh my bad
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 If $m = 4$ and we prepare and win against opponents 2 and 3 and lose against 1 and 4. Don't we get 2nd place? As our opponent 4 has $3 + 1 = 4$ wins against our 2 wins. I must be missing something obvious.Edit: ok my confusion was to fail to understand that "min place" actually means best ranking and not worst ranking.
•  » » » 4 weeks ago, # ^ |   0 We can pick the following opponents. (Bracketed means picked) [1] 2 [2] [1] Which gives us 3 wins. Opponents will be ranked as follows: P(i) = 1 2 3 4 Us Wins: 0 2 2 3 [3] This results in first place.
 » 4 weeks ago, # |   0 I almost spent the same amount of time on B as I did on C and D combined. Seemed like I was solving some weird newspaper puzzle.
•  » » 4 weeks ago, # ^ |   0 How is B an 'edu' problem?
•  » » » 4 weeks ago, # ^ |   +15 I start to think that "edu" is not about learning, "edu" is about Harbour space, like , there are Pinely rounds, Polynomial Round, CodeTON Round etc.
•  » » » 4 weeks ago, # ^ |   +19 It is rarely a difference between EDU and classic rounds. EDU were immature rounds initially, with no score distributions and possibilities for hacking, but later classic rounds overcome simplification and become similar to EDU, without hacking almost, but still with different costs of problems (except newer Div.>2, which are simplified further and have no difference with EDU).
•  » » » 4 weeks ago, # ^ |   0 It's not a random guessing problem. Notice that the difference is between 1 and $n^2-1$, so naturally we first try to get them all. For $n^2-1$, $n^2$ and 1 need to be adjacent, then for $n^2-2$, either $n^2$ and $2$ or $n^2-1$ and $1$ need to be adjacent, .... It's quite easy to achieve that. If you know gray code, Z-order, or something like those, easier.
 » 4 weeks ago, # | ← Rev. 2 →   0 Solution of D(with explaination please)?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +2 you can refer to the tutorial videos on my channel -video editorial
 » 4 weeks ago, # |   +3 This was a perfectly good round, without any major errors. Why all the downvotes?
 » 4 weeks ago, # |   0 Though the binary search solution greatly simplified the task, was it actually required in C? I mean, apart from the edge case of losing to the winner and changing the required score, it was all greedy and sequential, right?
•  » » 4 weeks ago, # ^ |   +3 That's how I solved it. For loop
 » 4 weeks ago, # | ← Rev. 4 →   +8 There is interesting solution of E with Eratosphens sieve: It's a fact that upper bound of a[i] / k must be <= upper bound of b[i] / k for all i. So we need to check only pairs where a[i] > b[i]. You can increase every a[i] position by any big number (1e7 + 1 in my case) and decrease every b[i] position by 1. Then we get prefix sum of this array and iterate like in sieve. If any sum on prefix with length which divides k doesn't divide 1e7, it means that we found some b[i] with b[i] / k > a[i] / k. That's it: 188522674UPD: nevermind lol, it's basic solution
 » 4 weeks ago, # |   0 For problem D, I submitted these 2 solutions after the contest:Submission 1 gives a Wrong Answer verdict. 188541769But when I submitted a new solution taking the answer modulo, I got a TLE verdict. 188542103I don't think I changed much of my code. Does anyone know what the heck is going on?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Modular operations are expensive. And even if they weren't, the first solution already took nearly 2s and adding more operations there inside the loop would yield TLE.
•  » » » 4 weeks ago, # ^ |   0 I see. Thanks!
•  » » 4 weeks ago, # ^ |   0 If a,b are in [0,mod-1], you can use ans=a+b; if(ans>=mod) ans-=mod; instead of ans=(a+b)%mod; 
•  » » 4 weeks ago, # ^ |   0 Also you should check if(a[1]!=0) instead of if(a[2]!=0). Because of this mistake your answer will be hacked by some tests with a[2]==0, even if don't get TLE.
 » 4 weeks ago, # |   0 problems are good , but the implementation part is a bit complicated.
 » 4 weeks ago, # |   0 For D problem,can we use dfs and work it out?
•  » » 4 weeks ago, # ^ |   0 Use DFS with memorization,in fact it is nearly the same with DP solution.My good friend wrote it,though his code was not very easy to read.188473734
•  » » » 4 weeks ago, # ^ |   0
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 As I said,you didn't use DFS with memorization.In other words,you could find that there will be many repeated search with the same $(i,ai)$.So you could record the answer of dfs(i,ai).It will cut lots of unnecessary search.Your TLE code is a $O(2^n)$ solution.If you use memorization,it will be $O(n^3)$ because you will find $|ai|$ will not exceed $90000$.
•  » » » » 4 weeks ago, # ^ |   0 hey, why are you returning 2 here? if(i==n-1) { if(ai==0)return 1; else return 2; }
•  » » » » » 4 weeks ago, # ^ |   0 Because if i==n-2,there are two operations you can make:a[i+1]+a[i] or a[i+1]-a[i].But if,a[i]=0,then a[i+1]+0=a[i+1]-0,these two ways are the same way，we can just calculate 1
•  » » » » » » 4 weeks ago, # ^ |   0 ohh, I see, thanks.
•  » » » 4 weeks ago, # ^ |   0 There's a line of code that needs to be modularized. I think my time complexity may be the same to your friend's,why mine cannot pass through?Can you help me slightly modify it and make it work?
•  » » » » 4 weeks ago, # ^ |   +1 I fixed your solution188553247
•  » » » » » 4 weeks ago, # ^ |   0 I racked my brains last night, but I couldn't figure out how to cut the branches. It turns out that you can use space to exchange time and it increases my knowledge. Thank you very much!
•  » » » » » 4 weeks ago, # ^ |   0 So it is Mnemonic search? It turns out that I can really use some simple knowledge that I am good at to pass this topic! Because the code of my friends around me is complicated, I hope my code can be changed and pass. It really turned out to be okay.
 » 4 weeks ago, # |   +3 Apparently I crashed codeforces because of a hack submission I made. I don't even remember the testcase I did, but it was supposed to bug a code that was using random generator for the answer. Anyway, thought I would leave that here so someone would look through it and see why it's still waiting for about 10 hours now!!Here is the link to the hack: https://codeforces.com/contest/1783/hacks?verdictName=TESTING&chosenProblemIndex=A
•  » » 4 weeks ago, # ^ |   0 I subitted my hack for someone's D problem last night,and it showed "generator crashed",which made me amazed,too.
•  » » » 4 weeks ago, # ^ |   0 No that's normal. That happens when the code you made to generate the testcase had some bugs in it.
•  » » » » 4 weeks ago, # ^ |   0 Aha?It shows that: The hack uses generator Generator is not determinate [the verification run produces different output, cmd =cvp], [389171 bytes, '1100000 5731847175 801 492 274 740 3 22 624 98...850 521 474 390 847 127 534 896 874 535 704 834', sha1=0cc6f6ae5c8479c995b9dec28fcd7dc48de6b3fe] vs. [388952 bytes, '1100000 5731847181 530 685 865 602 856 479 769... 803 621 675 483 837 275 74 663 223 426 353 310', sha1=911ae7fb5a320770e460a2a3d1a2c49baa34c4c6]. My hack submission includes randmized integers,so I think it's naturally that the generator is not determinate. I've tried to submit code that generates random numbers before, but I've always succeeded before, but I don't know why I didn't succeed this time. I tried to write test to a file to make the value certain, but it said the file was too big and had too much text. So I think this is a bug in the cf mechanism.
•  » » » » » 4 weeks ago, # ^ |   0 Could you send me your generator?
•  » » » » » » 4 weeks ago, # ^ |   0 You can search and see that the verdict of C problem in hacks is generator crashed
•  » » » » » » 4 weeks ago, # ^ |   0
•  » » » » » » » 4 weeks ago, # ^ | ← Rev. 4 →   0 You uses the time as the seed,may be $m \le \sum{a_i}$ won't be satisfied.You could use a number as seed instead of time.
•  » » » » » » » 4 weeks ago, # ^ |   0 You shouldn't use system time to initialize the RNG, which causes value generated become indeterminate. Use fixed seed instead.
•  » » » » » » » » 4 weeks ago, # ^ |   0 Aha?So does the fixed seed have some constraints?
•  » » » » » » » » » 4 weeks ago, # ^ |   0 Any number is ok.Such as I always uses 10086001,an interesting prime number :p
•  » » » » » » 4 weeks ago, # ^ |   0 Could you check my hack too because it's preventing the update of the ratings
•  » » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Sorry,this question is beyond my ability,may be you need to ask Mike for it XD
•  » » » » » » » » 4 weeks ago, # ^ |   0 Ok thanks
 » 4 weeks ago, # | ← Rev. 5 →   +9 Will we see rating update and tutorial before next contest begins?Why does "Educational round" mean slow rating update and slow tutorial?
•  » » 4 weeks ago, # ^ |   0 No this is because there is a hack submission that is still waiting till now. It's mine, and I don't know what's taking it so long. I hope they fix it
•  » » » 4 weeks ago, # ^ |   0 lol
•  » » » » 4 weeks ago, # ^ |   0 To think I would crash codeforces xD
•  » » » » » 4 weeks ago, # ^ |   0 I am wondering what you submitted that hacked the whole system XD
•  » » » » » » 4 weeks ago, # ^ |   0 It's really nothing xD Just a long testcase to hack a solution that uses random generator. That's all xD
 » 4 weeks ago, # |   0 How to solve G ? Seems that the tutorial won't be soon :(
 » 4 weeks ago, # |   0 Wait for D's solution.DP is my weakness...And there is still no tutorial yet?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +11 Small hint to you: In any time,$|a_i| \le s$,where $s$ is the sum of the given array. When you are going to operate $i$,you only care the value of $a_i$ now.Try to empress the dp state as $f(i,now(a_i))$.
•  » » » 4 weeks ago, # ^ |   0 Thank you.I know how to solve it now. :)
 » 4 weeks ago, # |   +23 I dont understand why this contest was downvoted, I felt like problems were good, specially C.
 » 4 weeks ago, # |   +1 I'm wondering how 300*2*300*300 solutions were accepted for D. Thats like (10^8)/2. Aren't 10^8 solutions supposed to TLE?
•  » » 4 weeks ago, # ^ |   +7 It is very easy to pass in codeforces.In fact,many $10^9$ level codes could pass in 1 or 2 seconds in codeforces with their small constant.
•  » » » 4 weeks ago, # ^ |   +7 Interesting, thanks. Wasn't really aware of it. It was a pretty straightforward dp question in that case. Will remember it for next time.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 It's like the worst case scenario strategy, because none of the authors consider 10^9 solutions
•  » » 4 weeks ago, # ^ |   +7 176169324Such as this code,it was a $O(n^3)$ solution and $n \le 1000$,but it was very fast,with a $\frac{1}{6}$ constant.
 » 4 weeks ago, # |   +1 B is worst problem fck
 » 4 weeks ago, # |   0 This Bootcamp, is it meant only for students? Or can I join at the ripe age of 33?
 » 4 weeks ago, # |   +5 Rating??
 » 4 weeks ago, # |   +4 When is system testing going to happen?
•  » » 4 weeks ago, # ^ |   0 Oh! It didn't happen all this time ? Hacking phase is finished
•  » » » 4 weeks ago, # ^ |   0 I was checking every while and I didn't see it happen
•  » » » » 4 weeks ago, # ^ |   0 Oh! I thought my solutions passed the systests already... Sad. There might be a chance for Failed systests :-(
•  » » » » » 4 weeks ago, # ^ |   0 Yeah I'm growing impatient
 » 4 weeks ago, # |   +1 Trush round!A is not perfect.Problem B is the worst problem I have ever seen.I wasted an hour on it.But C is very interesting.Hope more questions like C will appear in cf.
 » 4 weeks ago, # |   +9 Why it's taking time to get the rating updated for this contest?
•  » » 4 weeks ago, # ^ |   0 Because there is a hack submission still waiting lol
•  » » » 4 weeks ago, # ^ |   0 Oh..then, I am growing impatient these days
 » 4 weeks ago, # |   +14 Where the rating updates at?
 » 4 weeks ago, # |   +7 When will the tutorial will be published ?
 » 4 weeks ago, # |   +1 has this contest been declared unrated or what? why rating is not updated yet?
•  » » 4 weeks ago, # ^ |   +6 It takes so long in Educational Rounds
•  » » » 4 weeks ago, # ^ |   +6 Yes, and 4 hacks are not tested yet. All that hacks are on this solution, it has random and easily gets TL. I dont know why testing solutions on hacks dont break after TL...
•  » » » » 4 weeks ago, # ^ |   0 But in fact this code is expectly $O(Tn^2)$ in the worst cases,which is easy to pass.I didn't understand why it can be hacked(I submitted a same one and was hacked),could someone tell me?
•  » » » » » 4 weeks ago, # ^ |   0 I don't know about TLE, but does random give 100% correct answers?
•  » » » » » » 4 weeks ago, # ^ |   0 If it was checked that the array was not correct,it will repeat the random algorithm till it find a correct answer.
•  » » » » » 4 weeks ago, # ^ |   +13 If you have array [1, 1, 1, 1, ... , 2] you have 2 correct answers — [1, 2, 1, 1, ..., 1] or [2, 1, 1, 1, 1, ..., 1]. In this case you have n possible permutations of array, so in each random shuffle you have only 2 correct answers from n, where maximal n = 50. if you do K random shuffles, probability of your win would be correct positions / all positions. All positions = n ^ k, correct positions = all positions — bad positions = n^k — (n-2) ^ k. So if you do K random shuffles probability of finding correct answer is P = (n^k — (n-2)^k) / n^k. For n = 50: if k = 5, P = 0.1846273024 if k = 10, P = 0.33516736 if k = 100, P = 0.98312968 So on this testcase it does 100 shuffles for finding answer. So your code does t * n * K = 2000 * 50 * 100 = 1e8 operations, and you choosing random number 1e8 times for shuffling array, and this can take long time and maybe TL. If you would find testcase where is only one correct permutation:P = ((n^k) — (n-1)^ k) / (n^k) if k = 5, P = 0.096079 if k = 10, P = 0.182927 if k = 50, P = 0.635830 if k = 100, P = 0.867380 if k = 200, P = 0.982412 In this case your code does t * n * K = 2000 * 50 * 200 = 2e8 operations
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 Yeah I thought just like you,but I tried to use $2000,50,1 1 1\cdots 2$ to hack it,but it ran very fast,just used 93ms!linkAnd I just found the all the data hacked my submissions satisfied that $n$ is small(In fact,$n=4$). I'm a bit confused about it.
•  » » » » » » 4 weeks ago, # ^ |   0 I just wrote a random algorithm as it.188610805I guess that randomize in the hacked code is the murderer of it.
•  » » » » » » » 4 weeks ago, # ^ |   0 Yes, randomize function is bad and slow.When you tried to hack his solution it's not guaranteed that his random would use 100 operations — maybe if he would lucky he can find correct answer in 5 or 10 attempts. About test that hacked your code, i dont really understand why it failed, because for n = 4 and k = 5, P = 0.96, so you need on the average 5 attempts for shuffle, so I dont know why it got TL...I will try your solution in locale on testcase which hacked your solution, if I would find something interesting I will write you in messages.
•  » » » » » 4 weeks ago, # ^ |   0 It was me who hacked it. Sorry xD
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I didn't care about it(And it wasn't my code in contest),I just wanted to know why it got TLE(And now I get it).And my submission above with shuffle seems to be correct.
•  » » » » » » » 4 weeks ago, # ^ |   0 Yeah some types of shuffle will work. I saw someone use random_shuffle and when I looked at it in the documentry it looked like a very good way of shuffling, and a fast way too. It just two successive elements, which is really all what you might need for the answer
 » 4 weeks ago, # |   +4 The contest is supposed to be rated right?
 » 4 weeks ago, # |   0 IMO Editorial should be provided shortly after the hacking phase finished.It's too long.
 » 4 weeks ago, # |   0 Can anyone explain how to solve problem F?
•  » » 4 weeks ago, # ^ |   +16 We will post the official editorial in one or two hours. Here's an explanation of F copied from it. SpoilerThe solution to this problem uses cyclic decomposition of permutations. A cyclic decomposition of a permutation is formulated as follows: you treat a permutation as a directed graph on $n$ vertices, where each vertex $i$ has an outgoing arc $i \rightarrow p_i$. This graph consists of several cycles, and the properties of this graph can be helpful when solving permutation-based problems.First of all, how does the cyclic decomposition of a sorted permutation look? Every vertex belongs to its own cycle formed by a self-loop going from that vertex to itself. We will try to bring the cyclic decompositions of the given permutations to this form.What does an operation with integer $i$ do to the cyclic decomposition of the permutation? If $i$ is in its own separate cycle, the operation does nothing ($p_i = i$, so we swap an element with itself). Otherwise, let's suppose that $x$ is the element before $i$ in the same cycle ($p_x = i$), and $y$ is the element after $i$ in the same cycle ($p_i = y$). Note that this can be the same element. When we apply an operation on $i$, we swap $p_x$ with $p_i$, so after the operation, $p_i = i$, and $p_x = y$. So, $i$ leaves the cycle and forms its separate cycle, and $y$ becomes the next vertex in the cycle after $x$. So, using the operation, we exclude the vertex $i$ from the cycle.Suppose we want to sort one permutation. Then each cycle having length $\ge 2$ must be broken down: for a cycle of length $c$, we need to exclude $c-1$ vertices from it to break it down. The vertex we don't touch can be any vertex from the cycle, and all other vertices from the cycle will be extracted using one operation directed at them. It's easy to see now that if we want to sort a permutation, we don't need to apply the same operation twice, and the order of operations does not matter.Okay, then what about sorting two permutations in parallel? Let's change the problem a bit: instead of calculating the minimum number of operations, we will try to maximize the number of integers $i$ such that we don't perform operations with them. So, an integer $i$ can be left untouched if it is the only untouched vertex in its cycles in both permutations... Can you see where this is going?Suppose we want to leave the vertex $i$ untouched. It means that in its cycles in both permutations, every other vertex has to be extracted with an operation. So, if two cycles from different permutations have a vertex in common, we can leave this vertex untouched, as long as there are no other vertices left untouched in both of these cycles. Let's build a bipartite graph, where each vertex in the left part represents a cycle in the first permutation, and each vertex in the right part represents a cycle in the second permutation. We will treat each integer $i$ as an edge between two respective vertices in the bipartite graph. If the edge corresponding to $i$ is "used" ($i$ is left untouched), we cannot "use" any edges incident to the same vertex in left or right part. So, maximizing the number of untouched numbers is actually the same as finding the maximum matching in this bipartite graph.After you find the maximum matching, restoring the actual answer is easy. Remember that the edges saturated by the matching correspond to the integers we don't touch with our operations, the order of operations does not matter, and each integer has to be used in an operation only once. So, the actual answer is the set of all integers without those which correspond to the edges from the matching.This solution runs in $O(n^2)$ even with a straightforward implementation of bipartite matching, since the bipartite graph has at most $O(n)$ vertices and $O(n)$ edges.
•  » » » 4 weeks ago, # ^ |   +5 So when will system testing phase start?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +6 I don't know. I don't understand what happened to those several hacks which can't be tested, and I am awaiting a response from Codeforces admins.Hopefully this will be fixed soon.
 » 4 weeks ago, # |   0 ratings not been updated MikeMirzayanov
 » 4 weeks ago, # |   +13 Why do the ratings not still updated.Is any cheater caught or something else.Please update the ratings soon. Thankyou!!!
 » 4 weeks ago, # | ← Rev. 2 →   +13 MikeMirzayanov Why am i not rated? Please update the ratings soon. Thankyou!!!
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 4 weeks ago, # |   +5 Thanks for the Editorial :) Can anyone say why ratings are still not updated?
 » 4 weeks ago, # |   +5 When will the system testing is going to start?
 » 4 weeks ago, # |   0 why rating is still not updated?
 » 4 weeks ago, # |   0 Ratings have not been released yet!!!
 » 4 weeks ago, # | ← Rev. 2 →   0 Still no change in ratings :(
 » 4 weeks ago, # |   +52 Sorry, this is my fault. I completely forgot about judging this round, I just somehow got distracted and flew out of my head. Is it old age? Soon the round will be re-judged taking into account hacks and then take care of the rating!
•  » » 4 weeks ago, # ^ |   +23 The ratings are updated preliminarily. Tomorrow I will remove cheaters and update the ratings again!
•  » » » 4 weeks ago, # ^ |   +8 Thanks for first time I've been orange!
•  » » » 4 weeks ago, # ^ |   +11 there is no change in my rating and i see a lot of people got their rating updated. please look into this.
•  » » » 4 weeks ago, # ^ |   +8 MikeMirzayanov my rating is not updated till now and i see a lot of people getting their rating updated. please look into this.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 It's strange those who solved 2 problems with 50 penalty are ranked #2835 in "common standing" but ranked #2834 in "rating changes". Maybe this difference is caused by someone was omitted in rating calculation…
•  » » » » » 4 weeks ago, # ^ |   0 No only some are eliminated before 3000 rank...I mean to say...their rank of contest is pretty good before hack period and copy cat searching dudes..
•  » » » 4 weeks ago, # ^ |   0 30 minutes before the next contest. Hope for fast cheater removal
•  » » » 4 weeks ago, # ^ |   0 Now my rating is under 2100, if in the next div2 contest my rating is updated to 2100+, will I be rated in the next contest?
•  » » » » 4 weeks ago, # ^ |   0 Did you participate? Was it rated for you? Just curious
•  » » » » » 4 weeks ago, # ^ |   0 I participated it. The rating has not been calculated yet.
 » 4 weeks ago, # |   +2 Why rating update before next contest is important?Some people are on boundaries of getting new color to profile...they becomes aware before their upcoming contests and prepare as per that situation....Some might think to get good ranks in div3 Some might think that educational rounds are easy ...let's try for that and can skip some contestSome might have got good rank and might be eager for announcements....One of my friend won't eat food if contest not goes good....coding is turning someone emotion...❤️..Wow that's fantastic to listen it and get ready for coding...!We salute to efforts of all coding platforms...!! for making coding as emotion
•  » » 4 weeks ago, # ^ |   0 Haha, your words are like long, complicated, but sincere prayers.
 » 4 weeks ago, # |   0 help me. I am not able to figure out test case in which my code will fail. Your text to link here...
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Check out this testcase 1 4 1 6 6 6 
 » 4 weeks ago, # |   0 First time I “FSTed” with a later accepted time
 » 4 weeks ago, # |   +5 is this round unrated?
 » 4 weeks ago, # |   +1 Can anyone say why the given ratings are rolled out?
 » 4 weeks ago<