Hello friends!

As I've recollected in a previous post, I am an old competitor who hadn't really participated since ~2014, and recently got a bout of nostalgia to return to Competitive Programming. So, I did a couple Topcoder SRMs, suffered through some SNWS rounds, participated in three regional 5hr competitions on three consecutive days, and dozed off at every Codeforces contest I tried to wake up for.

A lot of things are still the same as 8 years ago: tourist is still at the top, grey coders still ask for how many minutes to solve a problem before reading the editorial, Russian university teams continue winning ACM ICPC, and Snarknews never gives up on his alternate competition formats. But in this post, I want to focus on the new patterns that emerged since my last time around.

#1: Codeforces rounds timing

Did you know that there used to be a time when not ALL the freaking CF rounds were held at 5:35pm MSK? Back in the day, no matter what timezone you were in, there would be an occasional round you could compete in without having to interrupt your sleep (or your work).

I'm personally pretty salty because 5:35pm MSK is like 6:35am in my timezone, and my brain simply refuses to operate for 2 consecutive hours this early in the day. And while a quick check of Ratings shows that most users are congregated in between Moscow and Japan timezones, I do wish we had rounds in more varied time slots.

#2: Petr and Java

Did you know that Petr used to write all contests in Java? Imagine you were looking for an intelligible implementation of any contest problem. You would sail through the ocean of C++ submissions filled with FOR0(n) and #define int long longs, and spot the safe haven of Petr's delightful Java solutions that read like a page from Dostoyevsky's masterpieces. His variable names alone could teach you more about solving this problem than the editorial itself. In fact, I was under an impression that Petr did not use prewritten code, and created each of his beautiful algorithms from scratch every time.

Well folks, those days are gone. Checking Petr's recent submissions, I noticed that he turned to the dark side and the values in his Lang column for over 2 years now show... this:

#3: The AtCoder library and the Codeforces Catalog

There is another curious pattern in the submissions of some top contestants: namespace atcoder and a myriad of data structures and algorithms that magically pop out of this namespace, like a rabbit from a magician's top hat. The source of all this sorcery seem to be the AtCoder library. I mean, come on, red and nutella coders, can't you even write your own min-cost max-flow over a network generated by lazy propagation segment tree with 2-SAT FFT butterflies stored in each node? Meh!

More generally, I can see there is a whole catalog here on CF, with links to tons of educational materials. And, in all seriousness, that's awesome — there was but a fraction of this available back when I was a student!

#4: The new MOD to rule them all

A lot of programming contest problems request to find some value modulo a large prime. The most common reason for this is that we are counting the number of ways to do something, but this quantity is extremely large. By requesting the answer modulo a large prime, we keep the calculations in a datatype that fits into machine word, thereby letting the solver focus on the "interesting" part of the problem.

10 years ago, the most common moduli used in contest problems were 1,000,000,007 and 1,000,000,009. These are nice, easy to remember big primes whose sum fits into a signed 32-bit datatype, making them perfect for the scenario above. Or maybe they were not, because fast-forward to today, I saw like 10 different problems requesting the answer modulo...

998244353

I mean, seriously, what the fuck is this? This is one ugly-ass forgettable prime and you should be ashamed for using it in your problems!

P.S. I found Petr's blog post discussing the properties of this number. And it seems like the problem where it was introduced at the time actually relied on these properties, but not every problem does! Also, this post is from 2014 — are y'all telling me you've been using nine-nine-eight-two-four-four-three-five-three in contest problems since 2014!?

#5: Probabilities modulo MOD

One of my favorite topics in programming contests was always probabilities and expectations. You can just feel the blood coursing through your veins when your dynamic programming solution prints out a sexy 0.07574094401. But y'all had to ruin this as well by introducing... probabilities modulo a prime!? o_O

Most probability theory-related problems I've seen in the past months request the answer modulo, you guessed it, 998244353, and proceed to add a note explaining that the answer can be represented as p/q where q is not a multiple of the given modulo. So essentially now to solve any problem with probabilities you have to also throw in some number theory and probably even more combinatorics. And you can't even receive a 0.07574094401 as an answer!

Can anyone explain how this new fad started?

#6: Li-Chao Segment Trees

Saving the best for last! A couple weeks back, I was delightfully reading Um_nik's list of things he allegedly does not know, and it was heralded by a data structure called a Li-Chao Segment Tree. I initially thought that this was a joke, but a quick google search revealed that people write tutorials on this thing.

Then I told myself that surely nobody would bring a problem utilizing a Li-Chao Segment Tree on Codeforces, but the very next Codeforces round editorial made sure to prove me wrong by mentioning a Li-Chao tree (I didn't dig into details, but you get the point!).

Come on guys, was Heavy-Light Decomposition not an obscure enough data structure to bring to contests? Someone has to stop this madness!