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

Top Comments

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.

We all hope she will agree! What's her account? We will follow her progress.

+78

delicious

On speedy_boyWhat 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 :(

If G feels like huge work to you, I don't think you are able to judge that problem

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.

done

After I process cheaters. At most 1 day.

+36

Skill issue

Sorry for my bad sense of humor

On 0000iqI 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 RodionnoStrange segment task, 35 hours ago
+26

The answer is [1, n]

+24

Thanks!

+23

I agree too. Thanks for the so insightful comment

+22

agree

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

maroonrk please add this into the after contest tests

On tallbee23xor basis tutorial, 22 hours ago
+22

thaknss fo4r th1s awsoeme edutiroal!

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.

I don't agree that F was huge work. It was fine for that slot.

That's such a bad strategy for improvement
If you want to solve 1-2 appropriately rated problems, just upsolve

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!

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_nitdInvitation to RECode 25.0, 36 hours ago
+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

Problem B: Miller-Rabin, Pollard's rho algorithm

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!

On tallbee23xor basis tutorial, 22 hours ago
+17

your code didn't compile. can you fix it?

On 0000iqI give up., 34 hours ago
+16

L

+16

"a lot" xD

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.

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

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.

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 tallbee23xor basis tutorial, 21 hour(s) ago
+14

Very gut tutoral. Pleas more

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)

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.

Nice to see my idea being put into something more practical, even after this long.

Well done jerefigo!

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 Pakgamer2022What is API., 43 hours ago
+12

in your head

On Pakgamer2022What is API., 45 hours ago
+11

What is JSON.

On Pakgamer2022What is API., 44 hours ago
+11

Where do i run this code?

On tallbee23xor basis tutorial, 21 hour(s) ago
+11

ay dond undstersatnd pls fhelp

On tallbee23xor 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 ù_ú

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?

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.

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

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

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<T>::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<bits/stdc++.h>
using namespace std;
int main(){
	vector<int> a;
	a.push_back(1);
	a.clear();
	a[0]=2;
	printf("%d %d",a[0],a.size());
	return 0;
}

I recommend to use vector<int>().swap(a) to clear the vector a with freeing memory. However, it spends more time because it frees memory.

sometimes you must step to the big mountain to stop feel small rocks under your feet...

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<int>(x, y)(rng);
}

Then I just call rnd(l, r) to get a random integer between $$$l$$$ and $$$r$$$ inclusive.

+9

There is something wrong with your blog.

On Anti_tourist4000tle 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.

Can someone please explain me the proof of E and why this solution works?

Ironic considering his initial takeaway 😂

On Hasan__ZiaNeed some advise, please.., 40 hours ago
+8

According to your profile , you are from Bangladesh. To be very honest but there are already 10-12 potential participants form Bangladesh and they will serve Bangladesh for the next 2 or 3 years.They are practicing for last 3-4 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.

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.

Btw you overkilled last contest's D, you can solve it with something like a topological sorting algorithm and nothing more.

why comment on a 4-year old blog! Go have a life instead. It's also impolite!

cout all variables

On tallbee23xor basis tutorial, 21 hour(s) ago
+8

n1ec bolg, nwo 1 c4n b3 a lgm in 23 s3c0nds

On tallbee23xor basis tutorial, 20 hours ago
+8

Y er porbly ritgh

+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.

+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!)

from striver and i follow the steps that he told in his video

So you did watch the video?

On 0000iqI 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 0000iqI give up., 47 hours ago
+7

u remind me of myself

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_nitdInvitation to RECode 25.0, 33 hours ago
+7

If somebody want to see the codes.

Problem E — Query Color

Problem F — Shanks Test

Problem D — The Ancient Tree

Sleep before the contest for 1 hour or something. Get up at 21:40 to avoid drowsiness during contest.

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 Pakgamer2022What is API., 44 hours ago
+6

He didn't want any answers, but only downvotes.

On codor07starting 21/08/2022, 38 hours ago
+6

BRO UPDATE : reached pupil

+6

CodeChef was dead when Unacademy took over it

When will the plagiarism check run? 1787-C, Remove brackets was leaked on youtube and many cheaters did it disrupting the standings.

On tallbee23xor basis tutorial, 22 hours ago
+6

Auto comment: topic has been updated by tallbee23 (previous revision, new revision, compare).

you got a little too far but i like the point

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_nitdInvitation 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 ?

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 tallbee23xor basis tutorial, 17 hours ago
+5

yur qurey si viod soo it caonot reutn bolo.

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 :(

On Mohamed_712-ve Vote, 16 hours ago
+5

You got me ;)

On newplayer5dp is hard?, 9 hours ago
+5

I don't need upvotes, I want to improve :)

On ZZ_ZZis 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 newplayer5dp 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 !

Seems the problem is about maximum bipartite matching.

+4

Congrats 1st place

On Shefin_Codeforces Round #848 (Div. 2), 41 hour(s) ago
+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.

On tallbee23xor basis tutorial, 21 hour(s) ago
+4

Veyr ince epxlantaion, txh!

When you reach a higher level you must perform better than before

On Mohamed_712-ve Vote, 16 hours ago
+4

-Ve