alxwen711's blog

By alxwen711, history, 15 months ago, In English

Hello all on Codeforces!

It’s been just over a full year since I created my Codeforces account. Since then a lot has happened on my Codeforces journey so far. With everything that’s happened I want to look back at how I got to my current point, share what I learned in the process, recap some of my best moments, and laugh at whatever I was thinking on a few of these contests, because a lot happened. The only issue is that there’s no way I’m going to detail all 60 contests I took part in 2022. Instead I’ve chosen to “award” the 9 most memorable contests, wheter it be because I did exceedingly well or self destructed in almost hilarious fashion.

A few notes before I begin: No full solutions for any problems are shown in this post but there are code snippets and discussions that are spoilers for these problems. I apologize in advance.

First Contest — Hello 2022

This was the first contest held in 2022, and the first contest I participated in. At this point my experience with programming consisted of about 4 terms of Computer Science study at SFU, a few offhand miniprojects, a solid math foundation and everything I did on Hackerrank and Codechef. This was the first time though that I felt like I was taking part in a “serious” competition since most of those were longer multi-day contests. It was a pretty rough start for me; I ended up only getting the first problem correct and then I spent the next two hours wondering how I kept getting a TLE. It turned out in Python that using sys.stdin.readline() was much faster than input(). Pretty silly mistake, but this was just one of the many things I learned from Codeforces in 2022. Besides, the next few contests would go more smoothly.

Honourable Mention

Greatest Blunder — Education Round 123, Problem B

In most of my first few contests I mainly did well on math-heavy problems and anything involving the greedy method. My goal in the first few contests was mostly to get used to the two-hour time limit of these contests and avoid making simple errors in logic or implementation. After six contests (note that 6 contests are needed to have the displayed rating match the “official” rating), my rating normalized to a starting point of 1527. Looking back this was actually a good start, but I was still pretty inexperienced at the time. The next contest “award” explains this better. Prior to this contest, my rating had declined a bit to 1454. After this contest I lost 134 elo, solely from the “I can’t count to five” incident.

I’m not sure if it’s just me, but at this point, I felt like even though I was technically at the Specialist rating, my knowledge and ability did not resemble that of someone at Specialist. What I mean is that I had some knowledge on concepts that would be found mainly in Expert level problems, but I would also have moments where I make inexplicable mistakes on Newbie or Pupil level problems, such as in this problem, where they reared their very ugly head. This was my second submission in the contest:

2nd submission (spoilers)

The important part is that I had cases for n = 3, 4 and 5 hardcoded for this problem, as I had a valid algorithm to generate n Anti-Fibonnachi permutations of length n for cases where n is at least 6. Yet somehow the above solution gets a wrong answer on pretest 2. If you have a keen eye you can probably tell that for the n=5 case, I only wrote out 4 perumations when I needed 5, which was the source of the problem. For those who didn’t, don’t worry.

It took 6 more failed attempts and 84 minutes for me to notice this error.

Needless to say, being able to implement solutions accurately and debug them efficiently is pretty important in competitive programming. I would become more consistent in implementation in later contests, but it took a while for this to be reflected in my overall rating.

Dishonourable Mention

Best Breakout Contest — Round 781

To give a bit of context, it is now the morning of April 8th. I am at a rating of 1398 and am still trying to climb back to Specialist. At this point I am consistently solving Problems A and B with Problem C being inconsistent and Problem D being well out of my current ability in Division 2 contests. This contest was a case where I solved 3 problems, but more importantly, I actually fully solved Problem D for the first time ever (in a Division 2 contest). It’s understandable that I completely missed Problem C because I was still learning about trees at this time and I was still pretty weak on data structures as a whole. On the other hand, Problem D was more around constructing an algorithm that could determine the value and was much more math and number theory heavy, both topics I was strong at. Even still, how I did on Round 781 was well outside my norm; at this point, this contest was the first time ever that I had a Candidate Master level performance, and was the reason that this contest led to my highest ever rating change of +148.

Honourable Mentions

Best Single Question Moment — Educational Round 132, Problem D

