gojira's blog

By gojira, 4 months ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +371
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +47 Vote: I do not like it

About #4.

This is about not to hint if this is fft problem. Personally I don't like this, as if problem is ruined by hint "it's about fft" it's a bad problem. But the other opinion is kinda logical too.

About #5.

This is story about eliminating precision issues and hacks like "everything with probability less then 1e-20 is 0, and we can not process that". In many problems that is not an issue, in many it is. Also hard problems tends to have at list one of this issues, so in them it's reasonable. And probably this sets a faction at some point.

For example, in http://nerc.itmo.ru/archive/2019/nerc-2019-statement.pdf problem G we asked for double answer. Solution, which jury have was numerically stable, while some contestants got alternative one, which was not, and was forced to have bigintegers to have precise solution. If you have modulo you can't get such a problem, although answer become meaningless, which some people don't like. I have no strong opinion if it's good or bad.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Thanks for the context! Re: #5 — I understand the rationale and how it enables certain types of problems. On the other hand, for some problems noticing the "irrelevance" of states with minuscule probability was an interesting part of the solution.

    My main issue with probabilities modulo something is the loss of physical notion of the answer (I assume this is what you refer to as "meaningless"). For example, it manifests in debugging phase (I can intuitively understand if the probability of a given state can be 0.2, but not 402821992). Although to me personally, which I admit can be subjective, it's also about the overall quality of the problem — requesting some highly artificial value creates another degree of removal from "the real world" (and programming contests are already famously esoteric).

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +117 Vote: I do not like it

      For debugging meaningless modulo values, if you're a C++ user I recommend using some struct ModInt to perform all modulo calculations and use a type alias using M = ModInt<998244353>;. This way, you can replace the type alias line with using M = double; to see meaningful values when debugging and then just change it back before submitting.

»
4 months ago, # |
  Vote: I like it +48 Vote: I do not like it

If you think Li-Chao segment tree is evil, you should read about permutation tree.

»
4 months ago, # |
  Vote: I like it +100 Vote: I do not like it

cringe, especially #4 and #5. who cares about modulo, this is so insignificant, problems are not about modulo... i understand this is kind of humor, but bruh

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    As humorous as it was intended, I do feel quite strongly against probabilities modulo MOD.

    I commented about this right above in response to Pavel, but to unwrap it a bit further — I think the problems with some easy-to-grasp real-life meaning are more beautiful than dry mathematical statements.

    The more technical tricks we add to a problem to make it eligible for contest, the less accessible it becomes to a layman/newcomer. (Note that even modulo arithmetic is already a technical trick, but a relatively simple one that is necessary for most combinatorial counting problems.)

    As a paper dream, wouldn't you love it if you could share a problem with your non-CP friend and actually expect they might be interested in solving it? And yet, the chance of this diminishes with every single "known technique" we pile upon our problems.

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      Requiring probability modulo MOD doesn't change the way we solve problems if the answer is required to be exact. You don't need to mention modulo part to your friends. That's just some technicality which is required to make it CP problem.

      P.S. Just saw smax's comment. Yeah, basically change type to modint, no need to be philosophical.

»
4 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

About #4,

but not every problem does

I read somewhere that setters use this number for precisely this reason, if you use 998244353 for FFT problems and 10^9+7 for other problems, then the modulus becomes a hint, if you use 998244353 as the default modulus you leak less information

About #5, IDK how it started, but as a contestant I enjoy not worrying about precision issues. Actually I normally solve the problem using floats first (easier to debug / interpret) and switch to modulus at the end.

»
4 months ago, # |
  Vote: I like it +88 Vote: I do not like it

About #2 — at some moment both me and Petr just got too tired of dealing with problem authors unwillingness to take Java into account when setting time limits, so we switched to C++ (and I believe pashka did the same one year earlier). I since switched to Rust as it allows better level of abstraction without paying runtime costs

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    That's pretty sad. Having done a bunch of recent Yandex-hosted contests in Java, I can probably relate.

    Does every platform (aside from Topcoder, obviously) support Rust?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      USACO and COCI are notable absences. Also Codechef has ancient version, but they promised to update shortly

»
4 months ago, # |
  Vote: I like it +52 Vote: I do not like it

you forgot cheater report blogs

»
4 months ago, # |
  Vote: I like it +74 Vote: I do not like it

Regarding 6, I once proposed a problem (not on Codeforces) whose solution involves the Li-Chao tree built not using straight lines, but circles of the same radius. And several high school studets actually figured it out!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

