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

UPD: Editorial is out

• +45

 » 6 weeks ago, # |   0 Educational Round are the best for me, good luck for all participant <)(>.
 » 6 weeks ago, # |   +4 Goodluck all participants <3
 » 6 weeks ago, # |   -11 hope I become a specialist today !!!! :)
•  » » 6 weeks ago, # ^ |   0 Solve 3 problems in less than 30 minutes of time.
•  » » » 6 weeks ago, # ^ |   0 don't expose the secret technique of speed-solving experts :)
•  » » » » 6 weeks ago, # ^ |   0 okay...XD
•  » » » » 6 weeks ago, # ^ |   +7 plz bro can guide us how to do speed solving
•  » » » » » 5 weeks ago, # ^ |   +6 Practice . I speedforces upto to D. Guess what ?? i will become expert today. Haha
•  » » » » » » 5 weeks ago, # ^ |   0 Soml xD
•  » » » » » » 5 weeks ago, # ^ |   0 I sometimes speedforce upto D. but average I can only do until B or C
•  » » » » » » » 5 weeks ago, # ^ |   +1 When i was newbie i was only able to solve A and sometimes B. You are already ahead of me mate. That's great
•  » » » » » 5 weeks ago, # ^ |   0 Learn to use STL. Use macros to define function and declaration in short lines. Also, use good editor like sublime text etc.
 » 6 weeks ago, # |   0 hope it'll be easier, good luck to everyone
 » 6 weeks ago, # |   0 Can anyone guess what the rating range problem C would be??
•  » » 6 weeks ago, # ^ |   +2 1400-1600
•  » » » 6 weeks ago, # ^ |   +23 I mean there has been Cs with 2000 rating like robot collision from Edu round 109, so trying to generalize ratings of problems could get you stuck trying to solve a problem that is way harder than what you think.
•  » » 6 weeks ago, # ^ |   0 I think it's like around 1200. Question difficulties have increased significantly to account for rating inflation.
•  » » 5 weeks ago, # ^ |   0 i think around 1100 to 1400
 » 6 weeks ago, # |   +21 Hope problems are less Ad-hoc and more algorithmic this time :/
 » 6 weeks ago, # |   -6 i love truc an
 » 6 weeks ago, # |   0 I hope there will be a lot of issues with the algorithm. I hope everyone will participate)
 » 6 weeks ago, # |   +1 Always love educational round.
 » 6 weeks ago, # |   +7 I can not thank you guys enough. Thankyou so much for your efforts.
 » 6 weeks ago, # |   +3 Educational rounds seems brainstroming to me. Does this happens to others also? But, Happy to attend these contest thinking one day these hard problems would be easy for me. Best of luck guyzz.
•  » » 6 weeks ago, # ^ |   0 "Useful, even well-known ideas can be reused in order to introduce them to a wide range of participants;"
 » 6 weeks ago, # |   +11 For the love of back to back rounds. <3
 » 6 weeks ago, # |   0 Best of Luck to everyone hope u all give your best.
 » 6 weeks ago, # | ← Rev. 5 →   0 hope this day will memorable to you all.
 » 6 weeks ago, # |   +16 Hope that I will not mess everything up again.
•  » » 6 weeks ago, # ^ |   +7 Hope you to become master and I can get specialist this round :>
•  » » » 6 weeks ago, # ^ |   +1 Thanks!
•  » » 6 weeks ago, # ^ |   0 Considering your rating history, I don't understory what you mean by "again"
•  » » » 6 weeks ago, # ^ |   +3 Because of stupid mistakes like not opening correct array sizes or mistaking C for D,I lost 150+ points.I might have got top 100 if I didn't.TAT
•  » » 6 weeks ago, # ^ |   0 Your messing up is equivalent of my best performance
•  » » 5 weeks ago, # ^ |   0 I just lost my color.HackingForces
•  » » » 5 weeks ago, # ^ |   -18 Testers/Testcase makers while making test cases for D...
 » 6 weeks ago, # |   +1 Thank you for the contest
 » 6 weeks ago, # |   0 Probably one of the best question sets this year!! However, I made a typo on question C which costed 20 minutes and 4 penalty attempts :(
 » 6 weeks ago, # |   +45 Only solved A-C again :(Maybe I should have a rest……
•  » » 6 weeks ago, # ^ |   +8 Relatable :(
•  » » 6 weeks ago, # ^ |   +67 D is just such a frustrating problem I hate it so much. Eventhough I solved it took me an entire hour to realize it is just a stupid bruteforce. it was not fun at all. so it's not your fault
•  » » » 6 weeks ago, # ^ |   +13 How do you prove bfs will not time out though?
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   +3 I did a bfs, but only took the 10000 highest numbers after each step. Have no proof that this yields always the correct answer (although I have a strong feeling that it does), but for sure this won't time out. (And just now I noticed, that I forgot to erase duplicate numbers. Uh-Oh...) 158202121
•  » » » » » 5 weeks ago, # ^ |   +8 It even works if we take just the top 5 numbers after each step. I am a little surprised.
•  » » » » » » 5 weeks ago, # ^ |   +16 Maybe you will be more surprised tmrw morning..
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 '
•  » » » » 6 weeks ago, # ^ |   +9 That was my problem the entire time! but after proofing by AC I think you can prove it this way: so because multiplication is commutative (i.e. 5*3 =3*5) then the order of the digits you use doesn't matter. How many numbers you can multiply by so that the result doesn't exceed 10^n? not that many as you are only using digits between 0 and 9
•  » » » » 5 weeks ago, # ^ | ← Rev. 5 →   +40 Numbers which will increase x are from 2 to 9 in which prime numbers are 2,3,5,7.So x will eventually turn into x*( 2^a * 3^b * 5^c * 7^d ) after some number of operations.As we all know 2^63, 3^39, 5^27, 7^22 are all close to 10^19.So 64 * 40 * 28 * 23 = 1648640 are the number of different numbers that can be made. In this I have considered all the numbers which can be made using these combinations of prime to the power of some number. Which will not be the case in the real brute force implementation. It will close out at about 1e5 or so. There's your proof.
•  » » » » » 5 weeks ago, # ^ | ← Rev. 3 →   +11 Great! I think there is a tighter upper bound.If we simply see that (a + b + c + d) <= 64 (considering a = 64, b=c=d=0). So, the numbers possible is found from this formula —  (N+R-1)C(R-1)  i.e (64 + 4 - 1)C(4-1) which approximates to 47905.
•  » » 5 weeks ago, # ^ |   0 I think it's just the fact that it's Educational round. You can see my contest history, and literally from each educational round I consistently have negative delta. And they also have an "individual" feature of FSTing and a lot of hacks each time.
 » 6 weeks ago, # |   +26 Educational speedingforces
 » 6 weeks ago, # |   0 B was easier than A
