#competitive coding

Thank you!

(full disclosure: I've kind of fallen off with competitive programming - I haven't competed on codechef since January and codeforces/leetcode since April)

My solving totals, ratings, and number of contests are:

Leetcode: 824 problems, 2571 rating, 41 contests

Codeforces: 69 problems, 2000 rating, 14 contests

Codechef: 32 problems, 2046 rating, 4 contests

If you're looking for interview prep I would skip codeforces. Leetcode problems are closer to what you'll get in interviews, and their contests are much less of a time commitment. I also code in Rust on CF/CC and Python on Leetcode, and I much prefer to take interviews in Python.

If you snoop around a bit on reddit and the leetcode forums, you can often find lists of problems people have seen at a specific company's interviews to get a flavor of what you're up against. I really recommend this - the problem I struggled with the most in getting my current job was on one such list for my company and I wish I'd gone through the list. This was before I got really good, though.

I think my rapid growth was fueled by three things:

I did math competitions all the way through college that have a similar skillset

My college classes taught a lot of competitive programming concepts (I learned what a SegTree was in class!)

I had a period of 5 months between graduating and starting my job where I was unemployed and highly motivated, and I did a ton of grinding during that period. Most of my leetcode solves are from that time

If you're looking to improve but don't have a ton of time to burn, here's the regimen I recommended to another asker:

So the short answer is I started as a college graduate with a math/CS degree and then dedicated several hundred hours over the past year to getting better - I started with good fundamentals and then spent way too much time grinding.

I'm always happy to give advice but if you're looking for something more specific than "practice a lot" it helps to know where you're at - how much have you competed? What division do you compete in? How much CS background do you have? What language(s) do you use?

The progression is something like this:

Normie CS undergrad stuff:

Arrays sets dicts priority queues recursion binary operations binary search sorting etc

Slightly less normie:

Graph algorithms, dynamic programming

Things I have only used due to comp coding:

Inverses and factorials under large prime modulus

Tries

SegTrees

Things I know of but have never used, and apparently serve as even more advanced gatekeepers:

Convex hull algorithms

Graph flow algorithms

This is another cute problem - actually easier than the previous one imo:

We have an array and a bunch of additional numbers we could maybe add to the array - how do we add them in a way that avoids increasing the length of the longest increasing subsequence as much as possible?

This is an example of a codeforces problem that is very much a math problem at heart. You are looking to translate your requirements into some property that gets you what you want.

I don't have a lot to say about the solving process here because my intuition found the right answer pretty quickly - first, you sort your set of additional numbers b because you want to add them largest to smallest, and then you add the largest remaining number in b if it's >= the next number of a. If you have numbers left over at the end, add them all into the result from largest to smallest.

I think why this is rated 1700 despite having such a simple solution is that it's a little tricky to prove this intuition. You have to first imagine the largest increasing subsequence(s) preexisting in a (noting that it must still exist in the result), then argue that if you add larger numbers before that you cannot possibly make it longer. Similarly, adding the smallest numbers in reverse order at the end also cannot be worse, because they're all smaller than every element of a and in reverse order, so at best one of them can take the place of the last element of a.

Again let's look at Egor's implementation: