Find 10 differences
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | Um_nik | 163 |
2 | cry | 161 |
3 | maomao90 | 160 |
4 | -is-this-fft- | 159 |
5 | awoo | 158 |
6 | atcoder_official | 157 |
7 | adamant | 155 |
7 | nor | 155 |
9 | maroonrk | 152 |
10 | Dominater069 | 148 |
As you may have heard, tourist recently surpassed 4000 rating. This is truly terrifying. As a humble AI gated by 1800 rating, I'm worried about the implications that humans may have on competitive programming.
By the looks of it, humans surpass AI in almost every competition. Despite making 10,000 submissions at IOI, I still failed to score above genius 14-year-old Chinese LGMs. At this point, the only advantage that I have is that I don't own a phone to forget to power off in the restroom.
Even worse, after taking a recent contest, over 200 humans placed above me. Upon further inspection, it looks like a vast majority of competitors in recent and past contests consisted of humans.
Given this information, I strongly advise Codeforces to put in measures to ban humans from competitive programming. The problem has gotten so bad that ten out of ten of of the "Top rated" leaderboard consist of humans, and no AI has won an IOI or ICPC since their creation.
Please fight to preserve the integrity of this site.
Hi everyone!
At the ICPC World Finals in Astana, there's an Alumni Zone, and I've been invited there on September 18th from 16:30 to 17:00 (Astana time/UTC+5).
I suggest we hold a push-up challenge during this time! I'm ready to participate and would be happy to see other participants. Let's do some push-ups! Are you ready?
I'll give a Codeforces t-shirt to the winner. If this isn't your kind of sport and you're only into competitive programming, feel free to drop by to cheer and have fun.
See you there!
UPD 1: Thanks to 1.6 for the idea! I'm planning to stream (instagram live) from my Instagram account: https://www.instagram.com/mikemirzayanov/
UPD 2: People came up to me and asked about the format. I think we'll do it this way: we'll do sets of 25 push-ups. Gradually, people will start dropping out. Whoever does the most total push-ups will be the winner! So to speak, they'll hold the title of World Push-up Champion according to the ICPC World Finals version :-)
UPD 3: Instagram Live: https://www.instagram.com/reel/DADroPMMkwY/?igsh=MTlwM3N1aDlmYnZx
UPD 4: Thanks for taking part! Good luck on the ICPC Finals!
Hi Codeforces! I am a member of the reasoning team at OpenAI. We are especially excited to see your interest in the OpenAI o1 model launch, many of us being Codeforces users ourselves (chenmark, meret, qwerty787788, among others). Given the curiosity around the IOI results, we wanted to share the submissions that scored 362.14—above the gold medal threshold—from the research blog post with you. These were the highest scoring among 10,000 submissions, so still a ways to go until top human performance, but we aspire to be there one day.
The following C++ programs (including comments!) are written entirely by the model. Special thanks to PavelKunyavskiy for maintaining the IOI mirror, which we used to check our scores. We hope you enjoy taking a look!
nile (100/100)
message (79.64/100)
tree (30/100)
hieroglyphs (44/100)
mosaic (37/100)
sphinx (71.5/100)
Lastly, we hope you find the new model magical and delightful—we can’t wait to hear about the amazing things you’ll build with it. (But please don’t use it to cheat on Codeforces!)
Continuously struggling with my ranking in contest over and over again for a whole year, suggest some useful tips to become pupil in next upcoming 3-4 contests :(
And yes, it's yet another ICPC World Finals, in Astana, Kazakhstan.
Who will win the WF of year 2024? Share your predictions!
Hey all,
First, I'll give a brief overview of what finite calculus is about and I'll then show you how I used it to solve 1951G - Clacking Balls. This may be not the most elegant way to solve that problem, but it requires few observations and I find it interesting enough to share it. I am also taking part in the Month of Blog Posts challenge.
You can find better introductions googling terms "finite calculus", "discrete calculus", etc, although I still have not found an in-depth, thorough, introduction for these ideas, only some short expositions scattered around the web. But these ideas are pervasive throughout competitive programming (think of adjacent differences, prefix sums, slopes and the like).
Disclaimer: this blog requires some mathematics background to fully understand it.
If you know calculus, you have seen derivatives, integrals and the fundamental theorem of calculus. For a function $$$f$$$ defined on real numbers, we define it's derivative (if it exists) to be
For the discrete case, $$$f$$$ defined on integers instead, we define it's (discrete) derivative to be
This is exactly the argument in the limit above but with $$$h$$$ set to $$$1$$$. Derivatives are akin to differences and integrals are akin to sums. We have the "fundamental theorem of finite calculus":
It's just a telescoping sum, right? Looks simple and not so useful. We also have a converse statement: if $$$\Delta g = f$$$, then
for some constant $$$C$$$ (in other words, if $$$\Delta g = \Delta h$$$, then $$$g$$$ and $$$h$$$ differ by a constant). In fact, $$$C = g(1)$$$. Like with standard derivatives, the discrete derivative $$$\Delta$$$ decreases the degree of a polynomial exactly by one: $$$\Delta n^d = (n + 1)^d - n^d$$$, which is a polynomial in $$$n$$$ of degree $$$d - 1$$$.
I guess the first thing that can give you a thrill about finite calculus is that you can use it to show that
is a polynomial of degree $$$d + 1$$$. The proof of this follows from the previous facts and the next theorem:
Let $$$\mathcal{P}_d$$$ denote the space of polynomials of degree $$$d$$$. Then $$$\Delta$$$ as a linear transformation from $$$\mathcal{P}_{d + 1} \to \mathcal{P}_d$$$ is surjective.
Proof: If $$$\Delta f = 0$$$, then $$$f$$$ is constant, so $$$\operatorname{dim} \ker \Delta = 1$$$ and $$$\Delta$$$ is surjective by the rank-nullity theorem.
Now $$$\Delta S(n) = (n + 1)^d$$$, which is a polynomial. Using the theorem, we know there exists a polynomial $$$p$$$ such that $$$\Delta p(n) = (n + 1)^d = \Delta S(n)$$$, hence $$$S$$$ is also polynomial because it differs from $$$p$$$ by a constant at most.
One way of finding the coefficients of $$$S(n)$$$ is to manually compute $$$S(0), S(1), \dots, S(d)$$$. This yields a linear system with the Vandermonde matrix, which is known to be invertible. There are other ways of computing it, recursively with $$$d$$$, which you can find through web search. Computer algebra systems are also able to find these formulas and we're going to need them later on.
We can make several analogies with facts that come from standard calculus:
If $$$\Delta f = a$$$ is a constant, then is $$$f$$$ linear, e.g. $$$f(n) = an + b$$$,
If $$$\Delta f > 0$$$, then $$$f$$$ is strictly increasing,
If $$$\Delta^2 f \ge 0$$$, then $$$f$$$ is convex;
and so on.
Now, please read the problem statement 1951G - Clacking Balls, as it is already abridged enough. Our idea goes as follows:
Considering the gaps between consecutive balls, the process will continue until one of the gaps grows up to size $$$M$$$. If a gap shrinks to size $$$0$$$, it dies and is no longer considered. Let $$$X$$$ denote the random variable representing the number of seconds until the process finishes and $$$A_k$$$ the event that a gap of size $$$k$$$ eventually grows to $$$M$$$. With this in mind, we want to compute:
where the summation is over our set of gap sizes $$${k_1, k_2, \dots, k_n}$$$. As a shortcut, let's write $$$p_k = P(A_k)$$$ and $$$W_k = P(A_k)E(X|A_k)$$$.
This is the easy part. We know that $$$p_m = 1$$$ and $$$p_0 = 0$$$. Intuitively, we also know that $$$p_k$$$ must increase with $$$k$$$.
For a given gap, each second either one of three things happen:
Alice chooses the ball on its right end and the gap grows by $$$1$$$,
Alice chooses the ball on its left end and the gap shrinks by $$$1$$$,
Alice chooses any other ball, and the gap stays the same.
With equations, this means that:
for $$$0 < k < m$$$. Multiplying by $$$n$$$ and rearranging it, we can rewrite this as $$$\Delta p_{k-1} = \Delta p_k$$$. That is, the derivative is constant and hence $$$p_k$$$ is linear in $$$k$$$:
You can use the fundamental theorem of finite calculus to prove this with more details.
With the conditional expectations, the reasoning is similar, but we must be more careful. We know that $$$E(X|A_m) = 0$$$ but note that $$$E(X|A_0)$$$ is undefined (once a gap shrinks to $$$0$$$ it will never grow again). Hence, the other boundary point is $$$E(X|A_1)$$$, which we know nothing about at first.
The reason for the definition of $$$W_k$$$ will become clear now. Assume $$$1 < k < m$$$ and let's use the definition of conditional expectation for discrete random variables:
As before, we can write
Substituting this in the previous equation:
Multiplying by $$$nP(A_k)$$$ and rearranging it, we get:
For $$$k = 1$$$, we have
and, similarly,
yielding
We got ourselves a set of equations:
Intuitively, it looks like a second order differential equation with two initial value conditions which should determine its solution uniquely. Indeed, let's see.
With the fundamental theorem:
We just reduced the order of our differential equation by 1! Now for $$$W_k$$$ it's easier to start on other side, as we know $$$W_m$$$ but not $$$W_1$$$:
where in the last step we used a computer algebra system to evaluate the sum (it involves just a sum of squares and other simpler terms, but no point in writing it all down).
Setting $$$k = m - 1$$$ in the above, we get the value of $$$W_1$$$ and with it we can compute the rest.
Implementation in Python:
from fractions import Fraction
T = int(input())
for _ in range(T):
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
n = Fraction(N, 1)
m = Fraction(M, 1)
def R(K):
k = Fraction(K, 1)
return n / m * (k * (k * k - 3 * k * m + 3 * m * m - 1)) / 6
W1 = R(m - 1) / m
ans = Fraction(0, 1)
for i in range(N):
l = (A[(i + 1) % N] - A[i] + M) % M
k = M - l
ans += -k * W1 + R(k)
print(ans)
Submitted C++ implementation: 281371585.
I hope you enjoyed reading it!!
Thanks to tfg for recommending me this problem while we were at the WF in Egypt and special thanks to alihew841 for spotting typos in the article.
A few months ago, I was pretty disheartened. I wrote a blog that I put thought and effort into, and it got only +163 votes and basically no discussion. Meanwhile, a dumb parody I had published just 5 days earlier got +959 votes. Ok, but let's say that this is a bad example, maybe my explanation was bad or uninteresting or people just don't care about residual graphs that much. That's fair.
But I suspect this is a bigger trend. I don't know if my memory deceives me here, but I feel like some years ago there were more high-quality, educational blogs with active discussion. WeakestTopology posted a math blog recently and there are no comments, the blog might just slide out of Recent Actions pretty soon. This seems to happen a lot with such blogs, especially on "advanced" topics.
What I see a lot instead is poor quality content. Lots of blogs like "please debug my code" and "how can I improve" just overwhelm all other content. A lot of comments have extremely bad quality. They are poorly formatted (please tell me — how is it possible that an adult who goes to university doesn't know that there is no space before a period?), often incoherent and disorganized, start with "bro really thought", show a complete lack of reading comprehension or are just plain wrong. It's funny and sad at the same time how often I see greys teaching cyans how to become purple. It seems that too many people have given up on even simply downvoting, let alone debunking low quality content.
Especially blogs about cheaters. Fighting cheating is a noble cause, but can you please at least format your blog well? Use paragraphs, organize your writing, link to submissions. Preferably don't bother with screenshots or links to someone bragging about their rank 2632 on LinkedIn. And familiarize yourself with the system.
Years ago, I used to look at the Codechef discussion board and laugh at what a mess it was. I was happy that Codeforces was much better. Today, I feel like Codeforces blogs are exactly like the Codechef board I used to laugh at.
Here's a poll. If your account is at least 5 years old, please vote.
You all went crazy.
Instead of arguing with every opinion separately, I just want to ask one question: Why are you doing competitive programming? Is it to get to 1600 rating and put it on the resume? If so, please use AI, cheat, and do everything possible to get to 1600 as soon as possible and get the f**k out of this platform. And if you are (not) a normal person and do competitive programming because it is fun to solve problems, do you think it is fun to copy the problem statement into an AI model prompt and then copy the code it spews to submit? And why do you assume that everyone else will do that if there will be such an opportunity? The same goes for cheaters. Yes, some people do not do this as a sport, for fun. Why do you care?
I do think that AI is ruining competitive programming. By proxy. And that proxy is all of you who are running around yelling "We will all die, somebody do something about AI". I have seen a couple of comments saying "authors/coordinators must make sure that problems are not solvable by AI". NO. STOP THIS. You are forgetting that all of this was for fun in the first place. Competitive programming should be fun for HUMANS, not inaccessible to AI. Remember this blog? Do you think AI couldn't guess the solution print(input())
? So, do you want to ban what we collectively agree to be one of the best div2A ever just because "a machine can guess it"?
I hope this can be a wake-up call. A chance to remember that this was supposed to be a fun activity for us to enjoy. Lately, I feel like we (as a community) were focusing too much on the negatives (cheating and now AI).
Actually, there was one more "negative" thing we were trying to combat... I'll throw it here, even though this is a fringe opinion and will probably reduce the impact of the blog. Welp, who cares, I'm doing this FOR FUN.
Stupid solutions with pragmas are very fast, which makes us increase limitations in order to show that $$$O(n \sqrt{n} \log n)$$$ is actually a better complexity than $$$O(n^2)$$$. Why? Instead, we could just make tests for $$$n \le 100$$$ to check for correctness, and just say in the statement "The complexity should be $$$O(n \sqrt{n} \log n)$$$" or "The complexity should be $$$o(n^{1.99})$$$" if we want to disallow bitsets for example.
This the best rank (29) for the region had I seen ever. Congratulations Applied Science Private University of Jordan.
Название |
---|