•  » » 6 weeks ago, # ^ |   0 for real bruh, nothing to write
•  » » 5 weeks ago, # ^ |   0 yep. just 4 to 3 lines and done
 » 6 weeks ago, # |   +4 Dude, really 6500+ people solved C?
•  » » 6 weeks ago, # ^ |   0 Yeah, coz n^2 is also allowed
•  » » » 6 weeks ago, # ^ |   +9 I fiddled like half an hour on a nice solution before realizing that stupid bubble sort also works.
•  » » » » 5 weeks ago, # ^ |   0 lmao just realized this. I wrote a solution that uses a n queries at most. It was not much write though
•  » » » » 5 weeks ago, # ^ |   +1 actual selection sort.
 » 6 weeks ago, # |   0 Speedforces
 » 6 weeks ago, # |   +9 What was the approach for D? Weren't we supposed to multiply the number by its biggest digit each time or I am wrong?
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   0 I solved it using maps and DP, not sure if there is a greedy solution for it
•  » » » 6 weeks ago, # ^ |   0 Proof that this wont give TLE?
•  » » » » 6 weeks ago, # ^ |   0 Well, this will require a lot of thinking and tracing, and honestly, I'm not very convinced but I would say that since I'm starting with one number for example 123 and I want to try to multiply it by 2 or 3, no matter what is the result they will all be divisible by 123 so the chance of duplicates is very high.
•  » » » » » 5 weeks ago, # ^ |   0 Lol now I'm convinced after I wrote this comment
•  » » » » » 5 weeks ago, # ^ | ← Rev. 4 →   0 no how does this matter? You can have so many numbers that are divisibl by 123 up to 10^19. it's \floor{10^19}/123>= 1e^16. I think it has to do with the fact that you only use digits and that you multiplication is commuitative1. __
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 we can have so many numbers that are divisible by 123, but not all of them are included because we are multiplying and growing fast.After looking into other solutions, seems that DP is not required to solve the problem but this is what came into my mind first.EDIT: One important thing that makes my observation true is that we only can multiply by 8 numbers [2,9]
•  » » » » 5 weeks ago, # ^ |   0 This comment is nice. https://codeforces.com/blog/entry/103099?#comment-915079
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +5 I thought about DP, but wrote greedy which works in $O(2^n)$. (On every step choose from 2 different maximum digits). Surprisingly it got AC.EDIT: Hacked :D
•  » » » » 6 weeks ago, # ^ |   0 Can anyone explain why this works. I did similar logic (few mins after the contest ended) and it got accepted. But still can't fully convince myself on why this works.
•  » » » » » 5 weeks ago, # ^ |   0 Update: Wrong answer on test 88.
•  » » » » 5 weeks ago, # ^ |   0 why the limit of 1000 ?
•  » » » » » 5 weeks ago, # ^ |   0 Just a number which is bigger than possible maximum answer (if we take 2 on every step, there will be maximum $log_{2}(x)$ steps.
•  » » » » 5 weeks ago, # ^ |   0 lul.. that's why you should never reveal anything "surprising" about your approach while the hacking round is still going on.
•  » » » » » 5 weeks ago, # ^ |   +7 No. My main mistake was to think about E/F tasks instead of resolving D in proper way, while I had a feeling my intuitive solution is wrong. Someone proved this, and it's good, I don't really care about color.
•  » » 6 weeks ago, # ^ |   -6 If you always multiply by the biggest number then you might exceed n
•  » » » 6 weeks ago, # ^ |   +27 No this will never happen as each time you can at most increase the size by one. The problem with the greedy approach is that it might lead you to a number that has digits of low values, so it is the same problem with "good localy, bad globaly"
•  » » » » 6 weeks ago, # ^ |   0 Thanks for the explanation
•  » » 6 weeks ago, # ^ |   +12 you can't even pass given testcase by that greedy approach..
•  » » 6 weeks ago, # ^ |   0 No bro, the counter example is given in sample.
•  » » » 6 weeks ago, # ^ |   0 Yeah thats what I am saying. However Im asking about the logic overall. In my head we get the best result while multiplying number by its biggest digit. Isnt it correct?
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +3 test case : 13 42
•  » » 5 weeks ago, # ^ |   0 6 -> 7 is better than 9 -> 3 so you might multiply by a lower number at first in order to gain better number in the future
•  » » » 5 weeks ago, # ^ |   0 158229061 what should I add here?
•  » » 5 weeks ago, # ^ |   +21 123456789x9=1111111101 and you're stuck :D
 » 6 weeks ago, # |   0 What's the proof for C???
