May 6, 2017
Plan to work on the algorithm:
Max Score in next 1 - 2 hours. Time is 5/6/2017, 12:53 pm.
Follow up
May 7, 2017 9:20am
C# code in the contest is
here, scored 3.5 out of 35.
Follow up
Study the discussion about the solution, the link is
here.
1. The following implementation uses memoization, backtracking, and backward processing:
C# practice code is
here which passes all test cases.
2. Continue to work on my code submission, change the key of memoization, relax to the sum instead of the string concatenated by various array's element.
Score 14 out of 30, timeout test cases 7 - 10.
C# practice code is
here.
3. Bit mask - pass all test cases
C# practice code is
here.
Bit manipulation 4 things to review
1. Get integer 2
i:
//use left shift i times,
bitToCheck = 1 << i
2. Check ith bit is 1:
// int bitmask
bitmask & bitToCheck
3. Get ith bit:
bitmask |= bitToCheck,
4. Unmask the ith bit:
// backtracking
bitmask &= ~bitToCheck
4. Bit mask - replace the integer using int[], size of array is 20.
May 11, 2017
Timeout on test cases from 6 to 10. Score 10.50 out of 30.
C# practice code is
here.
string.Join(",", bitmask) takes too much time.
Julia learned the lesson. Take some time to write bit manipulation instead of using int[]. Bit manipulation expedites the process, use int instead of int[].
5. Continued to work on code written in the contest,
May 12, 2017 11:11 pm
C# practice code is
here. Score 10.50, pass test case 0 - 5, and timeout on test case 6 - 10.
Learn when to do memorization, it should be out-of-for-loop, memo on the used HashSet<int>, actually encode all used indexes of the array to a string. Move the memoization from inside for-loop to outside for-loop.
Algorithm analysis
It is most important to come out the recurrence formula for the algorithm. Try to work backwards instead of starting from the first number and forward.
The maximum score of
k problem can be solved by choosing any number as the last
kth number, and then work on the maximum score of
k - 1 problem. Use bitmask as key to do memoization.
Actionable Items
Review previous practice, and find some cases to use bitmask.
Top coder - fun with bits, the article link is
here.
Take some notes:
Use bits of an integer to represent a set. Not only does it produce an order-of-magnitude improvement in both speed and size, it can often simplify code at the same time.
Go over the most popular set manipulations in the following:
Set union
A | B
Set intersection
A & B
Set subtraction
A & ~B
Set negation
ALL_BITS ^ A
Set bit
A |= 1 << bit
Clear bit
A &= ~(1 << bit)
Test bit
(A & 1 << bit) != 0
Extracting every last bit
Counting out the bits
2. Hackerearth.com dynamic programming and bit masking, article link is
here.
