Hackerrank week code 28 - Choosing White Balls

January 14, 2017

Choose white balls - problem statement

Introduction
What is the feeling about sitting on the bench while the match is going on? That is something Julia went through in the contest. She tried to do some reach, make 10 - 15 points if possible. One of practice here is to study player's discussion board, and see how top-players are doing when they need to communicate and have some discussion. It is not bad at all to see all over the world, people came together and exchange ideas for the same algorithm.

In the contest 

Hard algorithm, maximum score 54 

Study the khan summation algorithm - read discussion and found some one gave out this tip.

The discussion here is very helpful, at least it is helpful to understand the problem. Work on the example first.

Julia spent 10 minutes to work on the example here:

WBWBW

Analysis with a fault: 

The analysis with some issues:

step 1: 1, 3, 5 are white and 2, 4 black -> 3/5

step 2: 3 possible new sequence

BWBW -> 1 WBWB -> 1 WBBW -> 2/4 -> 1/3 * (1 + 1 + 2/4) = 5/6

total = 3/5 + 5/6 = 1.4333333

Analysis with corrections:

You do not choose xi, they are chosen randomly. You only choose either left or right for given xi. Therefore in step 1, if xi was 2 or 4, you end up with sequences WWBW or WBWW in step 2, you need to count these in your expectation. 

Then you get 3/5 + 1/5 ( 1 + 1 + 2/4 + 1 + 1) = 1.5

Hours of reading - Discussion

BWBWW

Set up a test case for BWBWW - the answer should be
Discussion is here.

BWBBBW

January 14, 2017

Choose white balls - problem statement

Study the khan summation algorithm - read discussion and found some one gave out this tip.

The discussion here is very helpful, at least it is helpful to understand the problem. Work on the example first.

Julia spent 10 minutes to work on the example here:

WBWBW

Analysis with a fault: 

The analysis with some issues:

step 1: 1, 3, 5 are white and 2, 4 black -> 3/5

step 2: 3 possible new sequence

BWBW -> 1 WBWB -> 1 WBBW -> 2/4 -> 1/3 * (1 + 1 + 2/4) = 5/6

total = 3/5 + 5/6 = 1.4333333

Analysis with corrections:

You do not choose xi, they are chosen randomly. You only choose either left or right for given xi. Therefore in step 1, if xi was 2 or 4, you end up with sequences WWBW or WBWW in step 2, you need to count these in your expectation. 

Then you get 3/5 + 1/5 ( 1 + 1 + 2/4 + 1 + 1) = 1.5

Hours of reading - Discussion

BWBWW

Set up a test case for BWBWW - the answer should be
Discussion is here.

BWBBBW

Discussion is here. 

Summary of Contest Activities

In the contest, spent hours to read the problem statement, discussion, did some research. No code, did not make any points.