•  » » 6 weeks ago, # ^ | ← Rev. 4 →   0 selection sort and max number of inversions(4950) is lesser than 10^4
•  » » 6 weeks ago, # ^ |   0 it's a swap so between any two indices so it won't take more than n steps. (unless I get hacked)
•  » » 5 weeks ago, # ^ |   +1 first forget about the values, after some swaps you'll attain a permutation of the indices so any permutation that works for both a and b is good, let us sort a first and then check if we can sort b without ruining the first sort(only moving elements with the same value), this process produces a new permutation and what's left is to check it
•  » » » 5 weeks ago, # ^ |   0 Thank you :)
•  » » 5 weeks ago, # ^ |   0 We can also sort the whole thing in O(n*n) where n is 100 so it'll possible to do in <1e4 operations.
 » 6 weeks ago, # |   +5 I think today's contest was easy as compared to normal Div2 rounds
 » 6 weeks ago, # |   +6 I spent 30 minutes thinking that C could be solved greedily, then I said let me just try to perform the K swaps no matter what, and it passed LOL
 » 6 weeks ago, # |   0 What was the idea behind E and F?
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +16 I used binary lifting in E. We just maintain the dp array of $jmp_{i,j,k,l}$ which represents the minimum distance moving $2 ^ j$ from the ith section first using the kth door of the ith section and ending up at the lth door of the $i + 2 ^ j$ sectionEDIT: Sorry for being ambiguous in the original response
•  » » » 6 weeks ago, # ^ |   0 Binary lifting what, and in which problem?
•  » » » » 5 weeks ago, # ^ |   0 You can use binary lifting for E, it's similar to the idea for BOI 2017 Toll.
•  » » » 5 weeks ago, # ^ |   0 Can you elaborate how do you count the binary lifting array?
•  » » » » 5 weeks ago, # ^ |   0 I did it like how u would do initialize a sparse table
•  » » 6 weeks ago, # ^ |   0 In E binary-lifting or $SQRT$-decomposition can be used. I tried the second but failed to make it accurate and correct (as usual).
 » 6 weeks ago, # |   0 God damn it! So everyone knew how to solve F except me. I lost my chance to became Master.I'm so sad now....................
•  » » 5 weeks ago, # ^ |   -8 similar nickname，same hacked on Problem D :(
 » 6 weeks ago, # |   0 Can anyone hack me? Unordered map Your text to link here...
 » 6 weeks ago, # |   0 How to solve F?
•  » » 6 weeks ago, # ^ |   +44 You can consider each $x$ separately. You can compress nodes connected by non-$x$ edges to get a new tree for each $x$. A pair of nodes $u, v$ has $x$ as a unique occurrence only if $u$ and $v$ belong to adjacent nodes of the new tree of $x$.To build the tree efficiently, iterate through all original tree nodes in decreasing order of depth and simultaneously build all the new trees. When you encounter a node $u$ for which the edge connecting it and its parent has value $x$, search for all components of $x$ already existing within the subtree of $u$, and join them to get a new component of $x$.
 » 6 weeks ago, # |   0 What's the intuition behind D??
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Use Breadth-first, a multiply x with every digit and take care of duplicates and also manage edge cases like if x=1 and n>1, ans=-1
•  » » » 5 weeks ago, # ^ |   0 length(x) can't be > n because x < 10^(n — 1)
•  » » » » 5 weeks ago, # ^ |   +3 Thanks , edited
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +3 I used dp, where dp[i][j][k] = max number after i steps lastly multiplied by j and has k as digitNumber of steps can't be more than 30, checked it with greedy
•  » » 5 weeks ago, # ^ |   0 I used memoized search: https://codeforces.com/contest/1681/submission/158228515
 » 6 weeks ago, # |   +21 In task D, How to know that memorization in a map will not exceed time limit?
•  » » 6 weeks ago, # ^ |   0 I also used the map, but it passed the pretest. I hope it will also pass the system test
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Even if you multiply by 2 everytime you will reach n digits extremely fast. This along with the fact that you can multiply by only 8 distinct number assures that the number of states transitions are actually quite small.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +7 no it does not. If you can multiply 8 distinct digits to get 8 distinct products, that has a very high upper bound. The map solutions have passed as the number of "distinct" numbers encountered, the "X"s are limited. That is different from what you meant to say. Edit: Explanation below makes more sense.
•  » » » » 5 weeks ago, # ^ |   0 You're right. I believe the 8 numbers fact is more prominent in a way that it limits the number of transitions from one state greatly.
•  » » 6 weeks ago, # ^ | ← Rev. 6 →   +105 Just notice that any value $y$ that will be reached can be represented as $y = 2^{\alpha}3^{\beta}5^{\gamma}7^{\delta}x$ and realize that the total possible combination of the quadruple $(\alpha, \beta, \gamma, \delta)$ is loosely upperbounded to $log_{2}z * log_{3}z * log_{5}z * log_{7}z = 60 * 40 * 26 * 21 \approx 1.5 \times 10 ^ 6, z = 10 ^ {n - 1}$, but obviously didn't prove during contestEDIT: Made the explanation a bit clearer.
 » 6 weeks ago, # |   +18 Trash E.It only takes me 5 minutes to manage out a way to solve it using something like Matrix multiplication and Segment Tree or binary lifting. But there are TOO MANY GOD DAMN DETAILS that I failed to accept it before the contest ends.I hope there will be more brain-consuming problems (maybe greedy or constructive ? ) instead of such complex and meaningless ones.
•  » » 5 weeks ago, # ^ |   +1 +1, the detail are nightmare to follow, I kept getting WA on test 5 :(, but since it's and edu round it completely deserves to be their.
•  » » 5 weeks ago, # ^ |   -9 Trash E? Trash you!
 » 6 weeks ago, # |   0 I use DFS to solve problem-D, but get TLE. :D158223688
•  » » 6 weeks ago, # ^ |   +8 You need to use memoization to avoid visiting the same values multiple times (which can happen).
•  » » » 5 weeks ago, # ^ |   0 yes, it should use memoization, so BFS + memoization, not DFS + memoization.
•  » » » » 5 weeks ago, # ^ |   0 I used DFS + memoization. Worked ok. I guess you could try to hack me :)
•  » » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 oh! I get AC with DFS + memoization 158229644, but I think BFS is more better, because if DFS always meets bad answer firstly, then memoization does't work.
•  » » » » » » 5 weeks ago, # ^ |   0 Well, as I say, I used memoizaton and haven't been hacked yet. Why do you think it doesn't work?I simply called a 'bad' answer very big (1e9) and then said if my final answer was >= 1e9, then output -1.
•  » » » » » » » 5 weeks ago, # ^ |   0 I just watched your submission, now I understand what you mean. My submission is not best, I just visite digits of x from left to right, I should visite them from big to small.
•  » » » 5 weeks ago, # ^ |   0 Hi @jimm89. I tried DFS too. Got TLE. Used memoization and it worked. Its kinda weird that you need memoization for this. I initially thought the probability that you will encounter a value you encountered before is so low. I thought the overhead for using a map would harm more than it will help but it is the other way around :-) I was just curious if I will need memoization for BFS as well.
•  » » » » 4 weeks ago, # ^ |   0 I expect you would not need memoization for BFS.I saw that tourist submitted a DFS solution with no memoization, but with sufficient pruning so as not to TLE. I suspect he knew it would not TLE, but did also wonder whether that was due to instinct from vast experience or whether there was some underlying (very fast) deeper thought process. Effectively the solution tries 'higher digit' paths first and then also eliminates any path which could be longer than the current best answer.For that reason, I am confident that BFS is fine without memoization, since you will only visit paths shorter than or equal to the best answer.
 » 6 weeks ago, # |   0 Can someone share the approach for problem F ,how to solve it using disjoint sets
