C++ in Competitive Programming: compromises

Posted: September 30, 2016 in Competitive Programming
Tags:

Crafting software is about balancing competing trade-offs. It’s impossible to optimize every factor of a system, as speed, usability, accuracy, etc at the same time. Moreover, solutions of today impact decisions and solutions of tomorrow. On the other hand, in Competitive Programming, the best solution is one that just makes each test-case pass.

However, since each challenge has specific requirements and constraints, we can still imagine it as a small and simplified component of a bigger system. Indeed, a challenge specifies:

  • the input format and the constraints of the problem;
  • the expected output;
  • the environment constraints (e.g. the solution should take less than 1s);
  • [optional] amount of time available to solve the challenge (e.g. 1 hour).

Questions like: “can I use a quadratic solution?” or “may I use extra space?” will be answered only by taking into account all the problem information. Balancing competing trade-offs is a key in Competitive Programming too.

This post is a bit philosphical, it’s about what I consider the essence of Competitive Programming and why a professional could benefit from it. Since February of this year I’ve been monthly organizing “coding dojos” on these themes, here in Italy. After some months, I’m seeing good results in people regularly joining my dojos and practicing at home. It’s likely that in the future I’ll dedicate a post about how dojos are organized, but if you want more information now, please get in touch.

Follow me through this discussion and I’ll explain you some apparently hidden values of Competitive Programming and why I think they are precious for everyone.

Let me start by stating that the only real compromise in Competitive Programming is one that makes an acceptable solution. However, we distinguish two distinct “coding modes”: competition and practice. Competition is about being both fast and accurate at the same time. You just have to correctly solve all the challenges as fast as possible. On the other hand, practice mode is the opportunity to take time and think more in deep about compromises, different approaches and paradigms, scalability, etc. In practice mode we can also explore the usage of standard algorithms. A story about that concept: at one of my dojo I proposed this warm-up exercise:

Given two arrays of numbers A and B, for i from 0 up to N-1, count how many times A[i] > B[i].

For example:

A = [10, 2, 4, 6, 1]
B = [3, 2, 3, 10, 0]

The answer is 3 (10>3, 4>3, 1>0).

This exercise was trivial and people just solved it by looping and counting.

During the retrospective I asked people: “can you solve this problem without looping explicitly?”. I lowered my aim: “Suppose I provide you a function which processes the arrays pair-wise”. One guy plucked up courage and replied ” like ZIP?”. I said “Yes!”. I dashed off the blackboard and showed the idea.

The C++ algorithm to use in this case was std::inner_product, that we already met in the very first post of this series. I’ll get back to inner_product again in the future, meanwhile here is the slick solution to this problem:

As we already saw, inner_product is kind of a zip_and_reduce function. Each pair is processed by the second function (greater) and results are sequentially accumulated by using the first one (plus). People realized the value of applying a known pattern to the problem. We discussed also about how easy it is to change the processing functions, getting different behaviors by maintaining the same core algorithm.

In this post I’ll show different scenarios by turning on “practice mode” and “competition mode” separately, discussing the different ways to approach problems and care about compromises in both.

Consider the problem we tackled in the previous post: the “most common word”. Since we used std::map, the solution was generic enough to work with types other than strings with a little effort. For example, given an array of integers, we can find the mode (as statisticians call it) of the sequence.

Imagine this solution still fits the requirements of the challenge.

In “competition mode”, we stay with this solution, just because it works. The pragmatic competitive coder was lucky because she already had a solution on hand, so she just exults and lands to the next challenge of the contest.

Now, let’s switch “practice mode” on. First of all, we notice two interesting constraints of the challenge: 1) the elements of the array belong to the range 0-1’000; 2) the size of the sequence is within 100’000. Often, constraints hide shortcuts and simplifications.

Ranting about life in general and not only about programming, I use to say “constraints hide opportunities”.

In Competitive Programming this means that whenever we see particular sentences like “assume no duplicates exist” or “no negative values will be given”, it’s very likely that these information should be used somehow.

Sometimes “very likely” becomes a command and we won’t have other options to solve the challenge:  we have to craft a solution which exploits the constraints of the problem. Such challenges are interesting since they require us to find a way to cut off the space of all the possible solutions.

Anyway, back to the mode problem, since we know the domain is 0-1’000, we can just create a histogram (or frequency table) and literally count the occurrences of each number:

Although the solution is similar to the previous one (because std::map provides operator[]), this is dramatically faster because of contiguity.

However, we agreed to a compromise: we pay everytime a fixed amount of space to allocate the histrogram (~4 KB) and we support only a fixed domain of ints (the ones within 0-1’000). That’s ok for this challenge, but it could not be the case in other cases. Balancing speed, speed and genericity is something to think about in practice mode. In my coding dojos in Italy we use to discuss about such things at the end of each challenge, during a 15-min retrospective.

