Bonnie and Cylde - week of code 33

June 16, 2017

Introduction

It is the expert level algorithm and Julia likes to work on the algorithm. 

Expert Level

Julia chooses to work on the expert level algorithm, Bonnie and Cylde. She chooses to study graph algorithm for a few hours, and then tries to find a solution. 

First, she reads the topcoder graph blogs. Blog link is here. 

Next, she will search all graph algorithm in Leetcode marking hard level, she will quickly go over 5 - 10 of them. 

Third, undirected graph lecture notes - link is here. 

Fourth, detect cycle in directed graph, link is here. Detect cycle in undirected graph, link is here. 

Fifth step, go over graph algorithms on geeksforgeeks.org website. The link is here. 

One of graph algorithms, "Print all paths from a given source to a destination". The blog is here. 

"Competitive Programming" authored by - Graph

Union find algorithm on hackerearth - link is here. 

Progress Report

Now it is 8:44 am Saturday morning, Julia has to review her submission result. The interesting part of expert level algorithm is that Julia has to go over a lot of content about graph, a lot of reading, and then she decided to use one of algorithms to solve the problem. 

The idea to solve the problem was original wrong, and then she made a minor change to make sense on second sample test case. 

The another interesting fact to write code for expert level algorithm is that Julia does not have a lot of code to write. The idea is quiet simple, but a few test cases timeout. It is hard to find the right idea. Julia has to do time analysis for the algorithm and see which one can survive the time limit. 

Follow up after the contest

Julia submitted the code in the contest and score 25% of maximum score, 22.86 out of maximum score 80. Julia just used union find algorithm and then used another idea to apply union find second time to exclude one of two source nodes. Code is here.