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):
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):
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.
No comments:
Post a Comment