yellow_13's blog

By yellow_13, history, 10 months ago, In English

I'm writing this blog as a brief account of my journey from expert to candidate master. If you're someone who has been stuck in expert for a really long time and is trying to reach purple, I think this blog is worth reading. About me: I reached candidate master last week in Codeforces Round 850, before that I had been stuck in expert for a very long period of time, if you'll look at my rating graph, you can see that I reached expert in April 2020, and finally managed to reach candidate master in Feb 2023, which means I've basically been stuck in expert for almost 3 years. At multiple times I thought that maybe becoming a candidate master requires some sort of innate talent that I just don't have, but finally it has happened, and here's what I've taken away from all of this.

So I started giving contests on Codeforces in Jan 2020, in my first year of college. Initially, my main source of practice was Codechef long challenges, but I shifted my focus to giving Codeforces contests pretty soon. Things were going good and I reached expert in April, and I was one of the first ones to do so in my college batch, so I was pretty proud at that time. I figured that with a reasonable amount of practice, I should become purple soon, and I started working towards that. But then I don't know what happened, no matter what I did, I just wasn't able to gain rating. Many people in my college batch had started to reach purple at this point, and I was getting really stressed as to why I wasn't getting there. I started putting more and more pressure on myself to become purple, and that just made my performances even worse.

I was starting to feel like I'm lacking some sort of intelligence/smartness that's required to reach purple, since none of my friends had struggled as much as me to get there. I once had a very interesting discussion with my friend rockstar2514 regarding what exactly does one need to get good at problem solving, not just for competitive programming, but for science in general. We came up with an idea that problem solving requires 3 things on our part:

  1. Memory: This is just pure memorization, you exactly recall whatever you know, without thinking much more than that. In CP, this is useful generally when you have to write some well known data structure or algorithm, example, suppose you want to write the code for fast exponentiation, you wouldn't think much about it and you'd be able to write the code quickly from whatever's there in your memory.

  2. Analogy: This is a very important skill. You understand the problem, simplify it a little bit, and you try relating it to another similar problem that you've solved before. Once you can correctly relate the problem to something similar you've solved earlier, then the solution is pretty straightforward.

  3. Creativity: This is the most difficult and elusive part for most people. This is needed when you have very little background on a problem, and yet you manage to create some way to solve it, in a way which you may have never thought about before.

After this discussion I kind of realised that throughout my life, I've never really been great at the creativity part. My strength has always been that I have a decent memory. I could look at some problem and relate it to another problem I solved very long ago, but rarely I could come up with completely new approaches, irrespective of how long I took to think about the problem. That is also pretty much how I got through high school, through memory and analogy. I believed that if I kept practicing I could improve these two, but the creativity part seemed very difficult to improve. I started to think that maybe becoming purple requires some level of creativity that I just can't reach.

After giving myself all these excuses I took a little break from coding, and one fine day I came across Radewoosh's blog. In case you haven't read the blog, you should definitely give it a read, it gave me a lot of insight. In short, what I took away from the blog was that, one common trait among people who excel at CP is that all of these people devoted some part of their daily lives to solving these problems passively. It's not just about actively sitting in front of your computer and practicing, but rather about how sometimes you tend to think about these problems while doing your daily chores and going about with your day. I realized that somewhere on my way, I had lost this. Earlier when I used to give long challenges, I used to think about problems even in the most random places. I once solved a problem while I was waiting for my friend in the volleyball court. The excitement after that to come to your room quickly and submit the code to check if it'll get accepted or not is unparalleled. I realized I had stopped enjoying all of this as I started worrying about rating too much.

I came to the conclusion that rating is just a rough number, and there isn't much point in obsessing over it. All I knew was, I enjoy solving problems on Codeforces, and I'm just going to continue to do that, without many expectations for rating. I acknowledged the fact that even if I can't do much about creativity, solving more problems will at least improve my analogy. And that is ultimately what I started doing in my 4th year of college, I started practicing problems just for the fun of it, and that's how I finally managed to become purple. And now I can say that even if you think you lack creativity, solving more problems will definitely improve your analogy skills, as you'll have a bigger pool of problems to relate to. In my last 3 contests where I was able to solve problem D (which I am usually unable to), I can definitely say that I was able to solve these because I could relate it to some other problems which I had upsolved earlier.

To summarize, as long as you enjoy solving problems here, keep doing it. Even if you think creativity is too hard to improve, your analogy can surely be honed, and that itself can get you quite far. Me becoming purple is the biggest indicator that it can be done using analogy, and since I've managed to do it, I don't see why anyone else can't given that they put in the right amount of effort with the right mindset.

Full text and comments »

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

By yellow_13, history, 18 months ago, In English

The following problems are from the Codenation coding round held on 12th June. I was not able to solve these problems, and it would be very helpful if you guys could give a rough idea of the solution.

Q1. You have two integer arrays $$$X$$$ and $$$Y$$$ of size $$$n$$$. Initially, all the elements in both these arrays are $$$0$$$. You have to process $$$q$$$ queries, each query can be of three types:

  • $$$1$$$ $$$l$$$ $$$r$$$ : Flip all $$$0$$$ to $$$1$$$ and all $$$1$$$ to $$$0$$$ in the range $$$[l,...,r]$$$ in the array $$$X$$$

  • $$$2$$$ $$$p$$$ : $$$Y_i = Y_i + p\cdot X_i$$$ for all $$$i \in [1,...,n]$$$

  • $$$3$$$ $$$j$$$ : Find $$$Y_j$$$

Input: $$$n$$$, $$$q$$$, and all the queries, Output: For every query of type $$$3$$$, print $$$Y_j$$$

Constraints: $$$1 \leq n \leq 10^5$$$, $$$1 \leq q \leq 5\cdot 10^5$$$, $$$1 \leq l \leq r \leq n$$$, $$$1\leq p\leq 10^9$$$, $$$1 \leq j \leq n$$$

Q2. Given a number $$$n$$$, find the number of actual greater pairs. A pair $$$(a,b)$$$ is an actual greater pair if:

  • $$$0 \leq a < b \leq n$$$
  • sum of digits of $$$a < $$$ sum of digits of $$$b$$$

Since $$$n$$$ can be very large, you have to input it as a string. Return the number of actual greater pairs modulo $$$1e9+7$$$

Input: $$$n$$$, Output: number of actual greater pairs modulo $$$1e9 + 7$$$

Constraints: $$$1 \leq n \leq 10^{100}$$$

Full text and comments »

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