It would take until July 21st to reach the next Codeforces moment of my journey. In the past few months I participated in numerous Codeforces contests, and while I was still having contests where I only got Problems A and B, I was getting C with more consistency and occasionally solving D as well. Much of this can be attributed to better data structure knowledge which came from external Leetcode practice (I used the Data Structures I/II study plans for basic review) and reading through https://cp-algorithms.com (very useful resource containing just about everything useful for competitive programming). The only way I can really explain this moment is by my method to solving this problem, so alas, spoiler tag is absolutely needed here.

The method I used for Problem D

For this problem I actually ended up submitting with an Accepted verdict 3 times. This was due to me doing wack stuff to try and optimize my solution since my method was just fast enough to pass all the testcases, clocking in at 1918ms for a 2 second time limit. Even more fun is that there were 16 attempts made to hack this solution which all failed. I don’t care that I missed Problem C in this contest, for me, this question alone made this the most glorious loss of 3 rating points in a contest ever.

Honourable Mention

Best Overall Performance — Round 814

This contest can be described as a combination of my effort from the start of 2022 and a bit of luck in the problem topics used. At this point I was usually getting 3 or 4 problems in each contest, and my average performance was at an Expert level. At this point I was still at an 1834 rating.

This contest I technically solved 6 problems. It’s really 5 since Problem D was split into two parts but I am still amazed I even pulled this off. It wasn’t a perfect contest since I did have a few wrong submissions on D, but an important difference here is that I actually used the feedback correctly to fix my code. In past contests when I get something like Wrong answer on pretest 2 I would be fixing my solution in the wrong method by trying to make small adjustments to an algorithm I believed to be “almost” correct or by trying to account for edge cases. In this case I ended up pretty much creating a new solution after each attempt which led me to the right answer effectively. Then there’s Problem E. To be honest, I still have no idea how I solved this in 15 minutes. My thought process for E is in the spoiler below:

Problem E thought process:
Honourable Mention

After Round 814, I reached my current peak rating of 1981 and had successfully reached Candidate Master in 2022. My overall performance rating on this contest was estimated to be around 2363. Sure this was partially due to the contests having a focus on topics I was strong at and there was a good chance I would regress to my actual skill level eventually, but the progress up to this point was something I was proud of. I felt that I made great improvement in my algorithmic knowledge, and had learnt many useful data structures. I found myself to have improved in competitive programming as a whole, and was hopeful as I want to go as high as possible, not just Candidate Master, but Master and beyond. This graph showing my progress from my 6th contest where my displayed rating matched my actual up to this point was a culmination of all the hard work I put in, and I was proud of it.

There’s just one issue though: Round 814 occurred on August 16th. If 2022 ended here, then this wouldn’t be an interesting journey now, would it?

