Contest: HackerRank (1) Ad Infinitum 13 and (2) CodeStorm 2015

I haven’t blogged in a few weeks, and I wanted to report out on my recent programming adventures. I competed in a couple of contests recently on HackerRank.

The first was a Math Programming contest, where I placed 111 out of 1220 participants. This was my first time participating in a Math Programming event, and the problems were definitely way more mathematical (than algorithmic). The first 5 problems were a lot of fun, requiring knowledge of Pick’s theorem, invariants, and some clever math to compute a large GP sum in modulo arithmetic (efficiently). The last 2-3 problems were very cryptic, and relied on knowledge of the Mebius function, representation theory, and Stirling numbers of the second kind (I don’t even know what Stirling numbers of the first kind are, LOL!). I coded some un-optimal solutions to these last ones, which cleared some but not all test cases. Overall I had fun, but not as much as I do on the algorithmic contests. This is definitely due to my lack of knowledge of the hardcore math involved. It was an interesting experience though.

The second contest, CodeStorm 2015, was definitely my type of contest. It was more of a CS centric contest, and efficient solutions required algorithmic (rather than pure math) understanding. I placed 151 out of 4850 participants, which was a pretty good placement.

Here is a breakdown of the problems:

#	Problem	My Solution	Algorithmic Technique	Time Complexity	Space Complexity	Level
1	Emma’s Notebook	GitHub	Basics	O(t)	O(1)	Easy
2	Save Quantumland	GitHub	Greedy	O(n)	O(n)	Easy
3	Counting Triangles	GitHub	Binary Search	O(n^2 log n)	O(n)	Moderate
4	Boomerang	GitHub	Reverse Engineering 😉	O(T log n)	O(1)	Moderate
5	Game of Reduction	GitHub	Precomputation, DP for nCk, Game Theory	O(nmax) O(nmax^2) O(m + n) per test case	O(nmax^2)	Difficult
6	Independent Vertex Cover	Not Attempted	N/A	N/A	N/A	Difficult
7	Alexey’s Tree	GitHub	Memoization Graph Theory	O(n+m)	O(mn)? Not sure. Lots!?	Advanced

 

I solved the first 4 problems perfectly. Problem #5 cleared 4/14 test cases, the rest ran out of space. Problem #6 cleared 48/59 test cases, the rest again running out of memory. Of course, neither of these was the optimal solution. I didn’t have time to attempt #6 at all, though it looks like a fascinating problem.