I've been doing CP for more than a year regularly. I've usually had a decent judgment with respect to the rating a problem might be given, once I've solved it. But for a couple of months now, it feels like something has changed. I seem to be predicting the problems to be harder by more than 200-300 rating points. In virtual contests, I noticed how a lot more people are solving seemingly hard problems quickly. Is this just me or have others noticed this too? I've noticed a lot of blogs about plagiarism lately, has it been driving the rating of problems down? Have people been discussing solutions in live contests? Or am I just tripping?
For example, I was legitimately surprised to see more than 13k people solving questions on Diophantine equations — I Hate 1111
it's just brute force, you can solve it without knowing diophantine equations
Agreed, but one has to at least figure/get an intuition that you can obtain any number after a certain point right? — I don't know if that's a 1400 level conclusion. That example was just a sample anyways, I'm talking about a general issue, just wanted some feedback about the difficulty of problems.
I wanted to figure out if my level unknowingly dropped or if something external is going on.
Greens and cyans often solve problems by guessing things they have no proof of ;)
I think most do try to prove. Nobody wants to be unsure while submitting a solution. It's just sometimes the proof is not obvious and especially if time is running short one can't help but submit it as a guess.
Most of the days if it's a div 2 C I will at least try to be intuitively correct if I can't come up with a proof before submitting. (I don't know if that falls under a guess)
I actually get what you are saying, but I'll say that over my CP experience (mind you I don't really practice with friends etc) I only started solving on hunches after I reached high expert-ish rating. At lower ratings I was no where near confident or competent to pull houdini acts without proofs :P
Sometimes oranges do too ;)
A major factor is that this was a letter B problem. Contestants had a lot of time to bang their heads against it, because they didn't have much choice. The problem C from that contest was a weird two-part beast. As a beginner, I'm still trying to avoid two-part and interactive problems.
If this B. I Hate 1111 problem was a part of a different contest and had, let's say, letter D assigned to it, then your conclusion would be "yeah, Diophantine equations are difficult as expected" ;-) But the real reason would be that the contestants just spent time on A/B/C and haven't tried D.
From testing, I hate 1111 was either a 1 minute solve or a 1 hour brick.
There is nothing hard about the problem but sometimes you are just unlucky with key observation. And this will keep happening for d2ABC as problemsetters have no choice but to set these kind of "1 observation magic" problems for d2ABC because coordinators will not accept syntax and we cannot put anything too advanced in d2ABC.
So to you personally, the difficulties of d2ABC will definitely change alot whether you are lucky to think about the intended way to solve in the first try. (even a GM like monogon only ACed I hate 1111 more than 1 hour into his virtual during testing)
I was from 1 hour brick gang.
Yes, I think that is the case.......although I think this barely effects problems like D1B or ahead. I think its effect is mainly on Div 2A,B,C. Btw, one more thing. Easy problems does not always mean you will solve it faster. It might also mean "you require lesser skills solve it". There's a difference.
The example you gave.....it was a hard problem. But in an "easy" way. You understand what I mean? It is ok to get stuck on them.
Also, I think in a mind sport like this, your "level" will drop only if say, you haven't been training for a few weeks, maybe months. Else, you should be fine. Some variations in performance can always occur.
I see. With regards to the problem — I had actually solved it pretty quickly, 17 min, and yet there were more than 2000 people who solved by then if I recall correctly.
Unless you mean relative to problems from more than a year ago, you're tripping dawg. People are just getting better.
Not a year obviously, I was hogwash back then. Say December 20/Jan 21.
My theory is that a large cohort of people started participating in early 2020 (it went from 10k participants to sometimes 30k). And now all of them have > 1 year of competitive programming experience which is sufficient time to learn how to speedforce easy div2 problems.
I think you can prove/disprove this theory by checking the average account age of participants?
Like This problem got only 800 rating but it was a very good level of implementation, no way it can be 800 rated
Yeah, this problem use prefix sum array, which is a little bit upper from 800 (like, 1000 ~ 1200 I think)
Yeah even I think so ,from last 5-6 contests the cheating culture has increased so much and many of the cheaters don't get caught sadly. It's just my observation ,idk.
For the problem mentioned in the blog, I solved it using a more intuitive approach.
$$$Approach - $$$ Any number, say $$$n$$$ can be represented as $$$n = 11\lambda + \mu$$$ where $$$\mu \in [0, 10]$$$ and $$$\lambda$$$ is a positive integer. We also know that $$$111 \equiv 1\pmod {11}$$$, so we can represent every number as a linear combination of $$$11$$$ and $$$111$$$, i.e. $$$n = 111\alpha + 11\beta$$$, if its large enough. By large enough I mean $$$\mu * 111 \le n$$$. Since we can also represent $$$1111, 111111 \dots$$$ using this equation we don't need to check for other numbers and this condition gives all possible answers.
Considering that the code is like 2 liner maybe the number of submissions are justified.
Code: 120656716
According to the standings https://codeforces.com/contest/1526/standings, 5k people solve the problem I Hate 1111 during the contest, not 13k.
I tried DFS BFS almost anything I could think of. All my solutions either TLE's or MLE'd. One such solution.
When I saw the editorial I was pleasently surprised!
Is there a DFS or BFS implementation that actually works for this problem? I never thought of it as a graph theory problem.
If you used Diophantine equations to solve that problem, you're doing something wrong.
You can look at my solution — I'm not doing anything too complicated. I said diophantine cuz its the first thing that hits my head cuz I like those problems. Two coprime numbers and you are trying to find linear combinations. That's like instant intuition that eventually all numbers are going to be generated and hence brute force will work. I think that bound also has some theorem right? Chicken McNugget I believe?
That aside, the idea of the post is not to say I'm finding difficulty solving the given problem, the given problem is just an example to make my point.
Well that problem is somewhat of an exception, probably one of the harder Div. 2 Bs in recent memory. But I think there are so many ways of solving that problem, by the Chicken McNugget Theorem as you mentioned, for example, that it isn't surprising that so many people solved it. Personally, I solved it by doing a quick bruteforce dp for n <= 10^5, and printing out all the numbers for which it wasn't possible. From here, you notice that there are no values > 1100 for which it isn't possible, which I believe is also the easiest method of solving it. I don't think the big plagiarism problem started until after this round, and even if it didn't, I don't think it drastically affects solvecounts anyways.
Maybe this problem wasn't the best example, but I have seen other examples of problems being solved by more people than I expected. For example, GCJ 2021 Round 2's final problem's first subtask had 853 solves, and the subtask used bipartite matching. Now, bipartite matching isn't particularly difficult or anything, but I thought it was a relatively rarer topic that people don't typically learn. I even remember thinking during the contest "I must be overcomplicating this, there's no way this many people solved it if intended solution is matching." Turns out, bipartite matching was intended.
Another example, this CF problem is rated 1800 and its solution is based on modifying segment tree. I think 2 years ago, this problem would have been rated higher, but nowadays it seems segment tree is common knowledge even for newbies and pupils, hence this problem gets significantly more solves in contest.
This actually makes perfect sense. As time goes on, more high rated users make resources, so more people learn algorithms. 2 years ago, I remember learning segment tree from a half decent HackerEarth article and this blog post (no shade to these resources btw, I think they do their job). Now there is no shortage of high quality tutorials on segment trees in CF EDU, on YouTube, etc. I think this is a good thing because if the average competitor knowledge base expands, it gives problemsetters more options in what algorithms to base problems on.
Hmm, I didn't find the D. Playoff Tournament problem particularly difficult or unapproachable. I think that the primary reason why it got such a high 1800 rating is that many contestants just didn't have enough time left to even try it after they spent most of their time quota on A/B/C. If the contest lasted 3 hours instead of 2 hours, then a lot more people would have solved it. Or if this problem had letter B assigned to it instead of letter D.
I successfully upsolved this problem after the contest without checking any spoilers. And for me it looked like a generic DP problem with a little twist. The twist being: how much of the DP state can we preserve between queries? It surely helped and provided a major hint that I have seen way too many recent blogs, where people complained about getting TLE only because they were memseting a huge DP state array between testcases. If we just minimize adjustments to the DP state array, then the performance improves a lot. My first TLE attempt with DP only (good enough for a single query): 118444005. And an updated AC version (update of the DP state between queries is minimized): 118445614.
Needless to say that I don't know the segment tree topic yet. Yes, memorizing all these advanced algorithms surely saves a lot of time during contests and provides a significant advantage. But this is not strictly necessary in principle, or at least not in all cases.
Sure, I went with segment tree because it was the most common source for intuition for that problem, as seen by a cursory scan through the comment section of the announcements blog (and even the editorial mentions segment tree). In fact, after looking at your submission, I think you essentially independently reinvented some of the core ideas behind segment tree (storing aggregate data in a binary tree, which is the same shape your recursive function calls follow).
Anyways, I don't disagree that you can get far without vast algorithmic knowledge (case in point), I was more so making an observation that the average competitor knowledge base seems to be expanding.
From last few contest I have also observed more people solving A, B, C 's in less time. Before I came up with up with a solution, boom 2000 already did it. Earlier the submission rate was slow. I gave virtual contests from nov, dec 2020 and I solved problems with same pace and got good ranks.
something is changed. Maybe people at CF have become better
People have become better and then placement season will start soon(at least in India) so more people are participating. Don't know about other countries though. Higher number of people can maybe explain the higher number of submissions to some extent.
I have similar thoughts. Although I can't say it is because of cheating since I am not practicing as I used to.
i solved that problem by using the "write brute force+print answers for all n<=1000, guess pattern, and pray" strategy :)
The only unsolved 1400 of my first page of sorted problems. After trying almost an hour, I was so disgusted with the problem that I didn't even bother to submit that.
Either you are not tripping, or you are not alone.
I think that specific problem wasn't that bad, the modular arithmetic argument (or just brute force and pray one) worked well. However, I feel that problems in the 2200ish range sometimes should be more like 2100 or 2000 whereas problems I feel like were 1600 or 1700 at least are dragged down to 1400-1500. Some rating inflation towards the top, and some rating deflation towards the bottom imo