Most Painful Choke — (Round 818)[https://codeforces.com/contest/1717]

I lost Candidate Master right after achieving it in the very next contest I participated in. Such is what happens when the previous contest plays into all of your strengths. Losing Candidate Master wasn't that much of a frustration to me though as I was still confident I could return given a few more contests. What the next round brought me though is only describable as pain. At this point I’m at a rating of 1883 so I’m in striking distance of returning, but unfortunately I performed terribly. Statistically it doesn’t look that bad. I only lost 3 rating from this contest, but I genuinely still have nightmares from my ineptitude in this contest.

For example, Problem C. It doesn’t look like I screwed up here at first because I only used 1 attempt and 38 minutes to solve this question but this should’ve been much quicker because I initially tried to solve more than the problem was asking. Consider the following problem:

Suppose I gave you only pencil and paper, and I asked you if 420.69 multiplied by 3.141592653589793238 is greater than 1300. How would you solve this problem?

What you would most likely do is approximate the value by rounding the values. For instance:

420 * 3 = 1260. 
10% of 420 = 42, thus 
420 * 3.1 = 1260 + 42 = 1302
1302 > 1300, thus 420.69 * 3.14159… > 1300. 

Notice that for the above problem, you did NOT have to calculate that 420.69*3.141592653589793238 is equal to 1321.63661343869011729422. The question only asks if the multiplication is above 1300, not for its exact value which is unnecessary information. Solve only what the problem requires you to solve.

This mistake is nothing compared to Problem D though. In fairness the question was a complex combinatorics problem that I eventually solved with 4 wrong attempts. That’s where the positives end. Submission #1’s error can be summed up as follows:

Let a = 2, b = 5, c = 3
My line of code: a = a + b % c

What I assumed would happen:
a = (2 + 5) % 3 = 7 % 3 = 1

What ended up happening:
a = 2 + (5 % 3) = 2 + 2 = 4

I didn’t notice the modulo order of operations mistake in the second submission, instead thinking that part of my code was buggy. This part in question was literally from a library of competitive programming code that I had created and tested a month before this contest. The good thing is that I found the modulo error in my third submission. The bad part is that I accidentally screwed with my library code. As for the 3rd submission error, I have no words for how I messed up basic Python syntax. The 4th failed submission? I quote from my personal journal entry, “I thought print(ans%m) wasn’t working properly.”. ans and m are int variables, and unsurprisingly, that wasn’t the problem.

This is a case where I was panic submitting. I can only assume I kept rushing because the point value of Problem D was dropping by 8 points per minute, but this entire debacle cost me 200 points in wrong submissions, not to mention additional points lost from trying to fix these wrong submissions. Had I properly fixed the modulo error after the first submission and not tried a desperate hack attempt at the end of the contest, instead of losing 3 rating, I would have gained around 20 rating and would have made it back to **Candidate Master. I completely blew this chance due to prioritizing speed over accuracy. I was still close to **Candidate Master, but just the idea of “What if I wasn’t being an idiot in those 4 wrong submissions?” made this an agonizing contest to start September.

Round 818 is also painful for one more reason: this is the start of The Implosion. The red text is absolutely necessary.

Dishonourable Mention

Before the next award, let’s briefly look at the 10 contests I participated in after Round 818 and how I did on them:

  • Round 819: Topics I’m weak at, contest ended up being unrated.

  • Edu Round 135: (-72). Python dictionaries punch me in the gut. This contest also unofficially wins the Most Heartbreaking Contest award as if Problem C was right, I would have again made it to Candidate Master. The one bright spot was that since my solution got hacked, instead of having false hope for 12 hours I only had it for 30 minutes.

  • Round 821: (-50). The order in which I read the questions was A, B, C, D1, D2. I ended up solving them in the order B, D1, A, C. I struggled on a Division 2 Problem A.

  • Round 822: (+9). Contest at 5am local time that I actually did well on, which at this point means there wasn't any egregious blunders to rant about here.

  • Round 823: (-58). System failed B because my brain forgot how absolute and relative error worked. I also inexplicably thought to go for Problem E with a total of 5 people solving it when Problem D had nearly 300 solves so add poor contest strategy to the mix.

  • Edu Round 136: (+29). Questionable contest strategy (again with attempting E before D because “oh no! trees!”), but aside from that I did okay (solved A-C) and somehow gained rating.

  • Global Round 22: (+71). The one actual bright spot in this series of mediocre to horrible contest performances.

  • Round 824: (-17). Problem D is solved, but slowly and with sloppy execution.

  • Round 825: (-74). 7 wrong submissions on problem B and I get SpeedForced, ie. lose rating mainly due to solving the same problems as a lot of other competitors slower and with less accuracy.

  • Round 833: (-43). Went into this contest after taking a month long break from CodeForces because after Round 825, my mentality was a wreck. Spent the month long break still competitive programming but doing absolutely nothing involving CodeForces, did Round 829 as a virtual contest to get myself back into rhythm which went decently well, then proceeded to over complicate Problems B and C and miss Problem D to lose even more rating.

I was at a rating of 1981 on August 16th. It took under 3 months for me to drop to 1673, 308 points below my peak. Before this slump the furthest I was below my peak was 207 rating points, and that was after not counting to five properly. Despite this, the most important part was that I was learning from these contests, even if my rating was collapsing. Besides, I have basically hit rock bottom at this point, so any decent contest will help in bringing my rating back up. Speaking of, what’s the next contest award I’m discussing?

Most Spectacular Implosion — Pinely Round 1

Ah.

This contest.

I think I’ll just let this personal journal entry explain how truly “Special” my "performance" was on this contest.

The above image is clickable by the way.

This week, on Days of Our Programmers,

Our protagonist's CodeForces journey has become one of so much drama comedy that the production crew has decided to make this the first relatively public episode. From where we last left off the Proponent for Python had returned from a one month hiatus from CodeForces. He took that time to mentally reset and prepare himself through logical preparation methods such as doing competitive programming stuff that isn't just CodeForces, actually getting enough sleep, and trying to convince himself that he's a dragon. Truly a man of logical reason. Currently 227 ELO away from the glory of having a purple username the next contest is of critical importance for our protagonist. Another choked competition here may turn his hope of escaping Expert rating hell into nothing. Thus at 6:30am our protagonist readies himself for Pinely Round 1.

As the contest begins the dragon strikes with fury solving Problem A in 4 minutes. Not a bad start but then Problem B comes in and suddenly our protagonist finds himself mindblocked. After half an hour of greedy attempts, the Proponent decides to move to C for now. It starts off well; the protagonist determines that the hierarchy of sets can be represented as a graph structure. For instance, if A subsets B and B subsets C, then node C is the parent of node B which is the parent of node A. Wonderful. The Proponent quickly begins work on representing the set structure as a tree. It is at this point where an old bogeyman rears its ugly head:

Runtime error on pretest 2

Runtime error? Not wrong answer? Clearly just a simple mistype in the code. And there was an error. But the runtime error remained. Our protagonist went through the code rationally yet no mistake was found. Desperation began to increase. Then, a brilliant move was made: he changed the Python compiler from PyPy 3-64 to PyPy 3. Marvel at the Proponent's genius as he gets another runtime error?

Huh. I swore that would work. If you couldn’t tell that was blatant sarcasm, and at this point, I have to ask, what in the hell am I doing? I’m blowing yet another contest and it’s my own damn fault because I am turning to inane measures that clearly don’t work. Is this not what the break was for??-

PLEASE STAND BY…

The search continues as he finally finds the problem as 40 minutes and [REDACTED] number of attempts. Turns out the set structure was not a tree because a set could have multiple direct parents. In this case, suppose A = [1,2], B = [1,3], C = [1]. This results in C having A and B as direct parent nodes, which is not possible in a normal tree. There is no time to lament this classic case of alxwen711 imploding in yet another contest though, for time is running short. Our protagonist rushes to rectify his set graph and with 20 minutes to go, he submits and passes pretest 2. It may not be victory, but at least Problem C is solved.

That is until the program runs out of time on pretest 5. Time is running short, and a quick look at his scuffed code shows that the slowdown was in scuffed implementation. Knowing his solution is logically correct, desperation creeps in again. Many optimizations occur, yet it falls short. And then, time runs out. For the first time since April, our protagonist only solves 1 problem.

The collapse has been completed. But in this collapse, a goal is achieved: The Proponent of Python is no longer in the ELO hell that is Expert. A truly amazing result. There is absolutely no copium involved with our writer of this episode here. As our protagonist finds that his contest of self destruction has landed himself in truly a "special" place, what shall he do to cope with this new predicament? Perhaps he'll be more inclined to take part in the dark arts of C++ to distract himself that pretty much all of these failures had nothing to do with language choice and more to do with overthinking solutions and abysmal implementation skills. Whatever the Proponent of Python decides to do in response to this dumpster fire, we can only hope that he recovers his mental for the next episode, of Days of Our Programmers.

I mean, what do I even.

448 points below my peak.

In 96 days, I went from breaking into Candidate Master to dropping out of Expert entirely. There’s no point in breaking down what went wrong here, because the only thing I did right was solve A quickly. I had a bigger question to ask myself, being “What am I doing?”.

I’ve seen many posts on this site from users asking how to reach x rating. Part of my reason for writing this post in the first place was to show how I reached each rank up to Candidate Master. But there’s only a few posts asking how to deal with a rating slump, and to say I was in one of those is an understatement. It felt horrible and left me questioning if I was doing anything right if rating wise I was at the same point as I was in February. I questioned if reaching Candidate Master the first time was only due to luck. I was coping with this failure through catharic mockery of my implosions.

Never at any point though did I consider quitting. Even with this massive rating loss, at the end of the day, it’s just a number. I may care about it a lot, but it didn’t change the fact that I was more knowledgeable from these contests. If that 1981 peak was an overestimation of my true skill, what’s stopping me from saying that my current 1533 rating is an underestimation? And at this point, I have dropped so far that any further losses would matter little to how numb I was to them. There is nothing left for me to lose if I go into another contest, and I would not forgive myself if I simply stopped here. In my mind, I had to keep going. Pinely Round 1 did not crush my spirit to compete, but ignited it to an admittedly infernal rage that drove me with the sole purpose of redemption.

On a lighter note, it’s a good thing I don’t use this same mentality toward gambling.

Comeback Contest of the Year — Round 836

The last 11 contests were undeniably a mess, but at no point did I feel demoralized in my efforts. If anything, I was more angry than anything from all the screwups I made in the past contests, especially in the Pinely disasterclass. As a result my strong result on this contest not just led to gaining 130 rating (even if this was because I was 448 points off my peak), but more importantly, it was a relief. After dropping so far down I just wanted any semblance of what I was capable of back in July and August, and I got it here. There were a few differences from the past screw ups that led to this good result:

  • I didn’t make trivial errors. I feel stupid having to mention this but just the fact that I didn’t make screwups like basic Python syntax errors, thinking the compiler was the problem or egregiously submitting solutions that are almost certainly wrong.

  • I took more time to actually think about my solution before submitting. This also means taking a bit longer to actually have a general sense of how I would implement my solution. Both of these helped in limiting my wrong submission count to just 2. In past contests I would have several avoidable wrong submissions either by my solution not being well thought out or rushed implementation leading to a TLE.

  • I had no expectations for this contest. In a way this also meant I put no self-pressure on myself to do well.

More importantly, from this contest on, I felt more careful. I still rely on being fast in these contests but for the most part I’m less prone to tripping over myself on the basic tasks. This is reflected in my final 6 contests of the year all being at least Expert level performances. To compare, the previous 12 rated contests before Round 836 consisted of 1 Candidate Master level performance (Global Round 22), 5 at an Expert level, 5 at a Specialist level, and the Pinely disasterclass with an approximate performance rating of 906. All of this led me to finishing 2022 at a final rating of 1805. I didn’t reach my goal of being Candidate Master at the end of 2022, but the upwards trend is hopeful. A lot of what I learnt during this year can be summed up in the following, which can double as an explanation for how I reached Specialist/**Expert**/**Candidate Master**:

  • Foundation is important. I cannot stress this enough. Most of the contests where I severely underperformed were due to messing up basic tasks or screwing up due to lack of knowledge in basic Python functionality, so knowing all the basic syntax and data structures in the programming language you are using is critical.

  • For additional practice doing virtual contests is the best method. If you want to improve at Codeforces contests then the best way is to simulate an experience as close as possible to the real thing. I didn’t find much use in solving x problems of y rating because it didn’t feel like actual contests; with those you know the problem rating and can look at the problem tags which gives you a general expectation and/or idea of what the solution is, an actual contest will have none of that help.

  • Your rating is going to fluctuate from contest to contest because there will be contests where the questions are mainly on topics you are strong at and vice versa. As such try not to be too fixated on the number, especially if it’s lower than expected.

  • Wrong answers are going to happen. The important part is being able to know what to fix based on these wrong answers instead of aimlessly guessing or making trivial edits. A quick overview of typical error messages and I usually infer from them:

  • Wrong answer on pretest x: if x is a smallish number (2,3,4), it usually means your algorithm as a whole is flawed. Here I would try to generate a counterexample to my current solution and fix based on that before resubmitting. If x is a larger value then it could be a missed edgecase.

  • Runtime error on pretest x: A similar method to fixing a wrong answer verdict can be taken here. I would focus more on edge cases and recursion loops as those tend to cause runtime errors. Also check the entire code in case there are syntactic errors not caught in previous pretests.

  • Time Limit Exceeded on pretest x: For small x values this usually means your algorithm is a significant factor too slow, such as O(n^2) when it needs to be at least O(n log n). If it’s a relatively large x value then you may be able to get away with marginal time improvement. For most contests, pretest 2 or 3 tends to be the test where the values are close to the maximum limits given (ie. if n <= 200000 then pretest 2 will usually be a case where n = 200000). You also want to be careful of other methods that a solution can be much slower than expected, mainly with blowing up unordered maps or dictionaries. It’s rare outside of hacks but there is the occasional problem that does test this.

  • Knowledge of more complex data structures (segment tree, sparse table, DAGs) are helpful mainly for going from Expert to Candidate Master. Otherwise a lot of the easier problems don’t really use complex data structures.

  • CodeForces has the fun nickname MathForces for a reason. Math concepts are generally important at all levels.

  • From about Pupil onwards binary search becomes VERY important, and there are many ways it ends up being used. One particular pattern I found was using it to solve questions in the form of “what is the minimum x required to do task y?”. If there is an easy way to check if task y is possible given a value x which may not be the minimum, then one can binary search across a range of values for the answer to find the minimum instead of trying to determine an optimal solution. Example Question involving this

  • Usually from around Problem C to D in contests is when I notice more of the challenge in problems going from rigorous implementation and relatively easier algorithms to problems that require more complex ideas via math/data structures/algorithms but being less heavy around implementation. I found that in reaching Specialist, the important factor is being able to implement one’s ideas into code accurately and efficiently.

  • Expert is a pretty wide rating range, and what I find is the difference between 1600 and 1900 is how consistently one can solve Problem D. This is also usually the question where more complex data structure or algorithm knowledge usually comes into play as by this point implementation is not as much of a challenge.

Before I end this post, there are several people I would like to thank:

  • MikeMirzayonov for hosting the CodeForces and Polygon platforms

  • Everyone involved in coordinating, writing, and testing these contests

  • Everyone at SFU part of the SFU competitive programming club for helping me learn many useful concepts for these contests

  • Everyone who tried hacking my solutions in live contests. It allowed me to properly learn how to prevent being hacked when using Python dictionaries, even if it made me very sad after Educational Round 135.

  • You, for reading this post and for making CodeForces great :)

