Oct. 30, 2016
Work on segment tree idea to solve timeout issue. After the contest, Julia has more time to relax, and try different ideas to solve this hard algorithm on HackerRank.
Previous blog
Will come back to write C# code to try segment tree idea.
Read editorial notes.
Ashar Faudi - study a player - Topcoder SRM problem writer
Need to spend time to figure out this linear recurrence for programming contest .
https://www.linkedin.com/in/fushar
Study C# submissions:
1. C# submission
2. C# submission
Think about the strategies of HackerRank contests - should work on medium algorithm instead of hard one. Math part is not easy to figure out in less than 24 hours.
Spent 2+ hours to go over the submissions on this hard algorithm, get the data - who are those talents? What they are sharing? A special group with strong math or research abilities?
1. Competitive programmer talking about achievements.
2. People good at math - problem solving on the algorithm - a few of them are competitive programmers.
3. programming contest
4. Math Ph.D. graduate (better programmer compared to Julia)
https://www.hackerrank.com/hoek3000
5. Figure out something new in computer science master graduate study:
Showing posts with label interesting Fibonacci Sum. Show all posts
Showing posts with label interesting Fibonacci Sum. Show all posts
Sunday, October 30, 2016
HackerRank - WarmartLabs Codesprint (Algorithms) - Interesting Fibonacci Sum
Oct. 30, 2016
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
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.
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.
I solved the algorithm called climbing stairs
Julia, remember the phrase: The hard makes it great! Enjoy the journey.
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
Subscribe to:
Posts (Atom)