11,571 reads

JavaScript for Algorithmic Competitive Programming

by Mikhail RomanovMarch 24th, 2018

Too Long; Didn't Read

Last year I spent some time participating in competitive programming contests where you have to solve algorithmic problems in a limited amount of time. Still I’m somewhere in the very beginning, it was already fun and gave me some benefits.

Companies Mentioned

featured image - JavaScript for Algorithmic Competitive Programming

I’ll split my story into three parts:

Motivation
JavaScript features
Some observations and advices for beginners

Motivation

I often hear that good knowledge of algorithms and data structures as well as success in competitive programming don’t really help in real work.

They help a lot and that is why.

You learn your language on the way. I learnt a lot of stuff about JavaScript which could hit me later somewhere on production because those issues are relatively rare so I’d barely think about them in advance (say big numbers).

You solve interesting problems. Yup, some natural questions like what is the optimal way to do some tasks and spend minimum amount of time for it.

The knowledge you gain is fundamental. If you are a frontend like me and feel tired about how often you have to throw away something you learnt just yesterday, this can be saving harbor for you — this is something you learn for years. I would even say for hundreds of years if not quantum computers hehe.

Programming muscles —half a year ago it was often a case when I understood the solution but had hard time putting it into the code. Now it is often vice versa — coding algorithm once I understand it is like speaking in a native language which for sure increases my productivity at work.

And that leads to another important skill — learning how to break things into smaller chunks so that you don’t keep the whole picture in your brain any given moment. This comes from some algorithm designs like divide & conquer or dynamic programming and followed by understanding how to prepare data from one step of algorithm to another so that you keep yourself in low time complexity but still have data in a format convenient to process.

JavaScript features

I chose JavaScript because I knew this language better than others.

Though comparing to C, Python and Java, it is not quite popular language for competitive programming, and I can guess some historical reasons for that but after trying it myself I think I might see some non-historical as well (but I’m still in love with JS).

Big Numbers

The maximum integer allowed in Javascript is quite big at first glance:

Number.MAX_SAFE_INTEGER === 9007199254740991

Until you bumped into a problem where maximum allowed input is already bigger than that(Google Code Jam 2017 and Google Code Jam 2016 and etc.).

Or sometimes issue can be even hidden — when you do multiplication of billions or when you use numbers for ids at your production and at one point all ids bigger than MAX_SAFE_INTEGER will be considered by Javascript as equal:

Number.MAX_SAFE_INTEGER + 1 === Number.MAX_SAFE_INTEGER + 2 // true

There are some libraries for handling big numbers and also initiative by Chrome team so we’re looking forward for a brighter future but who knows how soon it will come. For now we have to deal with it.

Floating Numbers

The statement below is pretty well known and you can see it often in articles all over the community:

0.1 + 0.2 === 0.3 // false

This is not specific to JavaScript and there are quite good explanations of this phenomenon. However I’d never thought it would hit me one day until I tried to solve Google Code Jam 2017 Round 1A problem where I had to calculate maximum amount of portions one could make with amount of each ingredient as an input and a deviation in the required to make a portion amount as a constant.

Consider the function below I used to solve it:

function getMinMaxWrong(total, serving) {var min = Math.ceil(total / (1.1 * serving));var max = Math.floor(total / (0.9 * serving));return min > max ? [0, 0] : [min, max];}

console.log(getMinMaxWrong(2376, 3)); // [720, 879]

Seems correct but let’s rewrite it using integers:

function getMinMaxRight(total, serving) {var min = Math.ceil(total * 10 / (11 * serving));var max = Math.floor(total * 10 / (9 * serving));return min > max ? [0, 0] : [min, max];}

console.log(getMinMaxRight(2376, 3)); // [720, 880]

Mathematically those 2 formulas are same. But when you execute them in a NodeJS environment you get 2 different results and the first solution won’t pass.

Array Methods Purity

I pretty quickly get used to functional approach and immutable Array methods like map, filter, slice and reduce. I used them even when simple for-loop would be more expressive, just because I felt cool 😎.

Later it made me believe all other Array methods do shallow copies and always return new array instead of original.

I thought after the code below was executed I still worked with unsorted arr:

arrSorted = arr.sort((a, b) => a — b)

But I was wrong because sort and reverse change the Array object in place.

Make sure you know which methods exactly mutates your array and which of them not.

Another reason to be careful with this is when you use a recursion you can easily bloat space complexity with shallow copies inside each recursive function call.

Maximum Call Stack

Another point about recursion is maximum call stack size.

I think every JavaScript developer at least once in a life saw this message as a result of infinite while or for loop execution:

Maximum call stack size exceeded.

