Things ‘began’ in December 2013 when I attended the Malaysian Computing Olympiad training camp, whereby I learned about how dumb the computer system is, why we should tell everything to our beloved device, what are the rules on declaring or doing iterations. Looks simple, but the progress up to December 2015 was minimal at the very best (or rather, negligible).
That’s when I picked up my books again, trying to understand data types, if…else selection, and try ‘if/else’ selection in order to write at least some baby code like asking for grades in A-Level by inputting your uniform score (e.g. scoring 90 will earn you an A*). As I progressed into learning arrays and loops, senses of inadequacy wafted into my mind and I kept questioning if I had been slow.
Little did I understand that in competitive programming, ideas and knowledge have to come hand in hand until I explored into actual competitions, ranging from the easiest junior category of Canadian Computing Competition (CCC) to some mind-blowing Malaysian Computing Olympiad (MCO) 2016 qualifier rounds. Coincidentally, all the selection rounds to the MCO were presented on Hackerrank, which attracted me to have a try on them and subsequently, involving myself in hacking techniques like graph theory and dynamic programming (all thanks to its baiting of badges to me, which required me to solve at least a question under these sections).
Hackerrank is right: the application of these two topics are very widespread (in the context of what I’ve done now).
As if time doesn’t exist for graphs and debugs
That’s the day when I learned graph theory (in late March), which took me a day or two to understand what is breadth-first search (connecting all edges as fast as possible) and its applications. As practice, I started off with snake and ladder game, where the goal was to locate the minimum number of turns needed to travel from 1 to 100 (warning on greedy approach: you won’t get the right answer!) Simple application of graph theory, but it took me 6 submissions before passing all test cases and realizing that my whole afternoon was gone.
Extending the idea to simple Dijkstra tormented my mind yet another round, and till now I could only claim that I got 30% out of it. Basically, programmers employ this idea to conquer the following real-life problem:
Several houses are in a town, and some of the houses are connected by roads. Given the pairs of houses connected by roads and length of roads, and given starting point. Find:
1. Whether it is possible to reach each of the houses by roads.
2. If yes to the previous question for some houses, what is the minimum length of travel to each of them?
Here I went, bearing in mind that this problem is ‘harder’ with 3000 towns (compared to 1000 previously). My algorithm as follows:
1. create an two-dimensional array such that the i-th column and j-th row is the length of road if the road exists, and zero if no road exists.
2. using the data above, keep updating the shortest path available at each step (e.g. Town B is recorded 5, and the road between Town A and Town B has length 1, then record Town A as 6 unless it already has a value lower than 6).
For some weird reasons my first few submissions returned zero, probably because of conflicts in naming variables. There I changed one of the variables from ‘i’ to ‘c’ before getting “all passed except one”, no thanks to segmentation fault.
From problem solving to fault finding
I then inspected several possible fault lines by consulting Google. Accessing ranges of arrays that don’t even exist? It couldn’t be: adding some spare spaces (e.g. allocating n+100 spaces instead of just n spaces) would end me up scoring 42.35/60 again. I gave up and escaped to another problem: this time to determine whether a number is prime by creating an array and by employing prime sieve.
As I gave up and moved on to determining whether a number is prime, a discovery bemused me: testing for numbers beyond 8 million will cause segmentation fault as well! Then Zi Song came to my computer and said “it must be memory limitations.”
I tried fixing it by reducing the memory needed for each element in the array by changing ‘int’ to ‘short’ (since I know too well that the array elements cannot exceed 350). As I submitted my edits, I starred at the feedback from several testcases, relieved as the code passed some test cases but couldn’t be satisfied until the grading system performed its last run. ‘Yay!’ I exclaimed as the scoreboard recorded 60/60.
—
To summarize, it was an accomplishment to be able to solve these problems, but there will be more to come later!
anzoteh96 