Code review: Lucky number 8

March 5, 2016

Problem statement

Introduction

Julia had a few submissions in the contest, she tried 12 submissions. Scores is an interesting array like this, [0, 2, 1.8, 3.6, 10.8]. The final version in the contest, a C# practice in the contest, scored 10.8 out of maximum score 19.80 30.

Lucky number 8 is the medium level algorithm in the week of code #28, Julia took the recursive function as an approach, in order to score more points, she wrote more than 450 lines of code.

Julia did not have too many choices in the contest, the dynamic programming approach is too difficult for her to figure out. Actually she was math major graduate, and then she just enjoyed the workout on this analysis. She was writing a "book" (a joke to verbose coding), actually computer science on hackerrank contest taught her a lesson - to be thrift on time to write code, if she can be ...

Julia spent some time to review hackerrank contest performance  and then looked into the issues of week of code #28, she took a look at the algorithm submissions, she was so surprised, my God, it is such a great workout on recursive function. This is like sports - but it is a time-consuming marathon. This is her first time to write a recursive function and spent more than a few hours, and experienced a little success. Cheers! Julia, good job, even it is 10.8, 30% of maximum score 30. Julia likes to call this algorithm with this submission with a beautiful name by Vancouver islands: Tufino, a vacation place she should take instead of going back to China, a popular summer place to visit whales from touring boats.

Today, Julia likes to show herself how to score maximum score. Learn a dynamic programming after she learned the lesson through the contest.

The most important is to work on the example 968 and figure out how to solve the problem to get the answer 3.

Lesson learned

450 lines of code using recursive function cannot beat 20 50 lines of code using dynamic programming. But Julia also learned the lesson through practice, not at work. That is the importance of practice!

Facts:

In order to score more points in the contest, Julia continuously wrote more code until 450 lines. She had determination to make more points, she showed her passion to solve the problem.

Actionable Items

1. Read editorial notes:

In this problem, you are given a sequence of digits of length . You have to find the number of non-contiguous subsequences, such that the number formed by their concatenation is divisible by .

Observe a bit,

The number is formed by concatenating the non-contiguous subsequences, which implies that the number itself is a subsequence and vice-versa.

So the problem boils down to counting the ways you can make a subsequence divisible by . This can be done by Dynamic Programming.

At any position of the sequence, you need to consider two cases:

1. Concatenate the digit at the position with your current subsequence and move to next position.
2. Leave the digit and move to next position.

The idea can be coded with states: Current position and Remainder of the subsequence modulo 8.

2. Check all Google's employees' submission on this algorithm:
Study Java code first, write C# solution with comments.

Work on frequency table to help understanding the algorithm:

Read the above table, we can tell that numbers: 96, 8, 968 are 3 numbers to be divisible by 8, and we found the answer. Is that easy to follow this frequency table?

C# code for Code review is here. Extract a function, make other changes, this version of C# code is better for review, here.

3. Google keyword search:

states? Current position and Remainder of the subsequence module 8

4. Dynamic programming vs recursive function - check stackoverflow.com

Code review

Plan to make the code more meaningful, and then post a question on codereview.stackexchange.com.