#competitive coding

[excludedmiddle]

hey congrats on reaching CM (? wanted to find the post where you mention that to confirm but tumblr search misbehaves). was curious as to how many problems you've solved on cf? I primarily picked it up cause ik it helped friends with interview stuff but I'm 2 months in stuck at ~1200 so wondering if I should be doing things differently. on one hand most problems <1400 are greedy or math so I worry an actual interview will be more "algorithmic" and I'll be unprepared (maybe leetcode is better in this regard?). on the other hand it's soo much easier to fantasise about being good at cp than actually practicing. so. anyway wondering if you had any advice on this? CM in one year does not sound like the journey of your average cf-er. congrats again. cheers!

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:

[excludedmiddle]

Sometimes I look through the submissions of the guy who made my algorithms library for inspiration on how to use it better, and I often learn things about the library (or about Rust) that I didn't know.

But sometimes I look at something he's written and I think to myself. Sir I admit that you are better at competitive coding than I probably ever will be. But this cannot be the best way to do this.

[excludedmiddle]

im sooo bad at codeforces contests can u please help m. How did u do it

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?

Also, what's your motivation? Do you want to get a job? Into college? Just for fun? Beat your friends?

[excludedmiddle]

this is probably only funny to me but i do adore how every weird datastructure out there is basically just an array/list/vector/whatever you want to call a bunch of items right next to each other in memory, since literally any other data structure construction is wildly inefficient

SegTree? Nah son that's a SegList with a treelike abstraction grafted on top of it

[excludedmiddle]

Trying to get back on the horse with comp coding, it's been a couple of months since I last competed. I was thinking about how there are no real shortcuts you can learn BUT there are comp coding specific concepts that, after a certain point, really start to kill you if you don't know them.

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

FFT and its applications

[excludedmiddle]

Another one

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

Problem - B - Codeforces

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:

Particularly instructive here is his use of while let. In my implementation I used a more traditional Pythonic while loop ported over to Rust, but Rust very elegantly lets you unwrap the last element of b while also checking if it exists via pattern matching.

[excludedmiddle]

Also just found out that the cutoff for division 1 for codeforces isn't master rank, it's 1900 rating. So I can't compete in division 2 competitions anymore - it's only vs the big boys.

This is... kind of a bummer, to be honest. Div 1 competitions are a lot rarer than div 2 competitions, and they're also a lot more demoralizing. They have harder problems and (of course) much stronger competition.

[excludedmiddle]

Holy shit I made Div 1 on Codechef

There are only around 2000 Div 1 coders on Codechef