I look forward to going even further on CodeForces in 2023. This nearly concludes my recap of 2022 on CodeForces, but there is one more special contest I want to highlight that occurred at near the end of this year:

The Greatest Contest — Polynomial Round 2022

This contest was special, not because of how I did, but because it’s a representation of why I enjoy Codeforces contests so much. This contest was in my opinion one of the best contests of 2022 since the problemset covered a wide variety of topics and the difficulty curve was one of the most balanced overall. In particular during this contest I felt that every question was intriguing and had a solution that was beautiful. It’s hard to really put into words. More memorably, there was also a sort of fun chaos that occurred with Problem B that I did fall for at first but was able to fix in time. To be fair, the lower clear rate on Problem B is a result of the questionable pretests, but the thought of myself and thousands of other people facepalming when they realized what had happened in that moment is kinda funny to me.

The Problem B hack shenanigans:

And that finally wraps up my 2022 on CodeForces in a “nutshell”. It was a crazy adventure from the highs of reaching Candidate Master in 8 months, to the lows of not being able to count to five. Each contest I took part in was a great learning experience and there is much I’m looking forward to in 2023 here on CodeForces. Thank you all for reading about my journey in 2022, hopefully you learned something or found this post to be an interesting experience.

Full text and comments »

  • Vote: I like it
  • +71
  • Vote: I do not like it