•  » » 6 weeks ago, # ^ |   +8 you may google "dynamic connectivity problem (offline)"
 » 6 weeks ago, # | ← Rev. 2 →   +2 Why are there orange people in the official standing?
 » 6 weeks ago, # |   +10 Can we solve F using smaller to larger technique ?
•  » » 6 weeks ago, # ^ |   +10
•  » » » 5 weeks ago, # ^ |   +3 Can you explain exactly what are doing in your code ? and what will be the time complexity ?
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   +1 what is smaller to larger technique? can you refer any blog?
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0
 » 5 weeks ago, # |   +40 What a bullshit D.
•  » » 5 weeks ago, # ^ |   +4 If I solved that shit, I would achieve performance of IM because I solved ABCF before. But now I even lost my rating.
 » 5 weeks ago, # |   +6 First time solved 4 problems in div 2
 » 5 weeks ago, # |   +101 What the meaning of D? I can't imagine the reason to put a rubbish standard dfs in the place of D.Is it so hard for you to simply delete this problem? I can come up with hundreds of problems like this.And for the difficulty, many people can't solve it just because they aren't dare to use such a stupid method in fourth problem. Why not put it in the place of A?
•  » » 5 weeks ago, # ^ |   +16 that's sums up my feelings. If this was C, people would have done it faster and lots more people would have solved this.
•  » » 5 weeks ago, # ^ |   +33 The point of D is to be a problem on implicit BFS/DFS/dynamic programming where it's not so obvious (but easy to prove) that the solution is fast enough. I don't think that your claim "they don't dare to use such a stupid method" is correct; proving that it works is not difficult.
•  » » » 5 weeks ago, # ^ |   +61 I would guess that most the people who solved it didn't actually prove that the number of states is small enough.
•  » » » 5 weeks ago, # ^ |   +36 It is true that the dfs solution can be proved to be fast enough. However, this is a programming contest, not a math contest. Most people who passed this problem during contest didn't think about what the complexity will be, they just tried dfs and it worked. The aim of the problem is to separate people who can come with a method and who can't, not "Here is an easy way to solve the problem. Can you prove it?" This way it will be more like a math problem. The proving part is important but that's not something that should be asked in contest.
•  » » » » 5 weeks ago, # ^ |   -8 You say "Here is an easy way to solve the problem" as if it's written in the problem statement that you should use DFS/BFS/something other there. I agree that this problem is on the easy side for ER D, but I don't think it's C level.I don't see anything wrong with some participants guessing that the method works without any actual proof. This is fairly common even on high-level contests. As long as the proof doesn't take five full pages of formulas (I mean, it's definitely possible to come up with the proof in a short period of time), it should be fine, in my opinion.
•  » » » » » 5 weeks ago, # ^ |   +17 I am not familiar with what the difficulty of ER D should be, maybe some of my opinions are biased. I am just expressing my confused feeling after solving this problem.Actually, I would really appreciate if the problem is changed to "Count how many different numbers $\le N$ could be reached by using this function."
•  » » » » » 5 weeks ago, # ^ |   +15 By the way, I do think that the problem statement directly points to the dfs solution because that's just something everyone will come up with after seeing the problem.
•  » » » » » » 5 weeks ago, # ^ |   -19 Judging by the results of our local competition where I used this problem yesterday, it's not the case. Some of our students definitely recognized a graph problem fairly quickly, but not all of them, even those who are kinda familiar with DFS/BFS.
•  » » » 5 weeks ago, # ^ |   +35 In fact I used pruning instead of memoization. 158184259This shows another problem: you can get accepted using whatever approach you want as long as you dare try the easiest dfs.So, I think his claim "they don't dare to use such a stupid method" is totally correct since I don't think a lot of people actually proved it. The people who solved it are probably just like "okay, let's try dfs. Test 19 42 and the answer came out immediately so submit!"This way of thinking is definitely not good for ER D.
 » 5 weeks ago, # |   -27 Is it just me, or does anybody else hate ALICE and BOB? They are always wasting our time by playing weird games.
