Max Score - RookieRank 3

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ⁱ:
//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.