Welcome to FutureAppLaboratory

v=（*＾ワ＾*）=v

Codility - Phosphorus - 2014

| Comments

Introduction

This is an analysis of Codility - Prosphorus 2014 Challenge.

  • This problem is, finding the minimal number of guards to set in a tree which can prevent prisoners escaping to tree leaves.
  • Time bound and space bound are both O(N).

Analysis

  • Create a Node structure, holding its parent index, a boolean value presenting it is a prisoner or not. Then a boolean value presenting whether prisoners can escape down to leaves, and another boolean value presenting whether prisoners can escape from the root.
  • Depth-First-Search from node 0.
  • Adjust the result according to node 0’s state. Done.
  • A classic DFS holds time bound and space bound.
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

static int N = 200003;

boolean[] visited = new boolean[N];
Node[] nodes = new Node[N];
int res = 0;

public int solution(int A[], int B[], int C[]) {
    for (int i = 0; i < A.length; i++) {
        if (nodes[A[i]] == null) nodes[A[i]] = new Node();
        if (nodes[B[i]] == null) nodes[B[i]] = new Node();
        nodes[A[i]].tlist.add(B[i]);
        nodes[B[i]].tlist.add(A[i]);
    }

    if (C.length == 0) return 0;

    // if a prison is on leaf(exit), then we cannot stop them escaping
    for (int i = 0; i < C.length; i++) {
        if (isLeaf(nodes[C[i]])) {
            return -1;
        }
        nodes[C[i]].isPrisoner = true;
    }

    dfs(0);

    // if node 0 is has only one path, then it is an exit. 
    // we should set a guard if node 0 is exit && prisoners can escape to root
    return nodes[0].hasEscapeRoot && nodes[0].tlist.size() == 1 ? res + 1 : res;
}

void dfs(int nodeIndex) {
    visited[nodeIndex] = true;
    Node node = nodes[nodeIndex];

    for (int i = 0; i < node.tlist.size(); i++) {
        int nextNodeIndex = node.tlist.get(i);
        if (!visited[nextNodeIndex]) {
            nodes[nextNodeIndex].parentIndex = nodeIndex;
            dfs(nextNodeIndex);
        }
    }

    if (nodeIndex != node.parentIndex && (isLeaf(node)))  return;

    int n = 0;
    int escapesLeaf = 0;
    int escapesRoot = 0;
    for (int i = 0; i < node.tlist.size(); ++i) {
        int next = node.tlist.get(i);
        if (node.parentIndex == next) continue;
        n++;
        if (nodes[next].hasEscapeLeaf) escapesLeaf++;
        if (nodes[next].hasEscapeRoot) escapesRoot++;
    }

    if (node.isPrisoner) { // if root is PRISONER,
        node.hasEscapeLeaf = false; // then it must not have escape paths to leaf
        node.hasEscapeRoot = true; // but it can escape to root
        res += escapesLeaf; // set guards on those leaves
    } else { // if root is NOT PRISONER, 
        if (escapesLeaf == n) { // all subtrees has escape to leaf
            // it a empty subtree, do nothing
        } else if (escapesLeaf == 0) { // no subtree has escape to leaf
            // then we do NOT need a guard here
            node.hasEscapeLeaf = false; // set no escape to leaf
            if (escapesRoot > 0) { // if at least one subtree has prisoner can escape to root
                node.hasEscapeRoot = true;
            }
        } else { // has SOME escape path
            if (escapesRoot == 0) { // if no prisoner can escape to root
                // then we do NOT need a guard here
                node.hasEscapeLeaf = true; // because it has escape paths
                node.hasEscapeRoot = false; // obviously
            } else { // if some prisoner can escape to root
                res++; // set guard here, prevent them escape to leaves through this node
                node.hasEscapeLeaf = false; // we set the guard, so there is no escape path to leaves
                node.hasEscapeRoot = false; // as above
            }
        }
    }

}

boolean isLeaf(Node node) {
    if (node.tlist.size() == 1) return true;
    else return false;
}

class Node {
    int parentIndex;
    boolean isPrisoner = false;
    boolean hasEscapeLeaf = true;
    boolean hasEscapeRoot = false;
    List<Integer> tlist = new ArrayList<Integer>();
}

Comments