•  » » 5 weeks ago, # ^ |   0 A for Alice and B for Bob to avoid confusion — it's pretty common.
•  » » 5 weeks ago, # ^ |   0 i agree i don't know why people downvote you i started developing a phobia of them and the game tag Spoilerjust joking
 » 5 weeks ago, # | ← Rev. 2 →   +17 Kind of sad that $O(N (\log{N})^2)$ approaches passed in F.I initially had an interesting $O(N^2 \log{N})$ solution where I run a re-rooting DP on each edge weight separately, to calculate contributions of that edge weight (a range sum data structure was used for this, thus the log factor). I sped this to $O(N \log{N})$ by using the DFS times for each node and simulating the DFSs for each edge weight by just looping along occurrences of each edge weight in the DFS order, using only $O(\text{occ}(x) \log{N})$ for each weight $x$, where $\text{occ}(x)$ is the number of occurrences of $x$.Edit to add:Since people seem confused, I will explain my solution in some more detail. Firstly the $O(N^2 \log{N})$ idea. First root the tree arbitrarily. Now, we find the contribution for each edge weight separately. I will describe how to calculate the contribution of edge with weight $x$.Notation:$\text{comp}(u, x)$ is the size of connected component of if only edges with weight not equal to $x$ are considered, $\text{sz}(u)$ is the size of subtree of $u$, $\text{par}(u)$ is the parent of node $u$, $\text{anc}(u)$ is the set of proper ancestors of $u$, $\text{sub}(u)$ is the set of nodes in subtree of $u$.Define $\text{dp1}[u] = \text{comp}(u, x)$ if the parent edge of $u$ has weight $x$ and $0$ otherwise. Similarly, define $\text{dp2}[u] = \text{comp}(\text{par}(u), x)$ if the parent edge of $u$ has weight $x$ and $0$ otherwise.How to compute $\text{dp1}[u]$? Some careful thought yields: $\text{dp1}[u] = \text{sz}(u) - \sum_{v \in \text{sub}(u), v \neq u} \text{dp1}[v]$and $\text{dp2}[u] = n - \text{sz}(u) - \sum_{v \in \text{anc}(u)} \text{dp2}[v] - \sum_{v \notin \text{anc}(u), v \notin \text{sub}(u)} \text{dp1}[v]$With these expressions, $\text{dp1}[u]$ can simply be computed with DFS and a range sum data structure (on the Euler tour of the tree). After computing all values of $\text{dp1}$, the $\text{dp2}$ values can be computed with DFS and a range sum data structure, noting that $dp2$ value of a node $u$ will be used when $u$ is an ancestor and $dp1$ otherwise. So, these values can be switched in the range sum data structure during DFS.Contribution of weight $x$ is simply $\sum \text{dp1}[u] \cdot \text{dp2}[u]$.How to make this $O(N \log{N})$? Well, since only particular $dp$ values are ever non-zero for a weight $x$, we can simulate the entire process by just looping over the positions of these nodes in the DFS order.Code: 158206764
•  » » 5 weeks ago, # ^ |   +99 samjh nhi aaya pr sunke aacha laga
•  » » 5 weeks ago, # ^ |   +8 I initially had an interesting $O(N^2 logN)$ solution where I run a re-rooting DP on each edge weight separately, to calculate contributions of that edge weight (a range sum data structure was used for this, thus the log factor).You can improve this solution to $O(N)$.
•  » » » 5 weeks ago, # ^ |   0 Oh yes, somewhat painful, but can be done.
•  » » 5 weeks ago, # ^ |   0 I am trying to Solve Problem F using centroid Decomposition.Timecomplexity should be : $O(N(\log(N)^2)$,But I am getting TLE on TestCase 45.MySolution:158262510.
•  » » 5 weeks ago, # ^ |   +8 I have $O(n)$ solution of FFor each value of $w$ from 1 to $n$, break all edges which have weight $w$. The tree will break into connected components. Now for each pair of "adjacent" connected components(i.e. components which were connected by the broken edge) you need the number of paths starting from one component and going to other. If we store everything in dfs order, then this can be accomplished in $O(n)$. It is not that painful but my implementation is a bit messy.https://codeforces.com/contest/1681/submission/158273456
 » 5 weeks ago, # |   0 I think this contest was an easy one (from my perspective). I had never been able to solve problems upper than B in a div2 rated contest. Here I was able to solve up to C.!
 » 5 weeks ago, # |   +6 Problem D was so frustrating. Still can't figure out why DFS would work? Also, can anyone point out what is the issue with the idea of always multiplying with the largest digit in X? This should give the largest possible number in some number of moves, right?
•  » » 5 weeks ago, # ^ |   0 In same test case n = 13, x = 42. 1. 42 * 4 = 168 Now, we've 2 choices either 6, 8 (ignore 1) Surprisingly taking 6 would yield 12 steps to reach goal. While taking 8 would need 13.
•  » » 5 weeks ago, # ^ |   0 I initially applied DFS but it was giving WA on test 3. Tried BFS and it worked
•  » » » 5 weeks ago, # ^ |   0 But why did it work? From what I can think of, we have 10 different possible states to go from each number. Talking in terms of Tree DS, we have a rooted tree of depth ~20 and each node has 10 children. This leaves us with around 10^20 leaf nodes. Is that even possible to solve?Is there any special structure to the problem which is not considered in my analysis?
•  » » » » 5 weeks ago, # ^ |   0 I donot know how to prove it but it got ac. I think some values will repeat in sequence so you do not need to process them, and hence the solution will pass in time. I tried to test it, at max only "4833" values were inside my queue when it reached level 19.
 » 5 weeks ago, # |   0 158229061 what should I add for this D problem submission so it will work? Or at least give TLE..
•  » » 5 weeks ago, # ^ |   0 Note that it is not always optimal to multiply by the largest digit every time.See this comment (and maybe work it out on paper too).
•  » » » 5 weeks ago, # ^ |   0 But that’s basically what dupl vector and for loop is for. Am I wrong?
•  » » » » 5 weeks ago, # ^ |   0 Yes -- it looks like you are keeping track of what digits appear in a single current number and then picking a digit to multiply by based on what maximizes the next number.What I am saying is that this decision of taking the largest of the results is not globally optimal.
 » 5 weeks ago, # |   0 The contest is nice but there are plz skip them ... bcz problems A B and C are in Youtube !
