Segment Tree - kindergarten adventures algorithm - Make my mark

Dec. 14, 2016

Problem statement:
https://www.hackerrank.com/contests/university-codesprint/challenges/kindergarten-adventures

Introduction:
Kindergarten adventure algorithm is the algorithm on HackerRank university codespring contest in November, 2016, and it is medium level difficulty. Julia spent over one hour to think about the algorithm in the contest, but she did not come out the idea using binary indexed tree or segment tree to solve it. After the contest, she likes to master the algorithm.

The Previous two blogs about the algorithm and solutions:

HackerRank - university codesprint - kindergarten adventures (after the contest)

http://juliachencoding.blogspot.ca/2016/11/hackerrank-university-codesprint_16.html

Here is one C# solution she chose to study, here are her workout experience:
1. Put some analysis together,
2. Review code
3. Put together a new version
4. Share on stackexchange.com code review section.

https://gist.github.com/jianminchen/c3abd1d967c58132023b7235b69fdcdd

5. Post the question on the stackexchange.com as well.

Post the question on stackexchange.com code review:
http://codereview.stackexchange.com/questions/149613/hackerrank-university-codesprint-2016-kindergarten-adventures

6. StackExchange.come code review feedback:

put on hold as off-topic by Peilonrayz, forsvarir, BCdotWEB, Vogel612, t3chb0t 2 days ago

This question appears to be off-topic for this site. While what’s on- and off-topic is not always intuitive, you can learn more about it by reading the help center. The users who voted to close gave this specific reason:

• "Questions must involve real code that you own or maintain. Pseudocode, hypothetical code, or stub code should be replaced by a concrete implementation. Questions seeking an explanation of someone else's code are also off-topic." – Peilonrayz, forsvarir, BCdotWEB, Vogel612, t3chb0t

8. Julia knew that she has to work on one algorithm a time, and this algorithm takes time. She started her own practice, failed 3 times:

8.1. Wrote my own version of segment tree, first try: 2.18 (maximum score 30)
only pass 4 test cases.
https://gist.github.com/jianminchen/3fc3df275c903e94b780e1612f0171f6

8.2. Second practice, score 1.08 max-score: 30, pass test case 0 and 1.
https://gist.github.com/jianminchen/98f38cfb31bace070184b641c95d14b9

8.3. Third practice, score 0  max-score: 30, pass test case 0, 1
https://gist.github.com/jianminchen/1411dc08a2a2c059454f788add19bceb

It is a really good study case for understanding depth of problem solving. Timeout issue is critical, at the beginning of construction of segment tree, the time complexity should be O(n^2), not O(n), n is the people in the group, n < 100000.

Better score 0 to write your own code, comparing to copy other's code score 30. Do not underestimate your own practice, the mistakes made, time spent all counts to the good learning experience.  

8. Go back to the study code C#: 

https://gist.github.com/jianminchen/c3abd1d967c58132023b7235b69fdcdd

And google and try to find some article to help.
The solution is classical, some one already did research how to store the value in segment tree most efficient way, almost O(n) to build up a segment tree.

Find the article using similar idea: 

http://codeforces.com/blog/entry/18051?

Workout: 

1. Show some graph on analysis of solution provided:

2. Get out from the first breakdown on stackexchange.com code review: 
Have some sports therapy - 30 minutes 

Watched the video of Genie Bourchard interview twice while she did some stretch in the living room, for a sports workout. 
Eugenie Bouchard Live: 
https://www.youtube.com/watch?v=w02BSPblBEs&t=320s

(Eugenia is a young player, 20 years old when she was interviewed. She talked about in the interview Nick is her great coach, when she was 12 years, she was taught how to deal with mental issues in sports - stay at moment on the court, no matter what happens )

Do not be lazy. Work hard, fail a few times and then get better. Julia, if you are in uncomfortable zone, that is the learning zone. Do not miss the learning opportunities.

Fail to post, the algorithm written is not mine. Need to come out my own solution first, and then, get code review. Tried various solutions, failed all times. Get to know the algorithm better.

And then, Julia gave her 30 minutes therapy, chose one of top tennis players to motivate herself. Work on algorithm is not easy, to be competitive, Julia has to learn what to work on. No shortcut. Hands on experience, stay at moment. When practice, make as many mistakes as you can. If you can afford the time. 