At this point we need to answer a related question: “are we always permitted to allocate that extra-space?”. Well, it depends. Speaking about stack allocations – or allocations known “at compile-time” – compilers have their own limits (that can be tuned), generally in order of a few MB.

The story is different for dynamic allocations. On websites like HackerRank we may have a look at the environment page which contains the limits for each language. For C++, we are usually allowed to allocate up to 512 MB. Other websites can limit that amount of space, typically per challenge. In these situations, we have to be creative and find smarter solutions.

Take InterviewBit as an example – a website focused on programming interviews. A challenge states: “given a read only array of n + 1 integers between 1 and n, find one number that repeats, in linear time using constant space and traversing the stream sequentially”. It’s clear that we cannot use an auxiliary data structure, so forget maps or arrays. A solution consists in applying a “fast-slow pointer strategy” – so does Floyd’s algorithm. I won’t show the solution because very soon we’ll have a guest post by Davide Di Gennaro who will show how to apply Floyd to solve another – more realistic – problem.

Space and time have a special connection. The rule of thumb is that we can set up faster solutions at the price of using more space, and viceversa. It’s another compromise. Sorting algorithms are an example: some people amaze when they discover that, under certain conditions, we can sort arrays in linear time. For example, you know that counting sort can perform very well when we have to sort very long sequences which contains values in a small range – like a long string of lowercase alphabetic letters.

Counting sort allocates an extra frequecy table (a histogram, as we have just seen), containing the frequencies of the values in the range. It exhibits linear time and space complexity that is O(N+K), where N is the length of the array to sort and K is the length of the domain. However, what if the elements go from 1 to N^2? Counting sort exhibits now quadratic complexity! If we need to care about this problem, we can try adoperating another algorithm, like Radix sort, which basically sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value.

Radix sort has also other limitations, but I won’t go into details because it’s not the point of this article. Again, I just want to highlight that other decisions have to be taken, depending on the requirements and the constraints of the problem. A general rule is that often we can exchange space for making faster solutions. Space and time go hand in hand.

Time is constrained as well: typically 1 or 2 seconds on HackerRank. To give you some feeling about what it means, let’s write down some time evidences measured on HackerRank’s environment.

std::accumulate – O(n) – on vector<int>:

100’000 elements: 65 microseconds

1’000’000 elements: 678 microseconds

10’000’000 elements: 6973 microseconds (6.973 milliseconds)

However, don’t be swayed by complexity. Time is also affected by other factors. For example, let’s try accumulating on std::set:

100’000 elements: 747 microseconds

1’000’000 elements: 16063 microseconds (16.063 milliseconds)

10’000’000 elements: timeout (>2 seconds)

You see that contiguity and locality make a huge difference.

Imagine now what happens if we passed from N to N^2. Roughly speaking, we can just square the time needed to accumulate a vector of 100’000 elements to get an approximation of what would happen: we obtain ~4.5 milliseconds. If the challenge expects at most 1 second, we are able to afford it.

Should we submit such a quadratic solution?

Again, we may in competition mode. Instead we should think about it in practice mode. What if the input grows? Moreover, special contests run extra tests once a day, generally stressing the solution by pushing inputs to the limit. In this case, we need to understand very carefully our constraints and limits.

Compromises also originate from the format of input. For example, if we are given a sorted sequence of elements, we are enabled to binary-search that sequence for free (that is, we don’t need to sort the sequence ourselves). We can code even more optimized searches if the sequence has also some special properties. For instance, if the sequence represents a time series containing samples of a 10-sec acquisition, at 100 Hz, we know precisely – and in constant time – where the sample of the 3rd second is. It’s like accessing an array by index.

The more we specialize (and optimize) a solution, the more we lose genericity. It’s just another compromise, another subject to discuss.

Compromises are also about types. In previous posts we have faced with problems using integer values and we have assumed that int was fine. It’s not always the case. For example, many times problems have 32bit integer inputs and wider outputs – which overflow 32bit. Sometimes the results do not even fit 64bit ints. Since we don’t have “big integers” in C++, we have to design such facility ourselves or…switch to another language. It’s not a joke: in “competition mode”, we just use another language if possible. It’s quicker.

Instead, in “practice mode” we can design/take from an external source a big integer class, for being reused in “competition mode”. This aspect is particularly important: when I asked to some top coders their thoughts on how to constantly improve and do better, their shared advice was to solve problems and refine a support library. Indeed, top levels competitive coders have their snippets on hand during contests.