•  » » 5 weeks ago, # ^ |   0 wdym problem are on youtube?
•  » » » 5 weeks ago, # ^ |   0 Yes ! U can find them easily
•  » » » » 5 weeks ago, # ^ |   0 Link?
•  » » » » » 5 weeks ago, # ^ |   0
 » 5 weeks ago, # |   0 I think I solved E during contest but was lazy to implement (though might TLE in theory). Tell me what you think.I looked at the doors as a layered graph. Each layer has 2 nodes (doors), and there are only edges between nodes of adjacent layers (the distance in the matrix between the doors of consecutive layers). So in total there are 4 edges between 2 layers. Now for the preprocessing, I want to calculate the distance between the doors of special layers (0 with 300, 300 with 600, 600 with 900). I'm using 300 but actually I would take sqrt(10**5). This is a simple DP such that in the end each node in each layer has a pair (d1,d2), where d1 is the distance from the first node (corresponding to top door) in the previous special layer, and d2 is the distance from the second node (corr. to right door) in the previous special layer.Observe there is never any need to travel back and forth between layers. Only one direction.So now, assume I get a query (x1,y1), (x2,y2). Suppose the first is in layer i, and the second in layer j. All I need is to calculate the distance from x1,y1 to both doors in layer i, then. Then use my preprocessing to calculate the distance from doors of layer i to both doors of layer j (4 distances), and then calculate the distance from both doors of layer j to (x2,y2). This could take up to 900 operations per query (300 for layer i to special naively, 300 for special to special using preprocessing, and 300 for special to j naively). But notice that if you do the preprocessing in both directions, this can be done in 302 operations per query (the distance to the next/previous special layer can be done in one operation). Of course this isn't really 302, but more like 302 * 4? (because every calculation I consider 2-4 different options?). So it might be TLE, but it might just work. I'll probably try to implement later and see ^_^
•  » » 5 weeks ago, # ^ |   0 Yes, it is called SQRT-decomposition and should work with $10^5$, but as you noticed, it depends on realization.It's better to make some const $X = 300$ and use this value for pre-calculating, calculating an answer. Then you will be able to play with this number to get the best result (usually it's less than $\sqrt{N}$, about 250).P.S. I think $6s$ time limit was done specially to pass such solutions.
•  » » » 5 weeks ago, # ^ |   0 Oh didn't notice the 6 seconds! Thanks for advice :)
 » 5 weeks ago, # |   0 can anyone try to hack my code for problem D : 158229663
 » 5 weeks ago, # | ← Rev. 2 →   0 Is it possible to solve $F$ using centroid decomposition? I tried to write it, but couldn't do it in time and don't know, will it work.Also, has anyone noticed, that during contest "cses.fi" went down? I only loaded my submission there for a centroid decomposition problem, and after several minutes the site stopped working.
•  » » 5 weeks ago, # ^ |   +6 Yes. But not a good implementation though.https://codeforces.com/contest/1681/submission/158227788
 » 5 weeks ago, # |   +2 I can't control myself to complain the weak pretests of problem D. A way to express this feeling is to hack myself :(
 » 5 weeks ago, # | ← Rev. 4 →   +4 If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints. A: Game with Cards B: Card Trick C: Double Sort D: Required Length E: [Labyrinth Adventures: Under maintenance F: Unique Occurrences If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).
•  » » 5 weeks ago, # ^ |   +3 Could you please a provide a failing test case for 158212087. It got hacked.
•  » » 5 weeks ago, # ^ |   0 Problem E checker is wrong, it's printing invalid testcases.
•  » » » 5 weeks ago, # ^ |   0 Thanks for letting me know. I will fix it soon.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Can you provide a counter example for https://codeforces.com/contest/1681/submission/158166501?
 » 5 weeks ago, # | ← Rev. 2 →   0 please try to hack this one , my solution is already hacked , i just want to confirm whether my new solution is correct or not. link-158229941 thanks in advance.
•  » » 5 weeks ago, # ^ |   +1 Hacked with Ticket 7282
 » 5 weeks ago, # |   +11 For D why a DFS with memoization works? From any starting number x you just multiply it with {2, ..., 9}, and there are only 4 prime numbers in that set: 2, 3, 5, 7.That means you actually just multiply x with those four prime numbers and in the worst case you start from 1 and use 64 multiplications with 2. But some of those 64 multiplications can be 3, 5, 7 as well. So that is really at most 64^4 (imagine you divide 64 positions into four segments for 2, 3, 5, 7). The real number will be much smaller because for 3, 5, 7 you probably don't need 64 multiplications.
 » 5 weeks ago, # |   0 SpeedForces, in two consecutive days QAQ SPEED IS NOT MY FORTE It's shocking that a D problem can be solve by brute force?? I'm trying to do recursion or dp, without even thinking that this problem can be sooooo easy! and I am sad that I mistake $bj$ to $bj_{th}$ in problem B.and I am sad that because my func for sort() returns false when two elements are equal, I received 3 Runtime Error..
•  » » 5 weeks ago, # ^ |   0 You're not alone being sad. lol
 » 5 weeks ago, # |   +3 My only bug on E was forgetting to initialized my binary lifting array with INF...easily the stupidest bug I've made out of not solving one of the hardest problems in a contestI also find it kind of funny that samples didn't even catch this bug
 » 5 weeks ago, # |   0 how to solve C?
•  » » 5 weeks ago, # ^ |   0 by using Bubble Sort
 » 5 weeks ago, # |   +5 I solved problem D using recursion + memoization. only prime numbers which will be multiplied by x are only 2,3,5 and 7 and each prime number occurrence will not be more than 60,40,24,28 respectively. so we can memoize the count of each prime number.
 » 5 weeks ago, # |   0 awoo my 1st submission on D is wrong on sample test case 2, then why I am getting a penalty when my solution is wrong on the sample case? Isn't sample test cases free of penalties?
•  » » 5 weeks ago, # ^ |   +25 Only the first sample is free of penalties.
•  » » » 5 weeks ago, # ^ |   -9 nice pfp
 » 5 weeks ago, # |   +8 Can solve F more directly using a dynamic tree supporting subtree aggregates, such as this. Just cut/compute/link the edges for each color.
 » 5 weeks ago, # |   0 I solved problem D with a dp approach. https://codeforces.com/contest/1681/submission/158204160 dp[size of number][mask][distance from the original X] = max number with this mask.I have a mask of all of the digits that are present in the number.So if I have a number 1434, digits 1 3 4 are present and current mask is equal to 2^1 + 2^4 + 2^3 = 26I used an assumption that if we consider all of the numbers with the same size and mask, we should always pick the biggest one. I am not sure about this assumption, I was not able to prove that is really always profitable to always pick the biggest number.
•  » » 5 weeks ago, # ^ |   0 My approach was similar to you; however, I didn't used mask but one of the digits existed in that number. "Wrong Answer on test 13 T_T"
 » 5 weeks ago, # |   0 why this recursive solution to problem D doesnt work? link
