Test results - Codility

Tasks Details

hard

1. SpeedCameras

Position speed cameras so as to minimize the lengths of unmonitored paths.

100%

Recently, more and more illegal street races have been spotted at night in the city, and they have become a serious threat to public safety. Therefore, the Police Chief has decided to deploy speed cameras on the streets to collect evidence.

There are N+1 intersections in the city, connected by N roads. Every road has the same length of 1. A street race may take place between any two different intersections by using the roads connecting them. Limited by their budget, the police are able to deploy at most K speed cameras on these N roads. These K speed cameras should be installed such that the length of any possible street race route not covered by speed cameras should be as short as possible.

You are given a map of the city in the form of two arrays, A and B of length N, and an integer K:

For each J (0 ≤ J < N) there is a road connecting intersections A[J] and B[J].

The Police Chief would like to know the minimum length of the longest path out of surveillance after placing at most K speed cameras.

Write a function:

class Solution { public int solution(int[] A, int[] B, int K); }

that, given arrays A and B of N integers and integer K, returns the minimum length of the longest path unmonitored by speed cameras after placing at most K speed cameras.

For example, given K = 2 and the following arrays:

A[0] = 5 B[0] = 1 A[1] = 1 B[1] = 0 A[2] = 0 B[2] = 7 A[3] = 2 B[3] = 4 A[4] = 7 B[4] = 2 A[5] = 0 B[5] = 6 A[6] = 6 B[6] = 8 A[7] = 6 B[7] = 3 A[8] = 1 B[8] = 9

the function should return 2. Two speed cameras can be installed on the roads between intersections 1 and 0 and between intersections 0 and 7. (Another solution would be to install speed cameras between intersections 0 and 7 and between intersections 0 and 6.) By installing speed cameras according the first plan, one of the longest paths without a speed camera starts at intersection 8, passes through intersection 6 and ends at intersection 3, which consists of two roads. (Other longest paths are composed of intersections 5, 1, 9 and 7, 2, 4).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..50,000];

each element of arrays A and B is an integer within the range [0..N];

K is an integer within the range [0..N];

the distance between any two intersections is not greater than 900.

Solution

Programming language used Java 8

Total time used 2 minutes

Effective time used 2 minutes

Notes

not defined yet

Task timeline

Code: 09:22:27 UTC, java, verify, result: Passed

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 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

import java.util.*;

public class Solution {

    private int rootIndex = 0;
    private int largestId = 0;
    private int sortedSubtreeDiameters[] = new int[50001];
    private Node nodeMap[] = new Node[50001];
    private boolean visited[] = new boolean[50001];
    private int diameter[] = new int[50001];

    static class Node {
        public int id;
        public List<Integer> edgeList;
        public Node(int v) {
            this.id = v;
            edgeList = new ArrayList<Integer>();
        }
        public void addEdge(Integer t) {
            edgeList.add(t);
        }
    }

