Welcome to FutureAppLaboratory

v=（*＾ワ＾*）=v

Codility - Magnesium 2014

| Comments

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

int result = 0;
Node root;
Edge[] edges;
Node[] nodes;

public int solution(int N, int[] A, int[] B, int[] C) {
    edges = new Edge[A.length];
    for (int i = 0; i < A.length; i++) {
        edges[i] = new Edge(A[i], B[i], C[i]);
    }
    Arrays.sort(edges, new Comparator<Edge>() {
        @Override
        public int compare(Edge o1, Edge o2) {
            // TODO Auto-generated method stub
            return o1.c - o2.c;
        }
    });

    int n = edges.length;

    nodes = new Node[200000];
    for (int i = 0; i < 200000; i++) {
        nodes[i] = new Node(0, 0);
    }

    for (int i = 0; i < n; i++) {
        // get start node
        int start = edges[i].a;
        int end = edges[i].b;

        Node cnodefront = nodes[start];
        Node cnodeend = nodes[end];

        Node nextEndNode = nodes[end];
        Node nextStartNode = nodes[start];

        if (cnodefront.value < edges[i].c) {
            nextEndNode = createNextNode(i, end, cnodefront.depth + 1);
        }

        if (cnodeend.value < edges[i].c) {
            nextStartNode = createNextNode(i, start, cnodeend.depth + 1);
        }

        nodes[end] = nextEndNode;
        nodes[start] = nextStartNode;

    }

    return result;
}

private Node createNextNode(int i, int end, int depth) {
    Node node = new Node(edges[i].c, depth);
    Node cnode = nodes[end];

    if (depth > cnode.depth) {
        result = Math.max(result, depth);
        return node;
    } else {
        return cnode;
    }
}

private class Edge {
    int a, b, c;
    public Edge(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
}

private class Node {
    int value;
    int depth;
    public Node(int value, int depth) {
        this.value = value;
        this.depth = depth;
    }
}

Comments