Introduction
It is a good idea to continue to work on maximum score algorithm, and also ask a question on code review. Learning memoization and bit mask is not an easy task, also Julia likes to learn the time complexity analysis algorithm better through the study.
Julia wrote a blog to document her learning experience on the algorithm, from the contest performance to after-contest catching up.
Code review preparation
C# code in the contest is here. Score 3.5 of 35 points.
May 12, 2017 11:16 pm
Code review of C# code in the contest, and then move the memoization out-of-for-loop, scored 10.50 of 35 points. C# code is here.
Instead of going over the recurrence formula, Julia likes to use an example to explain what can be in memoization. And what is her mistake in the contest? What is the reason causing the false analysis?
Suppose that the array has two numbers, int[] numbers = new int[]{1, 2}. The problem is to find the maximum sum such that the order of two numbers to put into scoring make the value maximum.
What is the subproblem of max score?
First, add sum of the array. The array new int[]{1, 2}'s sum is 3.
To choose the last number, two options, either 1 or 2. If the last number is 1, array's index is 0, then the 0th score is (3 - 1) % 1 = 0. Next number is 2, sum is 0, and then the 1th score is 0 % 2 = 0. The sum of score values (0th, 1th) is 0.
In other case, if the last number is 2, array's index is 1, then the score is (3 - 2) % 2 = 1. Next number is 1, sum is 0, and then 0 % 1 = 0. The sum of score values is 1.
From the above two cases, the maximum score is 1 by taking 2 as last number and then taking 1 as the first number. Just remind friendly that the order is opposite from end to start.
The maximum value is to choose maximum value from a set with two values.
The memoization process is to record to Dictionary<string, int> calculated.
["0", 1]
["1", 0]
["", 1]
Calculated variable as Dictionary<string, int> has the following:
[0 1, 0]
[0 2, 0]
[0, 1]
[1 2, 0]
[1, 0]
[2, 1]
[,1]
Debug the code, and check how many times the dictionary is looked up. 3 times.
key = "0 1", "0 2", "1 2".
Draw a recursion tree for this simple test case. Here is the graph:
Argument: If you can work on this simple test case and also work out the recursion tree correctly, then I believe that you can solve the problem using memoization and recursive, DP solution correctly as well.
Do not memo one more item in one recursive call; Stay outside the for loop; Memo before return statement.
Julia, if you are very good at unit testing, and work on simple and very good test case in the design of algorithm, your performance on Hackerrank can improve at least 20%.
It is the first challenge Julia worked on since last January on hackerrank, on the topic of bit mask, dp, memoization, subset. So she likes to make the algorithm everything. Learn one algorithm a time. Do not rush.
Julia likes to review a list of things on the algorithm. Bit mask, memoization, time complexity analysis.
Use bit mask, the code passes all test cases.
C# practice code is here.
Memoization Analysis Challenge
Instead of going over the recurrence formula, Julia likes to use an example to explain what can be in memoization. And what is her mistake in the contest? What is the reason causing the false analysis?
Suppose that the array has two numbers, int[] numbers = new int[]{1, 2}. The problem is to find the maximum sum such that the order of two numbers to put into scoring make the value maximum.
What is the subproblem of max score?
Guess what is the subproblem
May 13, 2017 11:03pm
First, add sum of the array. The array new int[]{1, 2}'s sum is 3.
In other case, if the last number is 2, array's index is 1, then the score is (3 - 2) % 2 = 1. Next number is 1, sum is 0, and then 0 % 1 = 0. The sum of score values is 1.
From the above two cases, the maximum score is 1 by taking 2 as last number and then taking 1 as the first number. Just remind friendly that the order is opposite from end to start.
The maximum value is to choose maximum value from a set with two values.
The memoization process is to record to Dictionary<string, int> calculated.
["0", 1]
["1", 0]
["", 1]
One more test case
Suppose that the array has two numbers, int[] numbers = new int[]{1, 2, 1}.
[0 1, 0]
[0 2, 0]
[0, 1]
[1 2, 0]
[1, 0]
[2, 1]
[,1]
Debug the code, and check how many times the dictionary is looked up. 3 times.
key = "0 1", "0 2", "1 2".
Draw a recursion tree for this simple test case. Here is the graph:
Common advice
Do not memo one more item in one recursive call; Stay outside the for loop; Memo before return statement.
Julia, if you are very good at unit testing, and work on simple and very good test case in the design of algorithm, your performance on Hackerrank can improve at least 20%.
Make it all
It is the first challenge Julia worked on since last January on hackerrank, on the topic of bit mask, dp, memoization, subset. So she likes to make the algorithm everything. Learn one algorithm a time. Do not rush.
Julia likes to review a list of things on the algorithm. Bit mask, memoization, time complexity analysis.
Use bit mask, the code passes all test cases.
C# practice code is here.
Hackerrank Editorial Notes
In order to write a good question on code review, Julia also have to write down some notes from editorial notes from hackerrank on the maximum score algorithm.
Here is the link of editorial notes.
Julia's note:
time complexity: O(2n * n)
Recursion tree - a major flaw, same recursive call many times; It results in exponential running time.
Actionable Items
Read book "Testable JavaScript" and then figure out a few things I can do in order to have a good sense of setting up test cases to help Hackerrank contest.
The algorithm is also on code review.stackexchange.com, the link is here.
No comments:
Post a Comment