Mathematics and hackerrank week code contest

April 18, 2017

Introduction

It is interesting to know that the advanced algorithm in hackerrank week code contest sometimes is purely a mathematical analysis problem. The score of the algorithm is 100. Julia likes to be able to solve one of them in the short future.

Today Julia likes to study if Euler algorithm on Hackerrank is good choice to practice. Mathematics is a golden mine, if Julia starts to work on the math again, she may find herself to be able to score extra 100 points on hackerrank week code contest.

Based on the experience to work on algorithm "Colliding Circles" in week code 31 contest, Julia learned and practiced one more time how to write clean and efficient DFS algorithm using recursive function. Those 5 hours she experienced a lot to construct a DFS - recursive function.

It was very exciting to make a small change in the two submission, solved test case 4, scored extra 3 points from 8 to 11. Julia learned to be extremely patient to learn to write best recursive code. The experience is documented in this blog.

Here is the short story of reducing time complexity of calculation O(n²) to O(n). There are n balls, any two can collide, so there are total n x (n-1) options; each collide the area gets increment of 2 x r_i x r_j, sum (2 x r_ix r_j) is O(n x n) time complexity. Since n is 10⁵, so n x n will be 10000 million; time complexity will be lowered from 10000 million of multiplcation to 100000 calculation of summation. As showing in the following code snippet, the difference of two summations is the 3 hours work/ 3 more points, (r₁ + r₂ +...+ r_n)² - (r₁² + r₂² + ... + r_n²).



More detail please refer to the colliding circles source code line 82 - 87 for extra 3 points. However, using mathematical analysis, the algorithm can be designed with time complexity lower to O(n). It was hard to get it in the contest.

One player did a lot of Euler algorithm heavily recently, the player got mathematics' Ph.D. degree from 1996 to 2000. Julia was wondering if she can learn something from other player's practice.

Algorithms 

Those Euler algorithms on hackerrank may be a good place to practice good mathematical problem solving.

Here is the leaderboard Julia tried to study next 30 minutes - 10:06pm - 10:36pm. Who are those talents? What are the motivations to have those talent group? Name 3 of them and try to find motivation behind.

Top player Yuehang Chen - profile is here.
Yuan Li, profile is here.

Take a course - mathematical thinking on coursera by stanford university professor -  keith devlin, or read a book called mathematical thinking.

Cracking the coding interview on hackerrank

I have fought the good fight

Show the first silver medal. And also, read the article about Timothy 4:7 (ESV) “I have fought the good fight, I have finished the race, I have kept the faith.”