Introduction
Julia changed the practice to attend the contest, she chose to take some risk; aim most difficult algorithm, last of 6 algorithm - Hard level. Total score is 100, she knew about Fibonacci algorithm very well, dynamic programming, memorization, bottom up; she also spent over 2 hours to read the problem statement, try to work on the mathematics part of the algorithm.
Until 4:00am, she gave up. She thought about last hour, if she can make this algorithm work, then, she can score 120, rank will be 120/ 2600; She could get into top 10%.
Problem Statement
Summary of practices
Worked on the algorithm from 11:am - 4:00am, near 15 hours, score 0 out of 100.
Submission 17 times. First work on memory issue, remove out-of-memory issue; and then, worked on timeout issue, could not get rid of range sum query O(n2) issue, n is O(n5).
1. First submission:
Fibonacci sum - first submission - line 183 - line 196 function fibo - array declaration on line 187 - 109 * 4 bytes = 4000MB.
If there is no memory limit, timeout issue, the algorithm will work. Cannot scale, timeout 2 issues.
2. 8th submission, out-of-memory, should be less than 512MB; but it is over 4GB for an array
3. 9th submission
4. 10th submission
5. 17th submission
Until last hour of 15 hours, Julia read discussion. "Segment Tree" may be the idea to avoid O(n2), range sum query classical problem.
Encouraging notes for Julia
Julia likes to celebrate her 15 hour effort to work on a hard algorithm problem on HackerRank; focus on the hard algorithm, therefore, she can figure out later what she should put her training next.
Instead of working on medium/ advanced level algorithm, Julia likes to solve first hard algorithm first. This is the first time she did in 24 hours contest, push herself to the limit, try to solve one hard algorithm. She does not have time to read 3 medium algorithms problem statement in the codesprint.
3 kinds of people, do not know what is happening, one is to make thing happen. Julia chose the last one. One day, She can solve hard problem on HackerRank contest. Make things happen. Fail fast, fail quick. Just do it.
Previous blogs about Fibonacci algorithm
I solved the algorithm called climbing stairs
Julia, remember the phrase: The hard makes it great! Enjoy the journey.
It's the spirit that makes every #player outstanding.#TennisQuotes #Motivational pic.twitter.com/CvI2pqeSdF— Tennis Coaching™️ (@tennisdothow) September 21, 2016
No comments:
Post a Comment