Problem statement:
https://www.hackerrank.com/contests/university-codesprint/challenges/array-construction/submissions/code/7825209
Advanced algorithm, Max Score: 80
Over 6 hours to work on the algorithm.
Warm up the topic:
It felt so good to work on the algorithm.
First, Julia warmed up the backtracking algorithm using sample test case, spent more than one hour.
input:
1
3 3 4
output:
0 1 2
Here is the submission: pass the above test case, score 0.
https://gist.github.com/jianminchen/c17ce782080a99a2480ff1c6eb390628
There are a lot of issues, timeout, wrong answer. As long as the solution used the backtracking, DFS with some pruning, the timeout issue could not be avoided. Julia worked up to 3:30am, more than 10 hours, 5 hours before the end of contest. She finally gave up the effort and called it a day.
Julia felt so challenged through the problem solving, she went through backtracking, timeout issue, and then, she did some pruning, set up maximum/ minimum range for the search, through sum of array and sum of difference of any two elements. She did some research after over 10 hours, and then, find the article to reduce O(n^2) to O(n) to calculate sum of (Ai-Aj) for any i, j from 1 to n.
Highlights of great things in the contest: (need to fill out with really good things, think hard again.)
1. First, Julia did search from smallest word to biggest one.
This way, if she finds one word, the word should be the smallest one. Backtracking algorithm she did practice on phone number.
2. Julia had backtracking code experience, on Leetcode phone number.
3. Although Julia did not know DFS/backtracking could not solve the timeout issue, she knew that backtracking practice helps her to understand the problem, really understand the scalability issue. She understands the depth of the problem, and also understand the math analysis of time complexity is such important to help design.
4.
5.
6.
Highlights of things to work on:
1. Backtracking algorithm cannot beat the dynamic programming algorithm on timeout issue.
DP solution can give the math formula about time complexity analysis, and then, further pruning gives out better performance.
10 hours hard word, learn the first lesson.
2.
3.
4.
5.
6.
Last submission: score 8 of 80
Julia spent over 20 minutes to clean up the code, reduce the complexity of the code through so many efforts, hours work. Just use common sense, "The real challenge is from mathematics! What is time complexity of my algorithm? I had to depend on those pruning ideas - it worked great on my test case, up to 50 (size of array)(line 101 - 119), only take around 110 milliseconds, but it still failed on timeout issue."
https://gist.github.com/jianminchen/42300e1f09b748d5a165990f0c7f64b2
Study C# submissions:
1. perfect solution with full score 80
https://gist.github.com/jianminchen/49f45acc69b4d87c51d02c81a788fbc9
2. perfect solution with full score 80
https://gist.github.com/jianminchen/096ebc5bc1769b83b38ec6eeaabbc7c5
3. score half score 40
https://gist.github.com/jianminchen/f85de0c2b6014ff79d1097ce12705691
Constructive algorithm: (preprocessing, and then, lookup)
(HackerRank - array construction is a constructive algo.)
https://www.quora.com/What-does-the-constructive-algorithms-tag-mean-at-Codeforces
No comments:
Post a Comment