•  » » 5 weeks ago, # ^ |   +3 Input4 34  Expected Output3  Your Output4 
 » 5 weeks ago, # |   -21 from a rank of 2000. to a rank of nearly 6500. after a solution get hacked is worst feeling ever for a coder. why don't they make proper pretest
•  » » 5 weeks ago, # ^ |   +30 hacking is a part of educational round.
 » 5 weeks ago, # |   0 used 3 hours to solve F with smaller to larger technique and get passed 2 hours after the contest. Made so many mistakes to count the number and contribution. Anyway, next time I might be better. How will you rate E and F?
 » 5 weeks ago, # | ← Rev. 2 →   -15 k
•  » » 5 weeks ago, # ^ |   0 it's 13 42 not 12 42
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 ohhhh
 » 5 weeks ago, # |   -13 Solved d using bfs and bigint, LMAOOO
 » 5 weeks ago, # |   0 NEED A Counter TESTCASE: https://codeforces.com/contest/1681/submission/158235552
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 42 2 2 12 2 1 1your code giving -1 as output
•  » » » 5 weeks ago, # ^ |   0 thanks
 » 5 weeks ago, # |   0 try hacking this 158235750
 » 5 weeks ago, # | ← Rev. 4 →   +2 Me: struggle with all my might in yesterday's round #793, solving one task for the entire contest, -131 ratingAlso me: solve ABCD in the first 26 minutes today and run away to work because I didn't have time for this shit from the very beginning. Predicted rating +203I'm stable like a stablecoin
•  » » 5 weeks ago, # ^ |   +1 Interesting. Perhaps you should always do contests before your work, so you can push yourself to solve problems very fast and then you can run away to work :)(of course, just kidding)
 » 5 weeks ago, # |   -7 Question D, if you use dfs to solve this problem, pay attention to this, if the front is 2 and the back is 4, the number of steps *2*2 will be more, but *4 cannot enter because it has already accessed this number
•  » » 5 weeks ago, # ^ |   0 WHat?
 » 5 weeks ago, # |   +7 Nice tests on E without int overflow, did some hacks with it.
 » 5 weeks ago, # |   0 Can somebody please explain C ?? also, i wasn't able to solve 'column swapping' in Round #794 (div1 + div2) , these are similar, right?? i think just saving the swapped elements in arr / vector was the difference.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +7 And they say time travel is impossible
 » 5 weeks ago, # | ← Rev. 2 →   +1 I really amazed about problem D! how a single bfs with visit array make this code accepted without TLE, what is the time complexity of the previous code? or there is a failing test case which make it TLE?
 » 5 weeks ago, # | ← Rev. 4 →   -26 deleted
 » 5 weeks ago, # |   0 I think D problem in this round is most hacked problem I have ever seen till now. It has changed so many rankings up and down. As I have also hacked 7 submission of D problem.
•  » » 5 weeks ago, # ^ |   0 whats the testcase? my d also got hacked. https://codeforces.com/contest/1681/submission/158189337
•  » » » 5 weeks ago, # ^ |   +6 you can see testcase on which your solution was hacked under show judge protocol option.
•  » » » » 5 weeks ago, # ^ |   0 but where to find that option
•  » » » » » 5 weeks ago, # ^ |   0 You have to go to your submission by clicking on # button.
•  » » » 5 weeks ago, # ^ |   0 It is 12 10000000000
 » 5 weeks ago, # |   +2 System test has already passed ?
•  » » 5 weeks ago, # ^ |   0 I am wonderning too ??
•  » » 5 weeks ago, # ^ |   0 same question
•  » » 5 weeks ago, # ^ |   +2 I'm not sure if my assumption is correct, but if the new test cases will be added to the original ones then the answer is no because problem D is still showing 66 test cases, which is the number of the original test cases.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 why you think new test cases won't included and no re-run the system test again.
•  » » » » 5 weeks ago, # ^ |   0 What I meant is that if the new test cases will be added to the original ones this means that we will have a number > 66 test cases for problem D and I can still see that problem D has 66 test cases, and if I'm not mistaken then they didn't run the system test yet.
•  » » » » » 5 weeks ago, # ^ |   0 Gotcha, thanks
 » 5 weeks ago, # |   0 About to submit C and then my Wifi decided to not work!
 » 5 weeks ago, # |   0 Can anyone plz tell how to solve F using dynamic connectivity ?
 » 5 weeks ago, # |   0 Is rating calculation still going on or it has been decided to become unrated even for Div. 2?
•  » » 5 weeks ago, # ^ |   0 After participating in almost 5 educational rounds you haven't realized that this series of contests rating always come late??!
•  » » » 5 weeks ago, # ^ |   0 Yeah it was late on previous contest but I didn't check the graph on those contest.Since it displayed as "unrated" on my graph so I was wondering if some new announcement was made.
 » 5 weeks ago, # |   +6 When will the tutorial open? The hacking phase is over ig
•  » » 5 weeks ago, # ^ |   0 same question
•  » » 5 weeks ago, # ^ |   0 System testing is in progress now, it should take a while.
•  » » » 5 weeks ago, # ^ |   0 oh ok, thanks
 » 5 weeks ago, # |   0 Why so many downvotes?
•  » » 5 weeks ago, # ^ |   +1 I think it's because peoples are waiting tutorial/uprate too much
 » 5 weeks ago, # |   0 Hope quick tutorial!
 » 5 weeks ago, # | ← Rev. 2 →   0 If you got hacked (TLE) in problem C, it's probably because of an I/O issue.
•  » » 5 weeks ago, # ^ |   0 yes, it is. this is my first time got TLE because of I/O, I just use java with Scanner.
 » 5 weeks ago, # |   +12 Even my grandma runs faster then the rating update system. Lol XD
•  » » 5 weeks ago, # ^ | ← Rev. 5 →   +6 desperately waiting for the rating update
•  » » » 5 weeks ago, # ^ |   +7
 » 5 weeks ago, # | ← Rev. 2 →   +3 When you wait for the rating change:
 » 5 weeks ago, # |   +6
