Codility - Magnesium 2014

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)).