Segment Tree - kindergarten adventures algorithm - code review

Dec. 10, 2016

Problem statement:

Introduction

Kindergarten adventure algorithm is the algorithm on HackerRank university codespring contest in November, 2016, and it is medium level difficulty. Julia spent over one hour to think about the algorithm in the contest, but she did not come out the idea using binary indexed tree or segment tree to solve it. Julia was very lucky to find a C# solution actually implemented using segment tree.

The Previous two blogs about the algorithm and solutions:

HackerRank - university codesprint - kindergarten adventures (after the contest)

Julia found out that her learning of binary indexed tree is missing most important part, the experience to play and learn from a simple concrete example; she read a lot about segment tree, or binary index tree, but she needs to have some time to play with an example, have some fun. The skills will come afterwards, she believes.

Here is one C# solution she chose to study, here are steps:
1. Put some analysis together,
2. Review code
3. Put together a new version
4. Share on stackexchange.com code review section.

C# code

Plan to work on the algorithm 2 hours. Dec. 10, 2016, 11:36am - 1:36pm

Put some references together for further study.

Workout

C# code - Julia tries to figure out how to build a segment tree through sample test
case:
3
1 0 0
The segment tree in an array: {0,0,2,2,1,1}

Segment Tree:

C# code

Julia's concerns about segment tree:

Questions:

1. Why does Modify function skip one and only add value on odd number?

Line 114 - line 125,

        public void Modify(int start, int count, int value)
        {
            int size = tree.Length / 2;
            int left = start + size;
            int right = start + count + size; // open border

            for (; left < right; left >>= 1, right >>= 1)
            {
                if (left  % 2  == 1) tree[left++]   += value;
                if (right % 2 == 1) tree[--right]  += value;
            }
        }

2. How does the range of start/ end to be determined on this simple test case: 1 0 0?

Line 87 - Line 93:
private static SegmentTree BuildTree(int n, int[] extraMinutes)
    {
        var tree = new SegmentTree(n);
        for (int i = 0; i < n; i++)
        {
            int curr = extraMinutes[i];
            int len  = extraMinutes.Length;

            if (curr >= len) continue;

            int start = (i + 1) % len;
            int end   = (i + extraMinutes.Length - curr) % len;

            if (start <= end)
                tree.Modify(start, end - start + 1, 1);
            else
            {
                tree.Modify(start, len - start, 1);
                tree.Modify(0,     end + 1,     1);
            }
        }

        return tree;
    }

Why start = (i+1) % len? Guessing,  i = 0, ID counts from 1 to 3, not starting from 0.
Why end  = (i + extraMinutes.Length - curr) % len;

3. Question:
Study Query API: Why skip the root node?
for loop, i > 0

Line 132 - Line 139:
public int Query(int index)
        {
            int res = 0;
            int i = index + tree.Length / 2;
            for (; i > 0; i >>= 1)
                res += tree[i];
            return res;
        }

Actionable Items

Julia, only way, better way to learn segment tree, binary index tree, is to work on an algorithm, and then, ask good questions to yourself, and then, post the question on the stackexchange.com as well.

Post the question on stackexchange.com code review:

Code review is here. The code review was closed.

It is not acceptable to ask help to understand other people's code. That is the rule from stackexchange.com. Do not be lazy. Work hard, fail a few times and then get better. Julia, if you are in uncomfortable zone, that is the learning zone. Do not miss the learning opportunities.

Fail to post, the algorithm written is not mine. Need to come out my own solution first, and then, get code review. Tried various solutions, failed all times. Get to know the algorithm better.

1. Wrote my own version of segment tree, first try: 2.18 (maximum score 30)
only pass 4 test cases.

C# practice 1

2. Second practice, score 1.08 max-score: 30, pass test case 0 and 1.

C# practice 2

3. Third practice, score 0  max-score: 30, pass test case 0, 1

C# practice 3

It is a really good study case for understanding depth of problem solving. Timeout issue is critical, at the beginning of construction of segment tree, the time complexity should be O(n^2), not O(n), n is the people in the group, n < 100000.

Better score 0 to write your own code, comparing to copy other's code score 30. But do not understand the design and algorithm. 

References

1. Read the lecture note to help:

Lecture note to study.

2. Read the article about segment tree.