JavaScript for Algorithmic Competitive Programming

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. 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( and and etc.). Google Code Jam 2017 Google Code Jam 2016 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 will be considered by Javascript as equal: MAX_SAFE_INTEGER Number.MAX_SAFE_INTEGER + 1 === Number.MAX_SAFE_INTEGER + 2 // true There are some libraries for handling big numbers and also 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. initiative by Chrome team 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 of this phenomenon. However I’d never thought it would hit me one day until I tried to solve 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. good explanations Google Code Jam 2017 Round 1A Consider the function below I used to solve it: function getMinMaxWrong(total, serving) {var min = Math.ceil(total * serving));var max = Math.floor(total * serving));return min > max ? [0, 0] : [min, max];} / (1.1 / (0.9 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 * serving));var max = Math.floor(total * serving));return min > max ? [0, 0] : [min, max];} * 10 / (11 * 10 / (9 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 , , and . I used them even when simple for-loop would be more expressive, just because I felt cool 😎. map filter slice reduce 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 and change the Array object in place. sort reverse 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 or loop execution: while for 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 DFS( , ):2 label as discovered3 edges from to .adjacentEdges( ) 4 vertex is not labeled as discovered 5 recursively call DFS( , ) procedure G v v for all v w in G v do if w then G w So did I solving a on Codeforces. And the very same solution working for didn’t work in because on one of the tests maximum call stack size was indeed exceeded. problem C++ Node There is a nice walk around by using which has some limitations but worked well in that specific problem. Same issue and walk around are applicable to algorithm and I believe a bunch of others as well. non recursive depth first search Flood Fill 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 vs methods on array with O(N) length. push/pop shift/unshift First two methods have O(1) complexity because they read array property — O(1) length add one more property to array object — O(1) update array property — O(1) length 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 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. means 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, , 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. divisibility by different numbers 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 approach, or or their combination. It just requires some practice to build the intuition on where to use each of them. Greedy Hashing Dynamic Programming What’s Next Even though JavaScript is not popular among competitors there are awesome projects filling this gap: _javascript-algorithms - Algorithms and data structures implemented in JavaScript with explanations and links to further…_github.com trekhleb/javascript-algorithms _javascript-algorithms - JavaScript implementation of different computer science algorithms._github.com mgechev/javascript-algorithms And here is my repository with some solutions for Code Jam Qualifications rounds: _GitHub is where people build software. More than 28 million people use GitHub to discover, fork, and contribute to over…_github.com romanovma/google-codejam I wish you fun time and thank you for reading. Give me some love ❤️❤️❤️ if you liked the article please make some 👏 so my motivation for further writings is up.