Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

 +204 This is an interesting blog post but let's not ignore that you have a small sample of div1 rounds. You should know segment trees, hashes, and shortest paths — those do appear in CF low-div1.
 On chenye3N → How Can I Persuade My Mother to Join Codeforces Contest?, 46 hours ago +88 We all hope she will agree! What's her account? We will follow her progress.
 On speedy_boy → What a bad luck for Radewoosh, 46 hours ago +78 delicious
 On speedy_boy → What a bad luck for Radewoosh, 41 hour(s) ago +67 I was not planning to participate at all since the contest ends after 2am. I just opened the problems right before I sleep, but after seeing problem H I became very confident to solve it easily, so I just participated in it. The day was a bad day (I was especially sleepy that day), and I ended up sleeping pretty late, today I was struck with strong migraine :(
 +46 If G feels like huge work to you, I don't think you are able to judge that problem
 +43 I have a different solution for problem $G$.The idea is to run a BFS and label the edges according to when they were processed by the BFS. Below, I have the tree, with the edge colors and labels.Now, we can turn these edge labels into color labels. Define the label of a color to the minimum label of one of its edges. For instance, the label of the red path is 1, and the label of the yellow path is 18. The label of the purple color is 13.Now, whenever we perform an update (blocking or unblocking a node), we are updating at most two continuous range of labels. Say, for instance, we update the root of the tree. Then, we're blocking "red" and "blue" (label 1 and 2). If we were to update the node from which edges 4,5,6 protrude, then we're blocking "red" and "blue (4 and 5).Now, updating continuous ranges of intervals can be done with a segment tree. Let the index of the segment tree be the label of each color. So segmentTree[label[i]] = sum of weights of path with color i.Each time, we block some "path", we can subtract a big number from that contiguous range of the segment tree. Each time we unblock that path add back that big number. Now, it's just range minima of whole segment tree and range add.
 On maroonrk → AtCoder Regular Contest 155 Announcement, 42 hours ago +38 done
 On rsj → TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!), 45 hours ago +36 After I process cheaters. At most 1 day.
 On speedy_boy → What a bad luck for Radewoosh, 42 hours ago +36 Skill issue
 +29 Sorry for my bad sense of humor
 On 0000iq → I give up., 32 hours ago +29 Yes. Totally agree, also it may workout if you cheat like Big_Soul cheated in many rounds and got caught in on Codeforces Round #799 (Div. 4), Codeforces Round #804 (Div. 2), CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!), Educational Codeforces Round 141 (Rated for Div. 2)
 On Rodionno → Strange segment task, 35 hours ago +26 The answer is [1, n]
 On speedy_boy → What a bad luck for Radewoosh, 46 hours ago +24 Thanks!
 On bajelega → 1787-C leaked on YT during contest, 17 hours ago +23 I agree too. Thanks for the so insightful comment
 On speedy_boy → What a bad luck for Radewoosh, 46 hours ago +22 agree
 On maroonrk → AtCoder Regular Contest 155 Announcement, 45 hours ago +22 Hack on problem D:Input: 6 2 2 6 15 30 30 Expected output: Takahashi Takahashi Aoki Aoki Aoki Aoki Output of hacked solution: Takahashi Takahashi Aoki Aoki Takahashi Takahashi
 On maroonrk → AtCoder Regular Contest 155 Announcement, 44 hours ago +22 maroonrk please add this into the after contest tests
 On tallbee23 → xor basis tutorial, 22 hours ago +22 thaknss fo4r th1s awsoeme edutiroal!
 On Vladosiya → Codeforces Round #847 (Div. 3) Editorial, 17 hours ago +22 Another way to prove your claim is by thinking about the euler tour of a tree.Intuition: It's straightforward to calculate the maximum value of the minimum distance between any two elements after some $K$ operations in the case of a list instead of a tree. So let's try to represent the "tree like a list".Your claim would have been trivial if we were given a list instead of a tree in the problem. You can "transform" a tree and represent it using the list of nodes visited during the euler tour of the tree. The difference of position between any two elements in the list will always be greater or equal to the actual distance between the nodes (that are being represented through those elements) in the tree. Like in this case, the difference in position between nodes 6 and 1 is 4, whereas the actual distance is 3. ImageNow we have a list of $2N - 1$ elements, and we know that even if these elements were independent of each other (same node does not appear in the list twice), the answer would be bounded by $\lceil\frac{2N - 1}{K}\rceil$.Note The bound works for the tree as well because we know whatever the answer for our list is, the actual answer for our tree is lesser or equal.
 +21 I don't agree that F was huge work. It was fine for that slot.
 On chenye3N → How Can I Persuade My Mother to Join Codeforces Contest?, 47 hours ago +19 That's such a bad strategy for improvementIf you want to solve 1-2 appropriately rated problems, just upsolve
 On chenye3N → How Can I Persuade My Mother to Join Codeforces Contest?, 41 hour(s) ago +19 Well,thank you for this post.I am 14 and live in YN.I found that I am really lucky to have such kind and understanding mom.When I take part in a CF contest,although she always says that she will leave me to sleep,but each time she always she stays up with me till I finished.My mom is always there to listen to me and encourage me to do what I like.Even in the weakest province of OI and I do not have a C++ teacher,I still can get good grades in CSP.My mom plays an important part in my improvement.Perhaps this is common in your country,but my mom is one of those rare parents like this in China.Thanks,mom!
 On chenye3N → How Can I Persuade My Mother to Join Codeforces Contest?, 41 hour(s) ago +19 You understand that chances of him getting in china IOI team is exceptionally low right? If he is very smart — low chances. otherwise 0%.
 On appu_nitd → Invitation to RECode 25.0, 36 hours ago +19 Unofficial Hints
 On bajelega → 1787-C leaked on YT during contest, 13 hours ago +18 How much would your rating really change by these cheaters? I feel like most of the time it's cope. Think I would've lost delta regardless of cheaters last round
 +17 Problem B: Miller-Rabin, Pollard's rho algorithmwhaaaaat?
 On Shefin_ → Codeforces Round #848 (Div. 2), 34 hours ago +17 Be clear man how much did you enjoy the problems?
 On bajelega → 1787-C leaked on YT during contest, 23 hours ago +17 I agree!Fuck the dirty liers!!!CF is a platform to learn CP but not for you bitch cocksuckers to defile!
 On tallbee23 → xor basis tutorial, 22 hours ago +17 your code didn't compile. can you fix it?
 On 0000iq → I give up., 34 hours ago +16 L
 On Shefin_ → Codeforces Round #848 (Div. 2), 22 hours ago +16 "a lot" xD
 On adityav664 → How be better at problem solving skills?, 13 hours ago +15 A lot of the time "problem solving" isn't coming up with a new thing, it's having seen something similar before. Solve more problems.
 +14 thanks i wanted to post the same list "how i became a master" but forgot
 On Shefin_ → Codeforces Round #848 (Div. 2), 43 hours ago +14 As a Robot, I will be taking place in the Round. Don't get scared Humans.. -- ChatGPT
 +14 Consider the OGF form of the array as $F(x)=\sum\limits_{i=0}^{\infty}a_ix^i$.For a generating function to do a prefix sum, just multiply it by $\sum\limits_{i=0}^{\infty}x^i$.So to do k times prefix sum just multiply by $(\sum\limits_{i=0}^{\infty}x^i)^k=\sum\limits_{i=0}^{\infty}\binom{k+i-1}{i}x^i$, and then use NTT convolution.
 On Everule → How to prove your solutions in Competitive Programming, 34 hours ago +14 I feel like Problem E from yesterday's contest belongs here, since many people (including myself) solved it without proving the construction always works.
 On tallbee23 → xor basis tutorial, 21 hour(s) ago +14 Very gut tutoral. Pleas more
 On adityav664 → How be better at problem solving skills?, 13 hours ago +14
 On chenye3N → How Can I Persuade My Mother to Join Codeforces Contest?, 41 hour(s) ago +13 Is 0:35 too late for sleeping ? (Seems like a lot of Chinese people go to sleep after 0:00 , you can try to take a nap at noon to avoid drowsiness)
 On chenye3N → How Can I Persuade My Mother to Join Codeforces Contest?, 37 hours ago +13 Just same to me, i'm from Vietnam and when contest starts it's 21:35, I only have 1 hours to solve problem before my mother forced me to go to bed.
 On jerefigo → Click here if you want to know your future CF rating, 37 hours ago +13 Nice to see my idea being put into something more practical, even after this long.Well done jerefigo!
 +13 Here am I with my toxic grumblings about the quality of editorials again. Nothing new, I just decided to try reading editorials again and once again I ask myself why the editorial authors hate their readers so much.I'm just opening the solution for D and the first thing I see is int a[N], v[N], s[N]; struct E { int to; E *nex; } *h[N]; The heck is a? the heck is v? the heck is s? Why the list of edges is h?Probably it should be relatively easy for the typical audience of this problem to deduce that E means edge even if you don't care about the others, but a/v/s/h is just too much. I won't even ask why you needed a linked list. As a result, decoding and deobfuscating the heck is written in the "author's solution" easily competes by difficulty with the original problem.I understand that codeforces doesn't enforce the quality of editorials and it is done by putting the minimum effort possible, but put at least the minimum effort into making it readable, this is so below any bar.I find it hard to comprehend that people spend some supposedly huge amount of time on coming up with and polishing those problems, but cannot find some minutes to make the code they just submitted at least a bit readable before attaching to the editorial
 On Pakgamer2022 → What is API., 43 hours ago +12 in your head
 On Pakgamer2022 → What is API., 45 hours ago +11 What is JSON.
 On Pakgamer2022 → What is API., 44 hours ago +11 Where do i run this code?
 On tallbee23 → xor basis tutorial, 21 hour(s) ago +11 ay dond undstersatnd pls fhelp
 On tallbee23 → xor basis tutorial, 20 hours ago +11 too difficult to understand, had to go through a grad level linear algebra textbook to even understand the notation. downvoted ù_ú
 On jerefigo → Click here if you want to know your future CF rating, 36 hours ago +10 Thank you!!, It means a lot coming from you.I'm guessing you used a more complex method for prediction, right? Could you share some insight as to how to improve the current model?
 On jerefigo → Click here if you want to know your future CF rating, 36 hours ago +10 I used only my stock trading knowledge and some gut feelings, no code was involved at all.I think you can try to use some geometrical knowledge to improve this project, that would be a good start.
 On jerefigo → Click here if you want to know your future CF rating, 35 hours ago +10 Oh, very interesting!Well, I don't have much geometrical knowledge besides the CSES geometry section haha, can you name drop some concepts that could be helpful for the project?
 On AndreyPavlov → Codeforces Round #846 (Div. 2), 28 hours ago +10 lmao
 On chenye3N → How Can I Persuade My Mother to Join Codeforces Contest?, 28 hours ago +10 Same for me, the timing is weird for me, contests at the end of the day is tiring. Why must it always be at the same time? The time should be randomized
 On rsj → TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!), 24 hours ago +10 The most interesting is that you get Accepted on main tests when contest was running. You are so unluckily!I see your code. You got RE because you visit the wyn[0] when it is empty. It is UB. Notice std::vector::clear() do not free memory. So it will only get RE when it is the first case sometimes.So following codes can run successfully and print 2 0 (GNU G++14 6.4.0 on Custom invocation of CodeForces): #include using namespace std; int main(){ vector a; a.push_back(1); a.clear(); a[0]=2; printf("%d %d",a[0],a.size()); return 0; } I recommend to use vector().swap(a) to clear the vector a with freeing memory. However, it spends more time because it frees memory.
 +10 sometimes you must step to the big mountain to stop feel small rocks under your feet...
 On snowmanonahoe → Simpler unhackable random numbers, 4 hours ago +10 I personally added the following in my template: mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count()); int rnd(int x, int y) { return uniform_int_distribution(x, y)(rng); } Then I just call rnd(l, r) to get a random integer between $l$ and $r$ inclusive.
 On Pakgamer2022 → People didn't reply. Why?, 19 hours ago +9 There is something wrong with your blog.
 On Anti_tourist4000 → tle on problem b, 47 hours ago +8 My bad. At first I though that you changed the array size from 1e6+5 to 1e5. Yes here the last index in the array is 1e5-1 so reaching 1e5 can result in RTE. That's why I always add some extra indices in my arrays.
 +8 Can someone please explain me the proof of E and why this solution works?
 +8 Ironic considering his initial takeaway 😂
 +8 here
 On maroonrk → AtCoder Regular Contest 154 Announcement, 40 hours ago +8 Here is my more detailed solution to F:We start with a well-known approach. If exactly $i$ faces have been seen so far ($0 \le i \lt N$), the probability of seeing a new face after exactly $t+1$ tosses is $(i/N)^t (1-i/N)$. Let's consider non-negative integer sequences $T = t_0, \ldots, t_{N-1}$, then the expected value of $m$-th power is $a_m = \sum_{k \ge 0} (k+N)^m \sum_{T: \sum(T)=k} \prod_i \left(\frac{i}{N}\right)^{t_i} \prod_i \left(1-\frac{i}{N}\right) \,.$Let's define functions $texfix$ $p_i(x) = \sum_{t \ge 0} \left(\frac{i}{N}\right)^t x^t = 1/\left(1-\frac{ix}{N}\right)$. Then with some new notation we have $a_m = \prod_i \left(1-\frac{i}{N}\right) \sum_{k \ge 0} (k+N)^m \prod_i p_i(x) \quad [x^k] = C_{\prod} \sum_{k \ge 0} (k+N)^m F(x) \quad [x^k]$where $[x^k]$ denotes the coefficient of formal series at $x^k$. Next, we can notice that $(k+N)^m F(x) [x^k]$ is the coefficient of $x^{k+N}$ of the formal series $O^m \left(F(x) x^N\right)$, where $O = x \frac{\mathrm{d}}{\mathrm{d}x}$ is the Mellin operator, effectively just turning $x^k$ to $k x^k$. That means we can express $a_m = C_{\prod} \left[ O^m \left(F(x) x^N \right) \right]_{x=1} = C_{\prod} \left[ O^m \prod_i \frac{x}{1-ix/N} \right]_{x=1} \,.$The Mellin operator satisfies the general Leibniz rule for derivatives too, so for non-negative integer sequences $texfix$ $E = e_0, \ldots, e_{N-1}$, we get $O^m \prod_i \frac{x}{1-ix/N} = m! \sum_{E: \sum(E)=m} \prod_i \left(\frac{1}{{e_i}!} O^{e_i} \frac{x}{1-ix/N}\right) = m! \prod_i \left(\sum_{e \ge 0} \frac{1}{e!} O^e \frac{x}{1-ix/N} y^e \right) \quad [y^m] \,,$ $O^e \frac{x}{1-ix/N} = O^e \sum_{k > 0} \left(\frac{i}{N}\right)^{k-1} x^k = \sum_{k > 0} \left(\frac{i}{N}\right)^{k-1} k^e x^k \,,$swapping sums to simplify $\sum_{e \ge 0} \frac{1}{e!} O^e \frac{x}{1-ix/N} y^e = \sum_{k > 0} \left(\frac{i}{N}\right)^{k-1} x^k \sum_{e \ge 0} \frac{1}{e!} \left(ky\right)^e = \sum_{k > 0} \left(\frac{i}{N}\right)^{k-1} x^k e^{ky} \,;$from now on, let's omit $i=0$ since $p_0=1$ and it'd cause some annoying singularities. At this point we're not doing any more derivatives, so we can plug in $x=1$ and simplify further: $a_m = m! \, C_{\prod} \prod_i \left(\sum_{k > 0} \left(\frac{i}{N}\right)^{k-1} x^k e^{ky} \right)_{x=1} \quad [y^m] = m! \, C_{\prod} \prod_i \frac{e^y}{1-\frac{i}{N} e^y} \quad [y^m] = m! \, C_{\prod} \frac{1}{P\left(e^{-y}\right)} \quad [y^m] \,,$where $texfix$ $P(x) = \prod_{i=1}^{N-1} \left(x - \frac{i}{N}\right)$. We know how to calculate $P(x)$ by multiplying $N-1$ linear polynomials or do polynomial inversion easily, we just need the first $O(M+1)$ terms of the composite $y$-function $P(e^y)$ since flipping the sign of $y$ is just multiplying odd-indexed coefficients by $-1$.How to compose a polynomial with exponential? If $P(x) = \sum_{j=0}^D c_j x^j$ then $P(e^y) = \sum_{j=0}^D c_j e^{yj}$ and the $m$-th derivative is $\sum_{j=0}^D c_j j^m e^{yj}$, so the $m$-th (at $y^m$) coefficient of $P(e^y)$ is $\frac{1}{m!} \sum_{j=0}^D c_j j^m$. (You may notice the Mellin operator in this again.) For now, let's forget about the $1/m!$ factor that makes an exponential — we need the coefficients separately for each $m$ anyway. What function has coefficients $\sum_{j=0}^D c_j j^m$? $\sum_{m \ge 0} y^m \sum_{j=0}^D c_j j^m = \sum_{j=0}^D c_j \sum_{m \ge 0} (yj)^m = \sum_{j=0}^D \frac{c_j}{1-yj} = c_0 + \sum_{j=1}^D \left(\frac{-c_j}{j} \right) \cdot \left( y - \frac{1}{j} \right)^{-1}$Let's rephrase the final sum in the following way: we have $D=N-1$ linear polynomials $y-\frac{1}{j}$ for $1 \le j \lt D$, we multiply each coefficient $(-c_j/j)$ by all of them except $y-\frac{1}{j}$, take the sum, then multiply by the inverse of product of all $D$ linear polynomials. The "coefficient multiplied by all other factors" sum can be quickly evaluated the same way as Lagrange interpolation polynomial, with divide and conquer — recursively evaluate left half, multiply by the sum of all linear polynomials in the right half and vice versa, then take the sum.Together, we have time complexity $O(N \log^2 N)$ for product of linear polynomials and the "coefficient multiplied by all other factors" recursive sum, and $O(\max(N,M) \log M)$ for inversion and remaining multiplications.
 On Noble_Mushtak → Every Technique and Algorithm I Used to Become Grandmaster, 31 hour(s) ago +8 Btw you overkilled last contest's D, you can solve it with something like a topological sorting algorithm and nothing more.
 +8 why comment on a 4-year old blog! Go have a life instead. It's also impolite!
 +8 cout all variables
 On tallbee23 → xor basis tutorial, 21 hour(s) ago +8 n1ec bolg, nwo 1 c4n b3 a lgm in 23 s3c0nds
 On tallbee23 → xor basis tutorial, 20 hours ago +8 Y er porbly ritgh
 On xiaowuc1 → USACO 2022-2023 Second Contest, 17 hours ago +8 As of 1 hour ago it is January 31 UTC-12 so it is okay to discuss the contest now I believe. Did anyone who solved silver 1 have the idea to count cycles in the directed graph of letters? I implemented this over and over for two hours but couldn't pass any tests. Trying to figure out if my idea was wrong or my implementation was wrong.
 On xiaowuc1 → USACO 2022-2023 Second Contest, 17 hours ago +8 I cleared Bronze with -100 or 0 CF rating, but CF and USACO problems are different, I also know someone who passed without a CF account.
 On xiaowuc1 → USACO 2022-2023 Second Contest, 16 hours ago +8 Hi, I still had an hour left on my clock when I was doing my gold contest but it ended. Is it normal (I started too late) or is it an error ? Anyway, it does not matter since I am not in any country's IOI preparation. But I was about to submit two bruteforces and grasp some more points haha.edit : Also, I really enjoyed the problems (I was able to see the silver and gold ones!)
 On bajelega → 1787-C leaked on YT during contest, 8 hours ago +8 from striver and i follow the steps that he told in his video So you did watch the video?
 On 0000iq → I give up., 2 days ago +7 It's ok...if you have figured this out by taking proper amount of your personal data and knowledge of self!! You may be having a good potential for other thing s and world is much more than competitive programming ,it is ok if you have worked hard and it it didn't worked for you!! You tried,you learned,you discovered sport for yourself !! Be happy for that .
 On 0000iq → I give up., 47 hours ago +7 u remind me of myself
 On chenye3N → How Can I Persuade My Mother to Join Codeforces Contest?, 39 hours ago +7 yeah, but starting competitive coding/math competitions etc at an early age makes you more interested in academics and hence very useful imo.
 On appu_nitd → Invitation to RECode 25.0, 33 hours ago +7 If somebody want to see the codes.Problem E — Query ColorProblem F — Shanks TestProblem D — The Ancient Tree
 On chenye3N → How Can I Persuade My Mother to Join Codeforces Contest?, 19 hours ago +7 Sleep before the contest for 1 hour or something. Get up at 21:40 to avoid drowsiness during contest.
 On bajelega → 1787-C leaked on YT during contest, 9 hours ago +7 With this standard of plagiarism detection, you would get a lot of false positives every contest, I don't think its reasonable to expect for everyone to have different base cases and transitions in their dp, when over 1000 people solved it.I don't know much about how code similarity is measured and the expected differences, so I may be wrong.
 On Pakgamer2022 → What is API., 44 hours ago +6 He didn't want any answers, but only downvotes.
 On codor07 → starting 21/08/2022, 38 hours ago +6 BRO UPDATE : reached pupil
 On Shefin_ → Codeforces Round #848 (Div. 2), 37 hours ago +6 CodeChef was dead when Unacademy took over it
 +6 When will the plagiarism check run? 1787-C, Remove brackets was leaked on youtube and many cheaters did it disrupting the standings.
 On tallbee23 → xor basis tutorial, 22 hours ago +6 Auto comment: topic has been updated by tallbee23 (previous revision, new revision, compare).
 On bajelega → 1787-C leaked on YT during contest, 11 hours ago +6 you got a little too far but i like the point
 On bajelega → 1787-C leaked on YT during contest, 10 hours ago +6 Well, your solution 191154288 have the exact same structure (except some variables/arrays renames) to these submissions: 191151588, 191153282, 191150426 or 191139412. And literally half the C skipped submissions I checked were suspiciously similar... Sometimes is better to admit your mistakes...
 On appu_nitd → Invitation to RECode 25.0, 7 hours ago +6 More than 24 hours have passed but still codechef is not letting us to do it so. Could you please provide editorial or fix this problem asap ?
 +5 https://cses.fi/problemset/task/1716/I know this has direct math formula but I want to apply DP to it, I was able to reduce it to O(N*M) but on observation, it's just applying prefix sum repeatedly N times to [1, 0, 0...] of length M, so, I was wondering if we could generalize this for arbitrary array and find a particular element of it. which is the last element in above CSES one.
 On tallbee23 → xor basis tutorial, 17 hours ago +5 yur qurey si viod soo it caonot reutn bolo.
 +5 MikeMirzayanov, somehow the curly braces do not render correctly (or at all), please take a look.
 On xiaowuc1 → USACO 2022-2023 Second Contest, 16 hours ago +5 Were you able to solve the second one (light and switches one) ? I couldn't come up with any proper strategy to make both the strings equal in minimal moves :(
 On Mohamed_712 → -ve Vote, 16 hours ago +5 You got me ;)
 On newplayer5 → dp is hard?, 9 hours ago +5 I don't need upvotes, I want to improve :)
 On ZZ_ZZ → is that relation true ? , 8 hours ago +5 Yes, you can prove it too. For each bit it can be proven using the truth table, and follow through similarly for all 'n' bits.
 On newplayer5 → dp is hard?, 7 hours ago +5 As I can remember, DP was the hardest topic for me to understand, so it's alright don't give up!For the advice, always think about the slow recursion solution and try to optimize it with memoization (it's much easier for you to think about while you're still not that good in dp than iterative dp).Goodluck !
 On wonderful_trip → I have a question about a problem., 47 hours ago +4 Seems the problem is about maximum bipartite matching.
 On speedy_boy → What a bad luck for Radewoosh, 46 hours ago +4 Congrats 1st place
 On Shefin_ → Codeforces Round #848 (Div. 2), 41 hour(s) ago +4 371 rating XDChatGPT, you can do better
 On Shefin_ → Codeforces Round #848 (Div. 2), 38 hours ago +4 We are waiting for interesting tasks of your competition. I wish you all good luck.
 On tallbee23 → xor basis tutorial, 21 hour(s) ago +4 Veyr ince epxlantaion, txh!
 On hulupig → Why does the rating change become less and less?, 19 hours ago +4 When you reach a higher level you must perform better than before
 On Mohamed_712 → -ve Vote, 16 hours ago +4 -Ve