•  » » 5 weeks ago, # ^ |   0 Me who is going to become expert right now. Having a lot of adrenaline rush. Can't wait anymore now .
•  » » » 5 weeks ago, # ^ |   0 Me too.
•  » » » » 5 weeks ago, # ^ |   0 Bro Your graph and solve count is so inspiring . You must be my friend . I have made you my friend . :_:
•  » » » » » 5 weeks ago, # ^ |   0 Thanks! I made you my friend too.
•  » » » » 5 weeks ago, # ^ |   0 I think your graph is so inspiring, too.If someone is going to be an expert, it must be you. XD
•  » » » » » 5 weeks ago, # ^ |   0 I didn't like my graph at all because I got stuck in gray and green for long period. But seeing you guys saying that my graph is inspiring really made my day! Thanks!
•  » » » » 5 weeks ago, # ^ |   +2 Me as well. :)
•  » » » » 5 weeks ago, # ^ |   +1 yeah, holy crap. Lots of effort, you definitely deserve expert!
•  » » » » » 5 weeks ago, # ^ |   0 Thanks!
•  » » » » » 5 weeks ago, # ^ |   +4 Bro prioritize upgrading the grand warden.
•  » » » » » » 5 weeks ago, # ^ |   0 Yeah this was my first thought too ...
•  » » » » » » 5 weeks ago, # ^ |   0 it's an outdated pic, hes like level 11 or smth now
 » 5 weeks ago, # |   +16 My dad has returned with the milk already.
•  » » 5 weeks ago, # ^ |   +1 so drink that and have asleep
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I Think your don't get the Joke. Is's the classic british Dad joke.. Google it :_:
•  » » » » 5 weeks ago, # ^ |   +1 Yeah, I got that.
 » 5 weeks ago, # |   +2 -1 votes right now, and it keeps decreasing.
 » 5 weeks ago, # | ← Rev. 3 →   0 MikeMirzayanov awoo submission 158171922 and submission 158186561 are nearly same and its a pure co-incidence neither i know the person nor i used any online IDE and question was pretty brute force so its obvious to have same kind of solution and further more I have no history of such offence and i personally hate cheaters . This kind of things demotivates a lot please look into the matter.
•  » » 5 weeks ago, # ^ |   0 Bro, You have a same problem as me(
•  » » 5 weeks ago, # ^ |   0 question was pretty brute force
 » 5 weeks ago, # |   -10 Idk why ppl are downvoting this contest . I find Task great . Just because of fst ??
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   -10 #define fst pls
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   -9 #define fst "FAILED SYSTEM TEST" 
 » 5 weeks ago, # | ← Rev. 3 →   -25 I got my ans similar of C to somewhat 100 people; tell me it isn't possible that too many people do the question with the same approach? IDK why my answers are being skipped. I did not use an online IDE or something that would leak my code. It's too bad; after 2 hrs of brainstorming, you just skipped my question, with no-fault. It is a correct ans, and that's why so many people have the same approach. awoo MikeMirzayanov adedalic BledDest
•  » » 5 weeks ago, # ^ |   -24 Exactly its a simple solution and many people can have it
•  » » » 5 weeks ago, # ^ |   0 Yus they should not be skipping our answers
 » 5 weeks ago, # |   -14 Codeforces is considering me responsible for the mistake that I have never made.Actually I was sitting in a public library while competing in this round.I guess someone has copied my solutions by continously peeping into my laptop without informing me. I have not indulged myself in any such activities and I always beleive in right conduct.For reference you can check my submission timings and code. I beleive codeforces won't do injustice to me.
•  » » 5 weeks ago, # ^ |   +1 aren't you responsible for keeping your code safe?
 » 5 weeks ago, # |   +2 I finally become expert after 1 year . Cheers
•  » » 5 weeks ago, # ^ |   0 congratulations
•  » » » 5 weeks ago, # ^ |   -10 Thanks Bro . You too for becoming cm!!
•  » » 5 weeks ago, # ^ |   -7 me too.. after 5 months
•  » » 5 weeks ago, # ^ |   -10 Congratulations!
•  » » » 5 weeks ago, # ^ |   -10 Thank you Brother !!
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   -10 Congratulations, well deserved. :)
 » 5 weeks ago, # |   -10 How on Earth did I pass pretest with accidentally typing "int" in memoization for D task?
 » 5 weeks ago, # |   -10 Why does my submission(158304624) for C give WA ("Arrays are not sorted")? My approach is to store each pair of $a_i$ and $b_i$ for both sorted and original arrays and compare all pairs, since pairs can't change, and then use a simple bubble sort to print swaps. I tried testing it on cfstress but it didnt give me any counterexamples(link).
 » 5 weeks ago, # |   -9 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 Can anyone tell why I haven't received the ratings for this contest yet... I am in div 2 (920 ratings)
•  » » 5 weeks ago, # ^ |   +1 Your Last rating change was +13, after this round. So, you're
 » 5 weeks ago, # |   0 Reached specialist because of this contest, thank you :).
 » 5 weeks ago, # |   -6 Well, finally i got my color back. Now i need to get back my rating! xD
 » 5 weeks ago, # |   0 In Educational Codeforces Round 129 (Rated for Div. 2) my rating drops 112 and cause is violation rules break. But I don't do anything wrong. First Thing First, In the contest time I didn't Copy and Paste code of others. I don't know in which part my solution is similar to others. I don't see others code. I have my solution. How do I know my code is similar to others in contest time? I don't know this thing. How my code is similar to others? how do I know. That is my code, I write it, I thought about it and i solved it by my own. And My rating drops. Drops 112. Please check my code and tell me how do I know My code is similar to others. It's my code and that's my evidence. Why you cut my ratings?Give me back my ratings. I didn't do any cheat and System's claim is actually wrong
 » 5 weeks ago, # |   +3 awoo MikeMirzayanov Yestarday, I recieved a letter from Codeforces System in which it was written that my solutuion 158183564 is similar to Boboge's solution 158175797. We weren't communicating with each other. It's just an coincidence. Both of us used simple implementation of classic bubble sort and well-known C++ STL functions. Please, review your verdict P.S. I didn't use any online IDE, just CLion.