    public int solution(int[] A, int[] B, int K) {
        int n = A.length;
        for (int i = 0; i < n; i++) {
            if (nodeMap[A[i]] == null) {
                nodeMap[A[i]] = new Node(A[i]);
            }
            if (nodeMap[B[i]] == null) {
                nodeMap[B[i]] = new Node(B[i]);
            }
            final Node na = nodeMap[A[i]];
            final Node nb = nodeMap[B[i]];
            na.addEdge(B[i]);
            nb.addEdge(A[i]);
            largestId = Math.max(largestId, A[i]);
            largestId = Math.max(largestId, B[i]);
        }

        rootIndex = A[0];
        int res = Integer.MAX_VALUE;

        int low = 0, high = Math.min(900, largestId);
        while (low <= high) {
            int mid = (low + high) / 2;
            if (isAvailabel(K, mid)) {
                res = Math.min(res, mid);
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return res;
    }

    public boolean isAvailabel(int cameraLimit, int notCoveredLength) {
        for (int i = 0; i < visited.length; i++) visited[i] = false;
        for (int i = 0; i < diameter.length; i++) diameter[i] = -1;
        if (dfs(nodeMap[rootIndex], notCoveredLength) > cameraLimit) {
            return false;
        }
        return true;
    }

    private int dfs(Node node, int limit) {
        if (node == null || visited[node.id]) {
            return 0;
        }

        visited[node.id] = true;

        int counter = 0;
        for (Integer id : node.edgeList) {
            counter += dfs(nodeMap[id], limit);
        }

        /*
                      @
                    /  \
                  @      @(current)
                / \    / \\\
               @  @    a b c d

         step 1: Sort diameters of subtrees in reverse order, store them in an array
         step 2: For each adjacent pair in the sorted array, e.g. [a, b], [b, c], [c, d].
            If a + b + 2 > limit, we break the edge connecting current node to a, and counter plus 1.
            Do the same for [b, c] and [c, d]
         step 3: For last child d. or if current node has only one child.
            If d + 1 > limit, we break the edge connecting current node to a, and counter plus 1.
         step 4: Set diameter of current node to the largest one of the remains(not broken ones).

         */

        /* step 1 */
        int n = 0;
        for (Integer id : node.edgeList) {
            if (diameter[id] != -1) {
                sortedSubtreeDiameters[n++] = (diameter[id]);
            }
        }

        Arrays.sort(sortedSubtreeDiameters, 0, n);
        for (int i = 0; i < n / 2; i++) { // reverse order
            int temp = sortedSubtreeDiameters[i];
            sortedSubtreeDiameters[i] = sortedSubtreeDiameters[n - 1 - i];
            sortedSubtreeDiameters[n - 1 - i] = temp;
        }

        /* step 2 */
        int maxDiameterAfterRemoval = -1;
        for (int i = 0; i < n - 1; i++) {
            if (sortedSubtreeDiameters[i] + sortedSubtreeDiameters[i+1] + 2 > limit) {
                counter++;
            } else {
                maxDiameterAfterRemoval = Math.max(maxDiameterAfterRemoval, sortedSubtreeDiameters[i]);
            }
        }

        /* step 3 */
        if (n >= 1) {
            int i = n - 1;
            if (sortedSubtreeDiameters[i] + 1 > limit) {
                counter++;
            } else {
                maxDiameterAfterRemoval = Math.max(maxDiameterAfterRemoval, sortedSubtreeDiameters[i]);
            }
        }

        /* step 4 */
        // if subtrees are all removed, we can treat current node as a leaf, so diameter becomes 0
        if (maxDiameterAfterRemoval == -1) {
            diameter[node.id] = 0;
        } else { // if still some subtrees remain, then set current node's diameter as one plus the largest
            diameter[node.id] = maxDiameterAfterRemoval + 1;
        }

        return counter;
    }

}

Analysis

▶

example
example from the problem statement

✔

Code: 09:22:59 UTC, java, verify, result: Failed

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

import java.util.*;

public class Solution {

    private int rootIndex = 0;
    private int largestId = 0;
    private int sortedSubtreeDiameters[] = new int[50001];
    private Node nodeMap[] = new Node[50001];
    private boolean visited[] = new boolean[50001];
    private int diameter[] = new int[50001];

    static class Node {
        public int id;
        public List<Integer> edgeList;
        public Node(int v) {
            this.id = v;
            edgeList = new ArrayList<Integer>();
        }
        public void addEdge(Integer t) {
            edgeList.add(t);
        }
    }

    public int solution(int[] A, int[] B, int K) {
        int n = A.length;
        for (int i = 0; i < n; i++) {
            if (nodeMap[A[i]] == null) {
                nodeMap[A[i]] = new Node(A[i]);
            }
            if (nodeMap[B[i]] == null) {
                nodeMap[B[i]] = new Node(B[i]);
            }
            final Node na = nodeMap[A[i]];
            final Node nb = nodeMap[B[i]];
            na.addEdge(B[i]);
            nb.addEdge(A[i]);
            largestId = Math.max(largestId, A[i]);
            largestId = Math.max(largestId, B[i]);
        }

        rootIndex = A[0];
        int res = Integer.MAX_VALUE;

        int low = 0, high = Math.min(900, largestId);
        while (low <= high) {
            int mid = (low + high) / 2;
            if (isAvailabel(K, mid)) {
                res = Math.min(res, mid);
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return res;
    }

    public boolean isAvailabel(int cameraLimit, int notCoveredLength) {
        for (int i = 0; i < visited.length; i++) visited[i] = false;
        for (int i = 0; i < diameter.length; i++) diameter[i] = -1;
        if (dfs(nodeMap[rootIndex], notCoveredLength) > cameraLimit) {
            return false;
        }
        return true;
    }

    private int dfs(Node node, int limit) {
        if (node == null || visited[node.id]) {
            return 0;
        }

        visited[node.id] = true;

        int counter = 0;
        for (Integer id : node.edgeList) {
            counter += dfs(nodeMap[id], limit);
        }

        /*
                      @
                    /  \
                  @      @(current)
                / \    / \\\
               @  @    a b c d

         step 1: Sort diameters of subtrees in reverse order, store them in an array
         step 2: For each adjacent pair in the sorted array, e.g. [a, b], [b, c], [c, d].
            If a + b + 2 > limit, we break the edge connecting current node to a, and counter plus 1.
            Do the same for [b, c] and [c, d]
         step 3: For last child d. or if current node has only one child.
            If d + 1 > limit, we break the edge connecting current node to a, and counter plus 1.
         step 4: Set diameter of current node to the largest one of the remains(not broken ones).

         */

        /* step 1 */
        int n = 0;
        for (Integer id : node.edgeList) {
            if (diameter[id] != -1) {
                sortedSubtreeDiameters[n++] = (diameter[id]);
            }
        }

        Arrays.sort(sortedSubtreeDiameters, 0, n);
        for (int i = 0; i < n / 2; i++) { // reverse order
            int temp = sortedSubtreeDiameters[i];
            sortedSubtreeDiameters[i] = sortedSubtreeDiameters[n - 1 - i];
            sortedSubtreeDiameters[n - 1 - i] = temp;
        }

        /* step 2 */
        int maxDiameterAfterRemoval = -1;
        for (int i = 0; i < n - 1; i++) {
            if (sortedSubtreeDiameters[i] + sortedSubtreeDiameters[i+1] + 2 > limit) {
                counter++;
            } else {
                maxDiameterAfterRemoval = Math.max(maxDiameterAfterRemoval, sortedSubtreeDiameters[i]);
            }
        }

        /* step 3 */
        if (n >= 1) {
            int i = n - 1;
            if (sortedSubtreeDiameters[i] + 1 > limit) {
                counter++;
            } else {
                maxDiameterAfterRemoval = Math.max(maxDiameterAfterRemoval, sortedSubtreeDiameters[i]);
                break;
            }
        }

        /* step 4 */
        // if subtrees are all removed, we can treat current node as a leaf, so diameter becomes 0
        if (maxDiameterAfterRemoval == -1) {
            diameter[node.id] = 0;
        } else { // if still some subtrees remain, then set current node's diameter as one plus the largest
            diameter[node.id] = maxDiameterAfterRemoval + 1;
        }

        return counter;
    }

}

Analysis

Compile error

Solution.java:133: error: break outside switch or loop
                break;
                ^
1 error

Code: 09:23:16 UTC, java, verify, result: Passed

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

import java.util.*;

public class Solution {

    private int rootIndex = 0;
    private int largestId = 0;
    private int sortedSubtreeDiameters[] = new int[50001];
    private Node nodeMap[] = new Node[50001];
    private boolean visited[] = new boolean[50001];
    private int diameter[] = new int[50001];

    static class Node {
        public int id;
        public List<Integer> edgeList;
        public Node(int v) {
            this.id = v;
            edgeList = new ArrayList<Integer>();
        }
        public void addEdge(Integer t) {
            edgeList.add(t);
        }
    }

    public int solution(int[] A, int[] B, int K) {
        int n = A.length;
        for (int i = 0; i < n; i++) {
            if (nodeMap[A[i]] == null) {
                nodeMap[A[i]] = new Node(A[i]);
            }
            if (nodeMap[B[i]] == null) {
                nodeMap[B[i]] = new Node(B[i]);
            }
            final Node na = nodeMap[A[i]];
            final Node nb = nodeMap[B[i]];
            na.addEdge(B[i]);
            nb.addEdge(A[i]);
            largestId = Math.max(largestId, A[i]);
            largestId = Math.max(largestId, B[i]);
        }

        rootIndex = A[0];
        int res = Integer.MAX_VALUE;

        int low = 0, high = Math.min(900, largestId);
        while (low <= high) {
            int mid = (low + high) / 2;
            if (isAvailabel(K, mid)) {
                res = Math.min(res, mid);
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return res;
    }

    public boolean isAvailabel(int cameraLimit, int notCoveredLength) {
        for (int i = 0; i < visited.length; i++) visited[i] = false;
        for (int i = 0; i < diameter.length; i++) diameter[i] = -1;
        if (dfs(nodeMap[rootIndex], notCoveredLength) > cameraLimit) {
            return false;
        }
        return true;
    }

    private int dfs(Node node, int limit) {
        if (node == null || visited[node.id]) {
            return 0;
        }

        visited[node.id] = true;

        int counter = 0;
        for (Integer id : node.edgeList) {
            counter += dfs(nodeMap[id], limit);
        }

        /*
                      @
                    /  \
                  @      @(current)
                / \    / \\\
               @  @    a b c d

         step 1: Sort diameters of subtrees in reverse order, store them in an array
         step 2: For each adjacent pair in the sorted array, e.g. [a, b], [b, c], [c, d].
            If a + b + 2 > limit, we break the edge connecting current node to a, and counter plus 1.
            Do the same for [b, c] and [c, d]
         step 3: For last child d. or if current node has only one child.
            If d + 1 > limit, we break the edge connecting current node to a, and counter plus 1.
         step 4: Set diameter of current node to the largest one of the remains(not broken ones).

         */

        /* step 1 */
        int n = 0;
        for (Integer id : node.edgeList) {
            if (diameter[id] != -1) {
                sortedSubtreeDiameters[n++] = (diameter[id]);
            }
        }

        Arrays.sort(sortedSubtreeDiameters, 0, n);
        for (int i = 0; i < n / 2; i++) { // reverse order
            int temp = sortedSubtreeDiameters[i];
            sortedSubtreeDiameters[i] = sortedSubtreeDiameters[n - 1 - i];
            sortedSubtreeDiameters[n - 1 - i] = temp;
        }

        /* step 2 */
        int maxDiameterAfterRemoval = -1;
        for (int i = 0; i < n - 1; i++) {
            if (sortedSubtreeDiameters[i] + sortedSubtreeDiameters[i+1] + 2 > limit) {
                counter++;
            } else {
                maxDiameterAfterRemoval = Math.max(maxDiameterAfterRemoval, sortedSubtreeDiameters[i]);
                break;
            }
        }

        /* step 3 */
        if (n >= 1) {
            int i = n - 1;
            if (sortedSubtreeDiameters[i] + 1 > limit) {
                counter++;
            } else {
                maxDiameterAfterRemoval = Math.max(maxDiameterAfterRemoval, sortedSubtreeDiameters[i]);
            }
        }

        /* step 4 */
        // if subtrees are all removed, we can treat current node as a leaf, so diameter becomes 0
        if (maxDiameterAfterRemoval == -1) {
            diameter[node.id] = 0;
        } else { // if still some subtrees remain, then set current node's diameter as one plus the largest
            diameter[node.id] = maxDiameterAfterRemoval + 1;
        }

        return counter;
    }

}

Analysis

▶

example
example from the problem statement

✔

Code: 09:23:32 UTC, java, verify, result: Passed

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

import java.util.*;

public class Solution {

    private int rootIndex = 0;
    private int largestId = 0;
    private int sortedSubtreeDiameters[] = new int[50001];
    private Node nodeMap[] = new Node[50001];
    private boolean visited[] = new boolean[50001];
    private int diameter[] = new int[50001];

    static class Node {
        public int id;
        public List<Integer> edgeList;
        public Node(int v) {
            this.id = v;
            edgeList = new ArrayList<Integer>();
        }
        public void addEdge(Integer t) {
            edgeList.add(t);
        }
    }

    public int solution(int[] A, int[] B, int K) {
        int n = A.length;
        for (int i = 0; i < n; i++) {
            if (nodeMap[A[i]] == null) {
                nodeMap[A[i]] = new Node(A[i]);
            }
            if (nodeMap[B[i]] == null) {
                nodeMap[B[i]] = new Node(B[i]);
            }
            final Node na = nodeMap[A[i]];
            final Node nb = nodeMap[B[i]];
            na.addEdge(B[i]);
            nb.addEdge(A[i]);
            largestId = Math.max(largestId, A[i]);
            largestId = Math.max(largestId, B[i]);
        }

        rootIndex = A[0];
        int res = Integer.MAX_VALUE;

        int low = 0, high = Math.min(900, largestId);
        while (low <= high) {
            int mid = (low + high) / 2;
            if (isAvailabel(K, mid)) {
                res = Math.min(res, mid);
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return res;
    }

    public boolean isAvailabel(int cameraLimit, int notCoveredLength) {
        for (int i = 0; i < visited.length; i++) visited[i] = false;
        for (int i = 0; i < diameter.length; i++) diameter[i] = -1;
        if (dfs(nodeMap[rootIndex], notCoveredLength) > cameraLimit) {
            return false;
        }
        return true;
    }

    private int dfs(Node node, int limit) {
        if (node == null || visited[node.id]) {
            return 0;
        }

        visited[node.id] = true;

        int counter = 0;
        for (Integer id : node.edgeList) {
            counter += dfs(nodeMap[id], limit);
        }

        /*
                      @
                    /  \
                  @      @(current)
                / \    / \\\
               @  @    a b c d

         step 1: Sort diameters of subtrees in reverse order, store them in an array
         step 2: For each adjacent pair in the sorted array, e.g. [a, b], [b, c], [c, d].
            If a + b + 2 > limit, we break the edge connecting current node to a, and counter plus 1.
            Do the same for [b, c] and [c, d]
         step 3: For last child d. or if current node has only one child.
            If d + 1 > limit, we break the edge connecting current node to a, and counter plus 1.
         step 4: Set diameter of current node to the largest one of the remains(not broken ones).

         */

        /* step 1 */
        int n = 0;
        for (Integer id : node.edgeList) {
            if (diameter[id] != -1) {
                sortedSubtreeDiameters[n++] = (diameter[id]);
            }
        }

        Arrays.sort(sortedSubtreeDiameters, 0, n);
        for (int i = 0; i < n / 2; i++) { // reverse order
            int temp = sortedSubtreeDiameters[i];
            sortedSubtreeDiameters[i] = sortedSubtreeDiameters[n - 1 - i];
            sortedSubtreeDiameters[n - 1 - i] = temp;
        }

        /* step 2 */
        int maxDiameterAfterRemoval = -1;
        for (int i = 0; i < n - 1; i++) {
            if (sortedSubtreeDiameters[i] + sortedSubtreeDiameters[i+1] + 2 > limit) {
                counter++;
            } else {
                maxDiameterAfterRemoval = Math.max(maxDiameterAfterRemoval, sortedSubtreeDiameters[i]);
                break;
            }
        }

        /* step 3 */
        if (n >= 1) {
            int i = n - 1;
            if (sortedSubtreeDiameters[i] + 1 > limit) {
                counter++;
            } else {
                maxDiameterAfterRemoval = Math.max(maxDiameterAfterRemoval, sortedSubtreeDiameters[i]);
            }
        }

        /* step 4 */
        // if subtrees are all removed, we can treat current node as a leaf, so diameter becomes 0
        if (maxDiameterAfterRemoval == -1) {
            diameter[node.id] = 0;
        } else { // if still some subtrees remain, then set current node's diameter as one plus the largest
            diameter[node.id] = maxDiameterAfterRemoval + 1;
        }

        return counter;
    }

}

Analysis

▶

example
example from the problem statement

✔

Code: 09:23:37 UTC, java, final, score: 100

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

import java.util.*;

public class Solution {

    private int rootIndex = 0;
    private int largestId = 0;
    private int sortedSubtreeDiameters[] = new int[50001];
    private Node nodeMap[] = new Node[50001];
    private boolean visited[] = new boolean[50001];
    private int diameter[] = new int[50001];

    static class Node {
        public int id;
        public List<Integer> edgeList;
        public Node(int v) {
            this.id = v;
            edgeList = new ArrayList<Integer>();
        }
        public void addEdge(Integer t) {
            edgeList.add(t);
        }
    }

    public int solution(int[] A, int[] B, int K) {
        int n = A.length;
        for (int i = 0; i < n; i++) {
            if (nodeMap[A[i]] == null) {
                nodeMap[A[i]] = new Node(A[i]);
            }
            if (nodeMap[B[i]] == null) {
                nodeMap[B[i]] = new Node(B[i]);
            }
            final Node na = nodeMap[A[i]];
            final Node nb = nodeMap[B[i]];
            na.addEdge(B[i]);
            nb.addEdge(A[i]);
            largestId = Math.max(largestId, A[i]);
            largestId = Math.max(largestId, B[i]);
        }

        rootIndex = A[0];
        int res = Integer.MAX_VALUE;

        int low = 0, high = Math.min(900, largestId);
        while (low <= high) {
            int mid = (low + high) / 2;
            if (isAvailabel(K, mid)) {
                res = Math.min(res, mid);
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return res;
    }

    public boolean isAvailabel(int cameraLimit, int notCoveredLength) {
        for (int i = 0; i < visited.length; i++) visited[i] = false;
        for (int i = 0; i < diameter.length; i++) diameter[i] = -1;
        if (dfs(nodeMap[rootIndex], notCoveredLength) > cameraLimit) {
            return false;
        }
        return true;
    }

    private int dfs(Node node, int limit) {
        if (node == null || visited[node.id]) {
            return 0;
        }

        visited[node.id] = true;

        int counter = 0;
        for (Integer id : node.edgeList) {
            counter += dfs(nodeMap[id], limit);
        }

        /*
                      @
                    /  \
                  @      @(current)
                / \    / \\\
               @  @    a b c d

         step 1: Sort diameters of subtrees in reverse order, store them in an array
         step 2: For each adjacent pair in the sorted array, e.g. [a, b], [b, c], [c, d].
            If a + b + 2 > limit, we break the edge connecting current node to a, and counter plus 1.
            Do the same for [b, c] and [c, d]
         step 3: For last child d. or if current node has only one child.
            If d + 1 > limit, we break the edge connecting current node to a, and counter plus 1.
         step 4: Set diameter of current node to the largest one of the remains(not broken ones).

         */

        /* step 1 */
        int n = 0;
        for (Integer id : node.edgeList) {
            if (diameter[id] != -1) {
                sortedSubtreeDiameters[n++] = (diameter[id]);
            }
        }

        Arrays.sort(sortedSubtreeDiameters, 0, n);
        for (int i = 0; i < n / 2; i++) { // reverse order
            int temp = sortedSubtreeDiameters[i];
            sortedSubtreeDiameters[i] = sortedSubtreeDiameters[n - 1 - i];
            sortedSubtreeDiameters[n - 1 - i] = temp;
        }

        /* step 2 */
        int maxDiameterAfterRemoval = -1;
        for (int i = 0; i < n - 1; i++) {
            if (sortedSubtreeDiameters[i] + sortedSubtreeDiameters[i+1] + 2 > limit) {
                counter++;
            } else {
                maxDiameterAfterRemoval = Math.max(maxDiameterAfterRemoval, sortedSubtreeDiameters[i]);
                break;
            }
        }

        /* step 3 */
        if (n >= 1) {
            int i = n - 1;
            if (sortedSubtreeDiameters[i] + 1 > limit) {
                counter++;
            } else {
                maxDiameterAfterRemoval = Math.max(maxDiameterAfterRemoval, sortedSubtreeDiameters[i]);
            }
        }

        /* step 4 */
        // if subtrees are all removed, we can treat current node as a leaf, so diameter becomes 0
        if (maxDiameterAfterRemoval == -1) {
            diameter[node.id] = 0;
        } else { // if still some subtrees remain, then set current node's diameter as one plus the largest
            diameter[node.id] = maxDiameterAfterRemoval + 1;
        }

        return counter;
    }

}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N*log(N)) or O(N*log(N)**2)

▶

example
example from the problem statement

✔

▶

tiny
0 or 1 edge to take

✔

▶

small1
small tests, N <= 6

✔

▶

small2
small tests, N <= 9

✔

▶

small3
small tests, N <= 14

✔

1.364 s

1.357 s

1.360 s

1.346 s

1.349 s

1.350 s

1.358 s

1.351 s

▶

medium1
medium tests, short paths, small K, N ~= 100

✔

▶

medium2
medium tests, medium paths, medium K, N ~= 300

✔

▶

medium3
medium tests, long paths, small K, N ~= 5000

✔

▶

binary_tree
binary tree, N ~= 50,000

✔

▶

star
tree forms a star, big K, N ~= 50,000

✔

▶

big1
big test, long paths, small K, N ~= 50,000

✔

▶

big2
big test, long paths, big K, N ~= 50,000

✔

▶

big3
big test, long paths, N ~= 50,000

✔