The problem is — it is not only about infinite loops. It prevents you to make recursion with big number of iterations as well.

If you ever implemented Depth First Search tree traversal then it is high probability you did it like this:

1 procedure DFS(G,v):2 label v as discovered3 for all edges from v to w in G.adjacentEdges(v) do4 if vertex w is not labeled as discovered then5 recursively call DFS(G,w)

So did I solving a problem on Codeforces. And the very same solution working for C++ didn’t work in Node because on one of the tests maximum call stack size was indeed exceeded.

There is a nice walk around by using non recursive depth first search which has some limitations but worked well in that specific problem. Same issue and walk around are applicable to Flood Fill algorithm and I believe a bunch of others as well.

If you still want to go with recursive solution and know input limitations(which is often the case) you can calculate the maximum call stack of your JavaScript engine by executing the following snippet taken from Dr. Axel Rauschmayer blog post:

function computeMaxCallStackSize() {try {return 1 + computeMaxCallStackSize();} catch (e) {// Call stack overflowreturn 1;}}

And see if the number of recursion iterations in worst case doesn’t exceed this number.

Array methods complexity

The very same problem on Codeforces made me learn another thing about JavaScript Array methods: even if they seem to do the same thing they have different time complexity.

Let’s take push/pop vs shift/unshift methods on array with O(N) length.

First two methods have O(1) complexity because they

read array length property — O(1)
add one more property to array object — O(1)
update array length property — O(1)

end.

Other two methods have to not only update array length but also to update the values of all its O(N) properties because their values are shifted either forward or backward, which gives O(N) complexity for almost the same operation you could do with O(1).

Strings Are Immutable

One small thing I always forget and which is not JS specific is you can update an Array with:

arr = ['n', 'o']arr[0] = 'y'print(arr.join('')) // 'yo'

but you cannot mutate string like this:

str = 'no'str[0] = 'y'print(str)) // 'no'

Because of that I often use trick to convert string to Array, process it and then convert back to string:

// str -> arrarr = str.split('')

// arr -> strstr = arr.join('')

This is not optimal from space complexity point of view but in many cases makes code more readable and easier to implement.

JS or not JS

Contest engines often restrict NodeJS version to some old one, for example Google Code Jam supports v4.8.2 which means you cannot use classes, let/const or destructuring there which sometimes split the mind in the process of trying to figure out are you in a competition right now or a web project at work.

Big numbers issues clearly prevents solving certain problems in JavaScript and maximum call stack issue also brings some inconvenience.

I was happy to use JS through qualification problems especially the way of working with arrays but for further steps I’d probably go with Python. It doesn’t have some of the limitations, it is extensively used in Machine Learning and it is one of only two languages along with Java allowed for famous Google foobar challenge 🙃.

How to prepare for Qualification Rounds

If you’d like to make your hands dirty and prepare for future competitions whatever language you want to strengthen I recommend to go through previous years’ problems and get some experience together with a confidence which is really needed when you cannot peep into the solution.

Small vs Large Dataset

Usually in Code Jam you are provided with Small and Large datasets. While Large dataset solution almost always shall respect time complexity restrictions, Small dataset can be often solved with brute force.

This gives you benefits that:

you can observe a pattern in Small dataset results and get some insight for the optimized algorithm especially when it is a Math problem
you can validate your Large dataset solution on the Small dataset results obtained from brute force solution
sometimes brute force works even for Large datasets(just pay attention on input limitations and your algorithm complexity)

Math

There are a lot of Math questions considering binary representations, divisibility by different numbers, prime numbers, etc. I guess this is hard to prepare so I personally just rely on my experience in Math competitions I used to participate back in school and add up some knowledge while solving previous years contest exercises.

Probability Theory

Surprisingly probability problems occur pretty often.

From my observations it is normally enough to know that if you for example have p_1_, p_2_,.., p_n_ probabilities of different events happening then probability of:

at least one event happening is: p_1 +_ p_2 + ... + p_n
at least one event not happening is: (1 — p_1) +_ (1 — p_2) +_ … + (1 — p_n)_
all events happening is: p_1 *_ p_2 *… * p_n
none of events happening is: (1 — p_1) *_ (1 — p_2) *_ … * (1 — p_n)_

Example: Round 1C 2017

Bitwise Operations

The whole programming world is based on binary nature of signals so for sure there are problems requiring knowledge of bitwise operations.

Example: Qualification Round 2011

Greedy, Hashing, DP

Mostly all algorithmic tasks from qualifications rounds can be solved with Greedy approach, Hashing or Dynamic Programming or their combination. It just requires some practice to build the intuition on where to use each of them.