Beating 100% C++ submissions in Leetcode.

Or fighting pesky inputs... again...

We’ve already discussed how slow input processing can negatively affect runtime for programming contest submissions, but it’s especially annoying when it comes to C++ - after all it’s particularly terrible to find out that our efficient algorithm performs poorly just because of slow input.

To illustrate the issue, let’s take a simple leetcode problem that is for some reason marked as medium.

You are given two strings s and t. In one step, you can append any character to either s or t.

Return the minimum number of steps to make s and t anagrams of each other.

An anagram of a string is a string that contains the same characters with a different (or the same) ordering.

Since both strings must contain the same characters and we can only add characters, it’s fairly obvious that the final anagram will contain the maximum count of characters of original strings. The total of differences between this max and the count of characters in each string would give us the result. Something like this

Even though it’s an obvious solution which can be further optimized by using a single counter instead of 2, it’s still fairly efficient and I expected this submission to beat at least 50% of other submissions. Well, I was wrong

That’s where I could have started optimizations like reducing number of counters, avoiding c - ‘a’ by extending counter size and using other low-level tricks, but what if we add

instead?

Let’s see

And looks like we are now beating 100% of other submissions. Not bad for 2 line boilerplate change.

The best way to understand why it helps is to read the documentation for sync_with_stdio and cin’s tie, but TL;DR; is that they have to do with synchronizing iostream infra with C’s way of handling IO and in/out synchronization respectively.

Note, that these lines are invoked as part of lambda that is invoked pre-main, so that the synchronization is disabled before leetcode infra processes inputs of submissions.

Moral of the story? Algorithms and data structures are still what matters the most, but there is no need to waste time on unnecessary synchronization.