Culture Conference - Rookie 3 contest

May 7, 2017

Problem statement: Culture Conference

Introduction

It is very interesting contest experience. Julia did not write a lot of code in Rookie contest, first she decided to review Union find algorithm, studied one of C# solution first. But in less than one hour, she used the algorithm to score a full score 20 on a medium algorithm - Maximum tourism. And then she started to work on the hard algorithm called Culture conference with maximum score 55. Julia also did not have time to write code, she was busy with tennis sport 2 hours, and one hour mocking interview around 8 pm. So she decided to use same algorithm Union Find to calculate the minimum number to attend the conference, a minimum dominating set, she scored 3.5 and then made some improvement to score 5.5.

One algorithm Union find helped her to score more than 30 point on two algorithms in the contest.

Here is her submission report on the algorithm.

Code review 

C# code is here.

The function Julia worked on in the contest from line 248 to 269 is here. She tried to adjust the maximum saved people by thinking about one node with more than one child, how many can be saved to let the parent node to go to culture conference, that is children.Count - 1.

Code snippet is here:

Follow up 

May 5, 2017

After the contest, study code written in Cpp file. Code is here.

Review code and then write a C# code. Code is here.

Performance Talk - 5 points to 55 points

10:37pm May 5/2017

Performance on this algorithm is based on the points I got. I got 5 points,  5 / 55 points, it is almost 10%. It is the hard algorithm, but the solution is not that hard to figure out.

Julia has to look into the performance issue in the contest Rookie 3, and then write down some tips to improve. Simple and practical tips.

May 9, 2017

Download test case 2, and then test the C# code in the contest using test case 2, and then modified the code. It took hours to fix the issues related to union find algorithm. Code is here, still need more work. Union Find algorithm implemented only keeps every node's parent node to the disjoint set's root node. Its director supervisor is replaced with the root node. No way to get the correct answer.

May 10, 2017
Leave union find algorithm alone, add some data structure to check each node with subordinates and supervisor, similar to the study code. Therefore the algorithm can only handle those edges with burnout node with its parent, and also figure out how many people go to conference.

It is a good practice to add something to Union Find algorithm, therefore learn to solve a problem and also get chance to know more about Union Find algorithm.

Actionable Items:

Study lead board of Rookie3

Read the math Ph.D. student - a good programming on Rookie 3 - Kevin Vissuet is the profile. Resume is here to take a look.

Aaron Albin - Amazon employee