This is a simplistic approximation to what we actually do as Software Engineers: we solve problems first of all by trying to directly use existing/tested/experienced solutions (e.g. libraries, system components). If it’s not the case, we have two options: trying to adapt an existing solution to embrace the new scenario, or writing a new solution (“writing” may mean also “introducing a new library”, “using some new system”, etc). Afterwards, we can take some time to understand if it’s possible to merge this solution to the others we already have, maybe with some work (we generally call it refactoring). You know, the process is more complicated, but the core is that.

Using or not an existing solution is a compromise. Mostly because the adapting and refactoring parts require time and resources.

I think everyone would love writing the most efficient solution that is also the simplest. Generally it’s not the case.

However it happens in many challenges – especially in the ones of difficulty Easy/Medium – that “average solutions” are accepted as well (these solutions work for the challenge, even if they are not the “best” – in terms of speed, space, etc).

The balance between the difficulty of a solution and its effectiveness is another compromise to take into account. About that, I tell you a story I lived a few days ago at my monthly coding dojo. We had this exercise:

Given a string S, consisting of N lowercase English letters, reduce S as much as possible by deleting any pair of adjacent letters with the same value. N is at most 100.

An example:

aabccbdea

becomes “dea”, since we can first delete “aa”getting:

bccbdea

Then we delete “cc” and get: “bbdea”, finally we remove “bb” and get “dea”.

The attendees proposed a few solutions, none of which exhibited linear time and constant space complexity. Such a solution exists, but it’s a bit complicated. I proposed that challenge because I wanted people to reason about the compromises and, indeed, I made one point very clear: the maximum size of the string is 100. It’s little.

We had two leading solutions: one quadratic and one linear in both time and space. The quadratic one could be written in a few lines by using adjacent_find:

The other one adoperated a deque (actually, I have seen such solution applied many times in other contexts):

Both passed. Afterwards, we discussed about the compromises of these solutions and we understood limits of both. In a more advanced dojo, I’ll propose to solve this challenge in linear time and constant space!

Competitive Programming gives us the opportunity to see with our own eyes the impact of self-contained pieces of code, first of all in terms of time spent and space allocated. As programmers, we are forced to do predictions and estimatations.

Estimating and predicting time/space is fundamental to decide quickly which solution is the most viable when different compromises cross our path. Back to the mode example, using std::map or std::vector makes a huge difference. However, when the domain is small we are allowed just not to care about that difference. Somehow, this happens also in ordinary software development. For instance, how many times do we use streams in production code? Sometimes? Never? Often? I think the most fair answer would be “it depends”. Streams are high-level abstractions, so they should be relatively easy to use. However, they are generally slower than C functions. On the other hand, C functions are low-level facilities, more error prone and less flexible. What to do entirely depends on our needs and possibilities, and very often also on the attitude of us and our company.

Although Competitive Programming offers a simplified and approximated reality, facing a problem “as-is” it’s an opportunity to understand compromises, estimate time and space, adapt known solutions/patterns to new scenarios, learn something completely new, think outside the box.

The latter point is related to another important fact that I see with my own eyes during my coding dojos in Italy: young non-professional people often find clever solutions quicker than experienced programmers. The reason is complex and I have discussed about that also with psychologists. To put it in simple terms, this happens because young people generally have a “weaker mindset”, have less experience and are not afraid of failure. The latter point is important as well: many professionals are terribly afraid of failures and of making a bad impression. Thus, an experienced solution that worked seems more reliable than something completely new. That’s basically a human behavior. The problem comes up when the experienced programmer cannot think outside the box and is not able to find new and creative ways to solve a problem.

Competitive Programming is a quick and self-contained way to practice pushing our “coding mind” to the limits. As a Software Engineer, programmer and professional, I find it precious.

Competitive Programming offers both a “practice mode”, during which I can “stop and think”, reasoning about compromises, time, space, etc. And a “competition mode”, where I can “stress-test” my skills and experience.

Learning new things is often mandatory. This needs time, will and patience. But you know, it’s a compromise…

Recap for the pragmatic C++ competitive coder:

  • Compromises in Competitive Programming have different shapes:
    • Dimension and format of the input;
    • Time and space limits;
    • Data types;
    • Adaptability of a well-known solution;
    • Simplicity of the solution.
  • The essence of Competitive Programming consists in two phases:
    • Competition: the solution has just to work;
      • Top coders generally take on hand snippets and functions to use during contests.
    • Practice: deeply understanding compromises, variations and different implementations of the solution;
      • Top coders generally refine their snippets and functions.
  • A challenge may have simplifications and shortcuts:
    • The more we use those, the less generic our solution will be;
    • Hopefully, the more we use those, the more optimized (and/or simple) our solution will be;
    • Many challenges require us to find shortcuts in the problem constraints and description.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s