Hi, I am fairly new to the Competitive Programming journey, solving problems for little over a month.
A gist background : I enrolled in a boot-camp for DS and Algorithms, learnt the tricks and methodology, but was overwhelmed for a large portion of the course. I have an overview of it and some basic understanding, but that's about it. After completing the course, I switched over to Codeforces, Codechef and some other online CP sites.
I have been solving problems for a month now, sorted according to ratings, i.e. 400-700 and lately some of the problems with 800. After a while, I gave 3 contests, Educational Codeforces Round 84 (Rated for Div. 2) , March Long and Cook-off of Codechef as I wanted to have a real-time experience of how competitive programming goes about. I fared bad, obviously. Solved a question each in the Codechef contests, and couldn't even solve the first problem in Educational Codeforces Round 84 (Rated for Div. 2). Rating and failure doesn't bog me down, and it won't. But the problem I seem to have is of proper guidance and trajectory on which I can take action.
To make it more clear, here are the issues I am facing:
- What topics should I study to be able to solve A, B and C problems as of now?
- How many Type A problems to solve before switching to the problems with higher rating/increased difficulty?
- What techniques(DP, Greedy, Backtracking etc.) should I learn and try to use currently?
- Do I study basic Algebra like Euclidean/ Extended Euclidean algorithm , easier topics of Number Theory, and how important are they?
- When should I start with topics like Graph Theory, Disjoint Set Union and beyond?
I know these are a lot of questions, but these are some genuine problems I have been facing. Please cut me some slack as it is my first post, thanks!
There is a very nice blog written by E869120. Go through the section "3-1. Practice Skills — From Rating 1000 to 1400" of this pdf.
Link of blog
Thanks, this was really helpful.
For me, the most effective way of learning CP is by upsolving problems that you failed to solve in contest. There are editorials for that reason. If there are unfamiliar names (of algorithms/techniques/etc), google them. If you still don't understand the editorial, ask in the comment section. This is probably because when you failed to solve a problem, and knowing the solution later, it gets an adhesive upgrade that lets it stick to my head better (basically my chance of remembering it rises).
Alternatively, you can go to sites like https://projecteuler.net/ that doesn't require you to code, but still trains your logic. This site makes me realize that simply having paper and pen when solving cp problems is helpful.
Btw, answering your issues:
You can also google something like
codeforces starting out competitive programmingif you haven't already.how many problems u have solved at projecteuler? just curious! tnx
I don't remember. Probably 20 or so. I even forgot my username and password. But, it's still a good place to practice.
I don't use projecteuler a lot because I had an alternative site. But it's in another language that is not english, so I cannot recommend that.
Sorry but even if it's not in English can you please share the name of that website....
https://tlx.toki.id/
https://osn.toki.id/arsip/
Thx bro... :)
Thanks, the answers to 1 and 2 are really helpful. I will jump right into solving B and C problems, which I was avoiding until now. Thanks again for helping out!
Dude, I think, First read about most of the commonly used algorithms in Contests.
Like- DSU, DFS, BFS, Shortest Paths, Dynamic Programming etc.
For that, I'd prefer https://cp-algorithms.com/
It's a great resource. Don't judge it by it's UI. The resource is a gem. GOod luck and happy Learning
Thanks, I have known about this site, was recommended by a good friend. Thanks for your input!
For each of your issues:
First, the difficulty of A, B and C problems in different Div 2 contest is not always the same.
For example, 630A is not very difficult to get the answer, but it is quite difficult to code than a usual Div2A. 632A is quite easy to code (just as many other Div2As), but it is quite difficult to get the answer.
Solving a Div2A might also be hard for beginners, too.
In my opinion, in order to solve most of the Div2As, you should know a bit of greedy (and how to proove it is correct), some math skills.
If you want to solve most of the Div2Bs, you should learn bit of linear DP, strings, sortings, binary search and some basic graph theory knowledge (i.e. how to build a graph), and maybe some bitwise calculation will be helpful.
If you want to solve most of the Div2Cs, you should learn DFS, BFS, DSU, etc.
Sorry for my poor English...
Thanks, this helped a lot. Where can I practice good Greedy questions?
Hmm...
Is greedy questions in CodeForces not good enough?
If you have a good translator or you can read Chinese, I recommend a CP website for beginners which is well-known in China: Luogu. There are some greedy questions there. There are lots of tutorials to help you if you can't solve some problems.
However, I think greedy questions in CF is good enough.
Would like to add to the first point... Data structures like vector, set, map, priority_queue, deque etc are quite important for implementation problems. Also Number theory problems related to gcd, lcm, modular arithmetic, primes, divisors, sieve etc are frequently asked.
I'm not sure if this is going to help but- to answer all your problems, I would suggest simply spend some more time on whatever you're currently trying to do. With time you'll either realise whatever you're doing is working for you — where you should just keep doing so until it's not the case anymore; or you'll realise that you need a difference in strategy. I have experienced that I do find the solution to my own problems with time. And I personally felt uneasy when I tried to follow somebody else's workflow.
Otherwise, I suggest reading Errichto's FAQ blog where he answers questions like "How to get better at CP". He has also started a new series of videos to introduce people to CP on his youtube channel.
You should start by studying basic implementation, brute force and math (a lot of div2A's are math based). Once you get comfortable with that, look into binary search, two pointers, constructive algorithm questions. If you're wondering when you should move up the difficulty of your problems, it should be when you can solve the majority of the problem rating you're practicing at right now. Don't try to jump to dynamic programming or graphs etc. I tried that and it didn't get me anywhere. I've been solving ~1200 rated problems on the topics I'm weak at and I can already see improvement.