#  User  Rating 

1  Benq  3813 
2  tourist  3768 
3  maroonrk  3570 
4  Radewoosh  3535 
5  fantasy  3526 
6  jiangly  3523 
7  Um_nik  3522 
8  orzdevinwang  3441 
9  cnnfls_csy  3427 
10  zh0ukangyang  3423 
#  User  Contrib. 

1  awoo  180 
2  isthisfft  178 
3  nor  169 
4  Um_nik  168 
5  SecondThread  164 
6  maroonrk  163 
7  adamant  162 
8  kostka  161 
9  YouKn0wWho  158 
10  antontrygubO_o  154 
+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 lowdiv1. 
+88
We all hope she will agree! What's her account? We will follow her progress. 
+78
delicious 
+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. 
+38
done 
+36
After I process cheaters. At most 1 day. 
+36
Skill issue 
+29
Sorry for my bad sense of humor 
+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) 
+26
The answer is [1, n] 
+24
Thanks! 
+23
I agree too. Thanks for the so insightful comment 
+22
agree 
+22
Hack on problem D: Input:
Expected output:
Output of hacked solution:

+22
maroonrk please add this into the after contest tests 
+22
thaknss fo4r th1s awsoeme edutiroal! 
+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. Image Now 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. 
+19
That's such a bad strategy for improvement 
+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! 
+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%. 
+19

+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
whaaaaat? 
+17
Be clear man how much did you enjoy the problems? 
+17
I agree!Fuck the dirty liers!!! CF is a platform to learn CP but not for you bitch cocksuckers to defile! 
+17
your code didn't compile. can you fix it? 
+16
L 
+16
"a lot" xD 
+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 
+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+i1}{i}x^i$$$, and then use NTT convolution. 
+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. 
+14
Very gut tutoral. Pleas more 
+14

+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) 
+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. 
+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
The heck is a? the heck is v? the heck is s? Why the list of edges is h? 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 
+12
in your head 
+11
What is JSON. 
+11
Where do i run this code? 
+11
ay dond undstersatnd pls fhelp 
+11
too difficult to understand, had to go through a grad level linear algebra textbook to even understand the notation. downvoted ù_ú 
+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? 
+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. 
+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? 
+10
lmao 
+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 
+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 So following codes can run successfully and print
I recommend to use 
+10
sometimes you must step to the big mountain to stop feel small rocks under your feet... 
+10
I personally added the following in my template:
Then I just call 
+9
There is something wrong with your blog. 
+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 1e51 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
According to your profile , you are from Bangladesh. To be very honest but there are already 1012 potential participants form Bangladesh and they will serve Bangladesh for the next 2 or 3 years.They are practicing for last 34 years and it is quite hard to acquire higher skills than them in a very short period of time.... And informatics Olympiads are not only about winning a medal , it is kind of learning process in which u are preparing yourself for the next generation of programming. Don't think about medal if you want to enjoy this journey , have fun and try hard. BTW , sorry for my bad English. 
+8

+8
Here is my more detailed solution to F: We start with a wellknown 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 (1i/N)$$$. Let's consider nonnegative integer sequences $$$T = t_0, \ldots, t_{N1}$$$, then the expected value of $$$m$$$th power is 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 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 The Mellin operator satisfies the general Leibniz rule for derivatives too, so for nonnegative integer sequences $texfix$ $$$E = e_0, \ldots, e_{N1}$$$, we get swapping sums to simplify 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: where $texfix$ $$$P(x) = \prod_{i=1}^{N1} \left(x  \frac{i}{N}\right)$$$. We know how to calculate $$$P(x)$$$ by multiplying $$$N1$$$ 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 oddindexed 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$$$? Let's rephrase the final sum in the following way: we have $$$D=N1$$$ 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. 
+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 4year old blog! Go have a life instead. It's also impolite! 
+8
cout all variables 
+8
n1ec bolg, nwo 1 c4n b3 a lgm in 23 s3c0nds 
+8
Y er porbly ritgh 
+8
As of 1 hour ago it is January 31 UTC12 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. 
+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. 
+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!) 
+8
So you did watch the video? 
+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 . 
+7
u remind me of myself 
+7
yeah, but starting competitive coding/math competitions etc at an early age makes you more interested in academics and hence very useful imo. 
+7
If somebody want to see the codes. Problem E — Query Color Problem F — Shanks Test Problem D — The Ancient Tree 
+7
Sleep before the contest for 1 hour or something. Get up at 21:40 to avoid drowsiness during contest. 
+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. 
+6
He didn't want any answers, but only downvotes. 
+6
BRO UPDATE : reached pupil 
+6
CodeChef was dead when Unacademy took over it 
+6
When will the plagiarism check run? 1787C, Remove brackets was leaked on youtube and many cheaters did it disrupting the standings. 
+6
Auto comment: topic has been updated by tallbee23 (previous revision, new revision, compare). 
+6
you got a little too far but i like the point 
+6

+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. 
+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. 
+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 :( 
+5
You got me ;) 
+5
I don't need upvotes, I want to improve :) 
+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. 
+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 ! 
+4
Seems the problem is about maximum bipartite matching. 
+4
Congrats 1st place 
+4
371 rating XD ChatGPT, you can do better 
+4
We are waiting for interesting tasks of your competition. I wish you all good luck. 
+4
Veyr ince epxlantaion, txh! 
+4
When you reach a higher level you must perform better than before 
+4
Ve 
Name 
