Count of Smaller Numbers After Self

April 27, 2017

Plan to study the segment tree algorithm - count of smaller numbers after all.

Plan to read the blog about the algorithm. The link is here.

segment tree

April 27, 2017

Plan to spend 30 minutes a time to learn segment tree from the Chinese blog.

code review: Hackerrank kindergarten adventures

March 19, 2017

Problem statement

Code review is posted here.

C# code - still work on more test cases on API testing, Modify and Query.

Introduction

Julia starts to learn binary index tree and segment tree through hackerrank university codesprint #2 in November 2016, she tried a few times but failed each time. She knew that she is better to work on the algorithm "kintergarden adventure" and learn from the algorithm.

She also did post the question on segment tree algorithm on code review to ask help on Dec. 10, 2016, and then the question "kintergarden adventure" was closed. Through the incident, Julia knew that she was afraid to learn by herself.

Julia is very comfortable at data analysis, so in order to figure out the algorithm, Julia chose to have some test case study, put together some data, and then taught herself what to look for through those tables.

Test case study

For example, there are 20000 students in the circle, and the first student only need to 0 minute to finish drawing, so that if the teacher starts from any students from ID = 1 to 20000, the first student can complete the drawing. SegmentTree class Modify API has to take the task to mark those 20000 nodes as value 1, it is not scalable for 3 seconds time limit, so that we can use up to logN intervals to cover the range of [1, 20000].

To make it simple, we assume that the range's width is 1024 instead of 20000, and see how many steps we need to mark in tree[]. Not up to 1024, but in the level of logN = log1024 = 10.


Here is the SegmentTree class Modify API: To understand the test case, in order to modify 1024 nodes as 1, we only do it in less and equal to 10 times, here is the two images to explain the detail.

The two variables of left and right are iterated from beginning to end 10 times, each iteration two variables's values are recorded in the table.

Let us get our hands dirty on this test case, RunTestcaseModify3() line 12, tree.Modify(0,1024,1). We look into the function call.

First row of table, left = 20001, right = 21024, since Modify API is called and function arguments: start = 0, count = 1024, value = 1,
read Modify API code line 5 and line 6, left is calculated as 20001 and right is calculated as 21024.

and more detail is here:

Action items

Review code review Hackerrank Modular Range Queries
Read the tutorial of segment tree.
Learn binary index tree from topcoder

Inspiration

This is the first time Julia started to use Microsoft Excel to do some test case analysis to help her understand the segment tree algorithm design.

All it takes is for her to have some patience. She read those two tables built by Microsoft Excel, and then she asks herself what is missing, what problems she can tell from those data. After a few times search, she comes out ideas to move forward her study.

Algorithm - Segment tree, lazy propagation

March 18, 2017

Introduction

Julia likes to invest 30 minutes to study Ahoy, Pirates! algorithm from this competitive programmer through her hackeerank contest experience, she usually studied the players and see what they share. She will find out the profile of Hackerrank and then she can measure how good the player is. Julia did some study on walmartLab codesprint last Oct. 2016 and she documented what she found.

She likes the article written called Advice For Beginners.

Also the writing of article is much better than 80% of Julia's blog. Julia likes the way the author using 3 different colors: purple, blue and red to construct a segment tree and explain the example. A lot of of hardwork, kudo for the author.

Algorithm study - Ahoy, Pirates!

Log of study history

1. March 18, 2017 - 2:14pm - 2:44pm

Good tool to use 

http://mathurl.com/

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

Nov. 16, 2016

It is time to learn Segment Tree quickly. Julia worked on Segment Tree a few times in 2016, but when she worked on the algorithm in the contest, she did not come out the idea using segment tree to solve the problem. Segment tree is also called binary index tree.

The best learning experience is a failure. She will remember forever how segment tree is applied to a real story - kindergarten adventures.

Problem statement

Previous blogs about segment tree:

1. Oct. 18, 2016
Segment Tree Tutorial

2. Sept. 25, 2016
Range Minimum Query blog

3. March 4, 2016
HackerRank: Bear and Steady Gene (I)

Study C# submissions:

1. C# code # 1
2. C# code #2
3. C# code #3
4. C# code #4
5. C# code #5

Study JavaScript submission

Study Java submission

There are over 60 solution to score 30 (maximum score 30), go over one by one, and learn a few tips from those solutions. Write down what you like most - 3 things in Java code.

1. Very structured code

2. Java code to study

