Array Construction - Code Review

Dec. 11, 2016

Introduction

Array construction is the first advanced algorithm Julia tried to work on in the contest, she did try to work on over 10 hours, but she scored 0 (maximum score 80). Through the contest, she started to understand the algorithm and built up strong interest in problem solving.

Later, she read one of solution, and then, spent over 4 hours to understand the pruning idea to avoid timeout issue.

Later, she did very intensive research on recursive function. But, she needs to get it on stackexchange.com, share her interest and questions, and then, see if she will get any surprise. Success after team work, Julia likes to practice the belief.

Previous blogs about the algorithm:
Labels: Array Construction (Series 1 of 5)

http://juliachencoding.blogspot.ca/2016/11/hackerrank-codesprint-array.html

Workout:

Plan to post a question on stackoverflow.com code review for code review.

HackerRank - university codesprint - array construction - testing and playing after the contest (series 3 of 5)

Nov. 18, 2016

Julia spent another 3+ hours to work on the array construction code study after she understood the algorithm design.  The blog:

http://juliachencoding.blogspot.ca/2016/11/hackerrank-codesprint-array.html

Here is the C# solution she did some research:

1. perfect solution with full score 80
https://gist.github.com/jianminchen/096ebc5bc1769b83b38ec6eeaabbc7c5

And then, she wrote some debug information on the code:

debug code:

C# code with debug info (stage II):

https://gist.github.com/jianminchen/f258bab2e8047ada3da94202f1cb8adb

So, she tried to figure out if she can apply the same idea to her code in the contest, but she still had timeout issues. And then, she noticed that line 36 of solution: 
https://gist.github.com/jianminchen/096ebc5bc1769b83b38ec6eeaabbc7c5

--
line 6:
static bool[, ,] w;

line 21:
w = new bool[n, s + 1, k + 1];

line 36:
if (w[p, sum, diffsum]) return -1; else w[p, sum, diffsum] = true;
--

- quick calculation to verify the space limit - 
n<= 50,
s<=200
k<=2000,
so, bool[,,]w size is less than 20 MB.
HackerRank contest space limit is 512MB. It is ok to declare the w[,,] 3 dimension array to avoid timeout!
-- the end of space limit calculation --


She tried to play with line 36, comment out the line 36, run HackerRank test cases, and then, she found out that test case 4 timeout.

Testing and new findings:

1. first, she commented out the code on line 36:
https://gist.github.com/jianminchen/096ebc5bc1769b83b38ec6eeaabbc7c5

and then, HackerRank complained test case 4 timeout.
So, this pruning is important to avoid timeout.

So, she open the test case 4 input:

20 50 200 1860 ...

Julia chose first test case by mistake: 50, 20, 1860 instead of 50, 200, 1860, trace file is 193 page long in the word document. Fact: 50, 200, 1860, out-of-memory, trace file is too big Julia ran the debug code to get trace: debug code: C# code with debug info (stage II): https://gist.github.com/jianminchen/f258bab2e8047ada3da94202f1cb8adb And then, here is the trace information -

TraceFile No 1:
https://gist.github.com/jianminchen/2d3622a096c51b0afe81fd60ca9865ef

Open the trace file(TraceFile No 1) using github,

Search the word: w[49,6,282],
Find first, line 4661,
w[p, sum, diffsum] is not true w[49,6,282]

Read content from line 4658 - 4661:

line 4658:
E: Array A is [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,3,3,9]

line 4659:
F: recursive call construct - arguments: (A,6,282,49)

We know that before the small sequence is found, then, w[49,6,282] is called again. We knew that
the first call W[49,6,282] is calculated and did not lead to a solution. So the second time, we
stopped right away.

Search again on w[49,6,282]
See the line 6722:
E: Array A is [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,1,1,4,15]

see the line 6723:
F: recursive call construct - arguments: (A,6,282,49)

see the line 6725:
w[p, sum, diffsum] is true - w[49,6,282] - return -1

In other words, [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,3,3]
(A, 6, 282, 49) is the first time to invoke W[49,6,282], and then, continue to run the code,
did not find the optimal solution.
So the second time, [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,1,1,4]
(A, 6, 282, 49)
w[p, sum, diffsum] is true, return -1.


Julia's notes:

HackerRank advanced algorithm "Array Construction" is really a challenging one. But Julia likes to
have some fun with the algorithm, and then, she just played the algorithm, C# study code, and then,
her own code. Try to find something interesting.

HackerRank - University CodeSprint - Array Construction - In contest performance (series 1 of 5)

Nov. 13, 2016

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