About #4 and #5: I thought sometimes we can make problem more hard by adding MOD.

For Example: ICPC 2018 WF Gem Island can increase to $$$1\le n,d\le 1.5\times 10^7$$$ when adding MOD.

Sorry to my poor English.

»
4 months ago, # |
  Vote: I like it +62 Vote: I do not like it

A couple more things: almost every problem has multitests now, the hacks are completely abandoned, FSTs are rare and trying to fail participants by excluding some cases from pretests is a very quick way to get negative contribution for the round

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    almost every problem has multitests now

    Oh yeah I hate that too! Is it because Codeforces popularity rose through the roof, and servers cannot handle sets of 50 tests for so many submissions?

    the hacks are completely abandoned

    I didn't realize until you pointed it out — but your subsequent information explains the reasons well.

    excluding some cases from pretests is a very quick way to get negative contribution for the round

    So essentially problemsetters now cave in to public opinion, like celebrities and brands cave in to twitter mobs? How far we've fallen.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +39 Vote: I do not like it

      So essentially problemsetters now cave in to public opinion, like celebrities and brands cave in to twitter mobs? How far we've fallen.

      If that public opinion is right then it is a good thing :)

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        Then let's stop pretending we have anything but ICPC system with points

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it +13 Vote: I do not like it

          I would definitely be up for this if this is feasible

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Oh yeah I hate that too! Is it because Codeforces popularity rose through the roof, and servers cannot handle sets of 50 tests for so many submissions?

      Nah, you could just check the number of tests and see that it's still in tens. The reason's probably not letting wrong solutions pass systests because you limited yourself to less small tests.

      Removing hacks as a realistic thing is then caused by using those tons of small tests in pretests, but it doesn't have to be done.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it -63 Vote: I do not like it

    FSTs are rare

    golden lmao

    Trying to fail participants by excluding some cases from pretests is a very quick way to get negative contribution for the round

    lmao

»
4 months ago, # |
  Vote: I like it +123 Vote: I do not like it

Thanks to Numb for proposing new modulo 998244853

»
4 months ago, # |
  Vote: I like it +20 Vote: I do not like it

I do wish we had rounds in more varied time slots

Bruh I've been competing during meetings at work. Early afternoon isn't always that great either unless you live in a basement and eat frozen pizza and hotpockets.

I'm not sure how ruined your sleep schedule is but I slept through the last round. That was on Saturday afternoon. That means I don't really care when the rounds are because there's no telling if I'll be awake (or afk). If you can force yourself to sleep early, you're better off than me.

dozed off at every Codeforces contest I tried to wake up for

Ok, apparently not. Welcome to the club then.

»
4 months ago, # |
  Vote: I like it +38 Vote: I do not like it

Li-Chao tree is mostly a poor man's convex hull optimization, which is 69x slower, 69x memory hungrier, and takes 69x longer to code than the normal solution.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Had you used 911x somewhere as well, I would know for sure that you deciphered 0.07574094401 xD

»
4 months ago, # |
  Vote: I like it +75 Vote: I do not like it

Apparently the expected value modulo just backfired in CF Round 768.

»
4 months ago, # |
  Vote: I like it +40 Vote: I do not like it

Regarding #5, I swore a vow to myself to never propose problems with fractions modulo MOD.

We are not alone in this battle.

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

wow, you wrote codeforces round 196 (hope that I am right)! I took a virtual contest of that round, and learned a lot there. Thank you for preparing such wonderful problems!

Time flies, while things change. I also feel that problems nowadays are somehow quite different from several years ago. Maybe this is just how competitive programming itself evolves. Anyway, welcome back to codeforces, and hope that someday I could do as well as you.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +59 Vote: I do not like it

    Slightly off-topic, but hey, thanks for acknowledging me :) Thousands of people compete in contests, but only a few stop to leave a sincere kind word. You made my day.

»
12 days ago, # |
  Vote: I like it -16 Vote: I do not like it

In China, many people will use Li-Chao Segment Tree instead of nomal segment tree. Because it is short and it can solve the problem as well as the nomal segment tree.

»
12 days ago, # |
Rev. 4   Vote: I like it -6 Vote: I do not like it

I don't think Li Chao trees are really too complicated or obscure of as an idea. It has a name that some programmers gave it but it's really just a nice application of segtrees for convex optimization.

A bit like Mo's algorithm which has a name that only became more common in recent years in CP community but the underlying main idea of sqrt decomposition was always standard and well known.