Introduction
This is an analysis of Codility  Magnesium 2014 Challenge.
 The problem is that, finding the longest path in a weighted graph in which the weights are ascending. Vertices can be visited multiple times.
 Here, length of a path means the number of vertices the path visits, not the weight sum of all edges that compose the path.
 Therefore, longest path means a path that visits more vertices than any other paths for the given graph.
 Time bound is O(V+E*log(E)).
Analysis
 A classic DFS search on every vertex can do this job, despite its worst time complexity is O(VE), which cause timeout.
 Let’s make an O(V+E*log(E)) approach.
 Because we do NOT need to trace the whole path, we just need to store a {w, l} pair for each vertex of the graph.
 This pair of data means that for a vertex V, the longest path ends with V has a length l path, and, the largest weight of the path is w.
 Then we pick edges one by one in ascending order, do some comparison and update the paired data for node which the edge connects.
Why this algorithm works?
 For any w_1 >= w_2 and l_1 >= l_2, we can always say that {w_1, l_1} is a better answer that {w_2, l_2}. Therefore, we only store the former answer. Note that, this only goes right when edges are picked by ascending order. That’s the GREEDY algorithm works.
 Sorting edges costs O(E*log(E)). Updating paired data costs O(V). The whole time cost is O(V+E*log(E)).
Source
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 