No. 1
No. 2
No. 3

C solution

Julia's ideas to improve the performance:

1. Try to write some code first, or do some research to categorize the problem, narrow down the algorithm problem - segment tree. (Quickly go over competition books, search ideas!)

2. Either improving the research of categorizing the problem to classical problem, or be practical, using brute force solution to get a few points. (Just do it!)

3. Give up the effort on advanced algorithm, only focus on one of medium algorithms. If Julia work on this medium algorithm in the contest, put 10 hours work on it, then she could score full score. (Aim low target first!)

4. Try to get in Bronze medal first. Work on medium algorithm (maximum score 30) instead of advanced algorithm (maximum score 80). (Play safe! From medium to advanced)

5. Try to work on an algorithm in 2 hours range - Do not spend more than 2 hours on a problem. First work on medium algorithm each one 2 hours first. Increase the chance to score more points.

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

Nov. 13, 2016

Problem statement:

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

Julia spent over 1 hour to read problem statement, and worked on ideas to solve the problem on Nov. 11, 2016. She will write down her analysis later.

HackerRank: Bear and Steady Gene (I)

March 4, 2016

  Problem statement:
https://www.hackerrank.com/contests/hourrank-6/challenges/bear-and-steady-gene

  Editorial:

Let's first think when Limak can choose some particular interval (substring). We should care about the remaining letters, both in the prefix and the suffix. If there are more than n/4remaining letters of one type then we can't get a steady string. Otherwise, we know exactly how many letters of each type are missing and we can fill the removed interval with these exact letters. So, the interval can be chosen only if the remaining part doesn't contain more than n/4letters of some type.

For each possible starting index of the interval let's find the nearest (leftmost) possible ending index. You can create four segment trees, one for each letter. Then, for fixed interval you can check in O(1)whether there are at most n/4 remaining letters of each type. So, for each starting index you can binary search the earliest good ending index. Segment trees and binary search give us O(nlog2n). Let's make it faster.

First thing is to get rid of segment trees. It's enough to store prefix (and maybe suffix) sum for each letter, so you don't need segment trees anymore. It's ok to get AC but you can change one more thing. As we move with the starting index to the right, the ending index also moves to the right (or it doesn't change). So, we can use the two pointers technique to get O(n) solution. You can check codes below for details.

Julia's practice:
https://gist.github.com/jianminchen/80723bae951328a690bb

score 15 out of 50, there are 2 run time error, failed a few of test cases. The implementation is no better than brute force solution.

C# code implementation to study:

https://gist.github.com/jianminchen/153eab0defae014842e8

Readable code, with some analysis.
https://gist.github.com/jianminchen/fae9142eff9a6f9643fc

Java code implementation to study:
https://gist.github.com/jianminchen/d52ced38de0bffa2d9e8

C++ code to study:
https://gist.github.com/jianminchen/d7370b7e73013ee708be

write this one as well <- Great code, very readable!
https://gist.github.com/jianminchen/c6b51207f9cc9b083573

https://gist.github.com/jianminchen/80638c0db328d0098f3b

Binary search algorithm: (Java)
https://gist.github.com/jianminchen/d01faa03ca9b06696db3

Comment:
The brute force solution will not pass the test cases. 

It takes a lot of time to read 108 people's code - all scores 50 / 50. It is fun to read all 108 solution scoring 50/50.

Julia, take time to play with this algorithm.


Nov. 28, 2016

Study the code:
https://gist.github.com/jianminchen/c4f1c84c984e58fdcdc467e6f28d84e3
code review:
1. line 26, int[] a = new int[1007];
1007 is not meaningful, we know the size should be bigger than 'Z', and we only need the array of size 4
2. variable i and index are not meaningful. There are two loops.
3. valid function from line 49 - line 58
   line 52 - 55 - four constant chars are used.


Review the code and make the change:
https://gist.github.com/jianminchen/124b33e3d7aa0276e7b6ea4542c8ad5b
1. line 26 - 36, add 4 test cases, with 4 postcondition assertions
2. function name is changed to minChange
3. line 61, array of size 4 is declared instead of 1007
4. function indexOf() is added
5. variable names are changed, left, right, two pointers, move forward only
6. add two explanation variable c1, c2 to advoid complicated expression.
7. valid function is declared using a for loop.

Based on the code review on this post:
http://codereview.stackexchange.com/questions/142808/quick-sort-algorithm/142853#142853
answered by Eric Lippert