#coding competition

[excludedmiddle]

Codeforces Weekly 865 (Div 1!!)

Link

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.

[excludedmiddle]

Hmm. Leetcode contest went... bad, tbh. I got all 4 questions with no wrong subs but was extremely slow, did worse than either of the prior two contests. It's not a terrible result but kinda hammering home that I need to practice more if I want things to get better

[excludedmiddle]

If anyone (@wuggen, @birth-muffins-death, etc) wants to have a bad time, here's an absolute nightmare problem I just learned how to solve:

Given an array A of positive integers, the score of a subsequence (a continuous slice of size at least 1) is the sum of the elements of the subsequence times the minimum element of the subsequence.

Find the sum of the scores of all of the subsequences of the array in O(n) time, where n is the length of the array.

For ex: A = [1, 2, 3].

Subsequences:

[1] = 1 * 1 = 1

[2] = 2 * 2 = 4

[3] = 3 * 3 = 9

[1, 2] = 1 * (1 + 2) = 3

[2, 3] = 2 * (2 + 3) = 10

[1, 2, 3] = 1 * (1 + 2 + 3) = 6

Total score = 1 + 4 + 9 + 3+ 10 + 6 = 33.

More than happy to provide hints, this one is a real challenge.

[excludedmiddle]

So. Still waiting on that system testing. But provided none of my solutions have hidden bugs, I got 5/6 questions and placed around 500th (out of the 11k people who are rated for the contest) and around 700th if you count the ~200 Div 1 contestants who placed above me.

[excludedmiddle]

Had another disappointing leetcode run (which I might not even bother writing up) but I think I'm gonna spend some time now switching my language to Rust. Going from how incredibly smooth Python is to how clunky Rust feels seems like a downgrade, but I'm planning on expanding the types of contests that I do to ones that require speed, and I want to learn more Rust anyways.

[excludedmiddle]

Weird experience I'm having with competitive coding is that I think I'm already trying to overgeneralize my limited toolkit, like I'll see a problem and connect it to a trick I know how to do (most infamously with linked lists but also with DP) and then I'll swap out of thinking mode and swap into implementation mode, and then I'll write this whole thing up, and then only after it times out do I realize that there's a much simpler method. And I do this... kind of a lot, like it's probably my number one failure state.

Today's leetcode question of the day wasn't even hard, but I took a DP approach because I knew it would be correct but it was too slow. Then I thought about it for like. Two more minutes and came up with a much, much faster priority queue version. Stupid. If I'd just prolonged the thinking period, I would've saved myself ten minutes of implementation.

This is especially problematic with DP because sometimes the asymptotic runtime is harder to calculate, or weirder, I guess, so it's hard to know for sure if you're fucked or not before you actually implement.

[excludedmiddle]

Codeforces thoughts

In addition to my leetcode contests and practice, I'm starting to practice on codeforces (and will hopefully compete there once I feel like I have the hang of the format).

It's a real shift! It's clear that the implicit audience is no longer undergrads or high schoolers looking to get a leg up on coding interviews, but rather people with professional coding jobs who are doing this as a rather intensive hobby.

Some major differences:

No more time-out modifiers: The amount of time your code has to run isn't language-dependent, which means that Python or even Java solutions can time out even if they're asymptotically correct. Most people use C++ as a result, but for me, that means I'll be using Rust.

Editing locally is incentivized: Leetcode basically forces you to edit using their pre-built browser editor - there's no option to submit your own code, it generates your function wrapper for you and gives you your expected inputs, and it lets you test in-browser.

Conversely, codeforces has a browser editor, but it doesn't give you anything, and you can submit files, so you're much better off editing locally. I'm also using a Firefox extension combined with a command line tool to set up my workspace for me and scrape the given tests off the web. This makes editing locally remarkably convenient.

IO is also different - leetcode just hands you your inputs as variables you can work with, and expects you to return your outputs. Codeforces writes your inputs to stdin and expects you to write your outputs to stdout. This would be really annoying in Rust, except I'm borrowing code which handles all of the messy bits for me.

Shit's harder: Leetcode only has three levels of problem, Easy, Medium, and Hard. Easy problems tend to be extremely trivial, medium problems range from a couple minutes of thought and coding to around half an hour, and Hard problems get quite difficult.

Codeforces problems are assigned a rating, starting at 800. The equivalent to Leetcode Hard problems start showing up around rating 1500. The highest rated problems on the site are well over 3000-rated.

On leetcode, contest winners finish the 90-minute contest in under 20 minutes. On codeforces, you'll see contests where almost no one solves all of the problems. As a consequence of this and editing locally:

You're expected to use an algorithms cookbook: You can't just go in blind and rewrite Djikstra's every time you encounter a graph problem, recreate Segtrees every time they end up being useful, or get away with using built in utilities like @lru_cache in Python every time you want to use dynamic programming. Reusing useful code is essential.

This would create a big problem with having to copy-paste code, except I can just import stuff and the command line tool will just automatically copy the code for all of my dependencies into the submission file, which rules.

All and all: very excited to be working with harder problems on a site that's more competitively focused. If anyone else finds this appealing (@birth-muffins-death, @wuggen) let me know and I can send you/walk you through all the stuff I picked up that makes your work environment nice.

[excludedmiddle]

Codeforces 818 (Div 2)

Link

My first codeforces contest! Slightly disappointing for reasons I'll get into below, but mostly I'm just happy to have finally gotten my shit together and competed. Here's to the first of many.

A was simple (6 minutes). Didn't even really derive the math behind it, just assumed n + 2 * (n / 2) + 3 * (n / 2) would work, and it did.

B wasn't hard but it was a pain in the ass, since I had to figure out how to extend Rust vectors from themselves. Took me 27 minutes, mostly for "does not know the language very well" reasons. Also had a (penalty-less) failed submission here which took me more time to correct, because they indexed from 1 instead of 0 (???).

C was easier than B, at least timewise (11 minutes). Just iterate through both arrays, checking that certain conditions are met.

D was really quite hard. I don't have a setup to do modular exponentiation yet, so I had to do so by hand. I also wasted a bunch of time trying to figure out why my code wasn't working because they switched from multitests to single tests on that problem and I didn't notice.

I made an error in my initial submission, and by the time I diagnosed it and figured out how to fix it, time had just barely expired. I'm not kidding when I say another minute and I would've gotten another submission off (not sure if it would've been correct, will find out soon). EDIT: It was also wrong. Probably would've taken me at least another 15 minutes to fix that one up.

For the most part, this was about what I expected from a Div 2 contest: got the first three problems pretty much without incident, spent the entire rest of the competition bashing away at the fourth, only to fall short.

I placed in the mid 1500s out of around 11k, which I'm pretty content with. Most of the people around me who've done more than a handful of competitions have ratings in the 1600-2000 range, which is about where I consider my own skill level to be, based on the problems I can solve.

You gain rating pretty slowly on codeforces and I don't know how frequently I'll be able to compete, but I hope within a year from now I can achieve the Master rating of 2000 (which would drop me out of Div 2 entirely). I think that's kind of a bonkers goal (there are only 2652 Div 1 coders [2000+ rating] out of 127k total users), but hey, if you aren't shooting for top 2% in the world, what's the point amiright.