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?
Anyone have experience with Codeforces or competitive programming in general? I’m very curious about that whole world and would love some insight on it (advice, opinion, resources, etc.)
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:
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.
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.
First div 1 only competition! Went... fine, I suppose. Gained a bit of rating, could've gained a lot more if I trained interactive problems a bit.
A - Okay don't laugh at me. I took a while on this problem. I think in large part because of how early the competition was, it took me a while to get warmed up and actually figure out what the fuck is going on with this one. I figured out the trick for even-length arrays but assumed it was universal - once I figured out that every odd-length array worked, I got it. (37 minutes, 2 failed subs)
B - A dreaded interactive problem - instead of getting all the information at the start, you have to send out queries and receive information back. I haven't practiced these at all, like literally never solved one despite knowing of their existence.
I kinda turned my brain off for it. The actual solution isn't that bad I think - you do a bunch of queries to form a long line, and then you can do a bunch more to find an endpoint. Either way, didn't get this one.
C - My savior was this really interesting problem. Took me a bit to play with it conceptually, but you can do a BFS starting from 1 and map each node to a tier based on its distance from 1, by dependency. If a node isn't in the tier mapping, it's infinite. Otherwise, you can recursively construct the ideal pattern in O(n^2) using your tier mapping. (65 minutes, tho some of this was on B)
Gained a bit of rating! Currently just under 2000 rated. I think I'm definitely on track to make Master (2100) by August - that didn't feel like my best effort, and I'm still gaining rating.
Managed to avoid complete catastrophe here but still only got 3/6. Placed something like 3000th out of 13k.
A - simple problem that could be solved in a few lines. A nice warmup for what was to come.
B - also an easy problem, if you read it correctly! Which I didn't. And also, I didn't check to see if I had gotten it right before moving onto C. Which means I checked the standings halfway through the contest and panicked when I saw that I got it wrong and had a second failed submission because I fixed a small bug but not my complete misreading of the problem.
Anyway! Self-inflicted wounds here that derailed my contest.
C - kind of a nasty one, in that I had to cycle through a few math approaches before I found the correct one. Here's the correct one:
Everyone always plays their highest card all the time - this is optimal. You can split each round into a few options: the player whose turn it is has the highest card, generating (n - 1) choose (n / 2) possible winning arrangements for them, the player whose turn it is has some shit card, meaning the other player will immediately win next turn (i - 1) choose (n / 2 - 1) wins for them, for i in range n / 2, n - 1. Or the player whose turn it is plays the second highest card, in which case you flip the turn, subtract 2 from n, and recurse.
Now for the other funny part - this is all modular arithmetic under some fucked up modulus, requiring combinations.
Here's the good news: I stand on the shoulders of giants. Egor's algorithm library has modular arithmetic tools, including combinations.
Here's the bad news: This was my first time using any of them, so it took me ages to figure out what the fuck was going on.
Fortunately, Egor is a genius and his tools are designed so elegantly that I just sorta did what was intuitive and it ended up working out, and I solved C with like 5 minutes left in the contest, avoiding placing 9000th or whatever.
This one kicked my ass! I feel tired and slow, and I think I need to go to bed even earlier if I want a chance at tomorrow's.
