Maximum Disjoint Subtree Product - World codesprint 10

April 29, 2017

Introduction

It is a wise decision to spend time for each algorithm in the contest. Even Julia did not make any points last few hours, she found out that it is better to write a brute force solution even scoring 0, or write a blog about the algorithm.

The maximum disjoint subtree product algorithm should be a DFS/ BFS tree problem. Julia had some idea to solve the problem, but she was not sure how simple the code should be.

The problem statement is here. Just work on the most simple test case, and then write some code first.

Plan to do 60 minutes workout on the algorithm. 3:03pm - 4:03pm.

Code preparation 

Read one of players resume, and go over all the players in united states scoring 60 on the algorithm. 3:13 pm, study those players and get myself ready to think about a solution and start to write down some code. 

4:00pm now - spent 20 minutes to go over those 24 people scoring 60 maximum points, and I knew that those are very experienced ones, Julia spent time to loo at those who scored 3 points, 6 points, to 30 points. Those are players who are working hard as well.

Go back to study on topcoder webpage after googling disjoint set, make the algorithm general. How to approach? Article is here. 

Finished 15 minutes to read the disjoint set article first. Time is checked, 4:15pm.

Disjoint-set Data structure - topcoder tutorial

Read the article - link is here, and take some notes. 

Disjoint sets, dynamic disjoint sets,
Define two sets are disjoint - intersection is null
representative - Every disjoint set contains a representative

It is assumed that the representative of each group is the person with the biggest index in the article.
Every one has its own group
-> the group containing 1 and the group with 2 will become one group.
-> the representative of first group will become 2.

How to check if two persons are in the same group? Check the representative.

Define some operations:
Create-Set
Merge-Set
Find-set

Implementation with linked lists

Each element will be in a linked list and will contain to the next element in the set and another point to the representative of the set.

Read the graph representing the problem, catch up more later.

Read how to implement the Merge-Set(x,y) operations.

a weighted-union heuristic - complexity O(M + NlogN)
where M is the number of operations (Find-sets, Merge-sets, Create-sets), N is the number of operations Create-Sets.

Two heuristics -

Union by rank
Path compression

Time is checked again, 4:53pm.

Move on to next topic

Disjoint Set questions on Hackerrank

Link is here.

Disjoint Set tutorial on hackerearth 

The article link is here.

Being a hacker 

Wrote a brute force solution to work out on sample test case, but the code passed test case 1, failed 2, 3, and time out everywhere. Score 0. Time checked, 10:53pm.

Can hackerrank give me 0.001 points? I just need 0.0001 points.

Is that possible to give 0.25 points for passing test case 1? I wrote a brute force solution just to try to advance my ranking. My points are 36 points, ranking from 767 - 1307 all scoring 36 points. Never work so hard to advance 0.25 point, failed this time.
Here is the comment link. 

Follow up 

Code written in the contest is here. 

Study one of C# submission code. C# study code is here with sample test case. 
Continue to code review the algorithm, prepare to give a code review on stackexchange.com, here is the C# code.