Codility ‘NailingPlanks’ Solution

Short Problem Definition:

Count the minimum number of nails that allow a series of planks to be nailed..

Link

NailingPlanks

Complexity:

expected worst-case time complexity is O((N+M)*log(M));

expected worst-case space complexity is O(M)

Execution:

The solution gets 100/100, but I am skeptical. The runtime is rather O(N * (log(M)+M)) than O((N+M)*log(M)).  Maybe it can be proven that the execution of the linear scan will never have to scan all possible positions. I also violate the space complexity by creating a copy of A+B.

Solution:
PLANK_START = 0
PLANK_END = 1

NAIL_ARR_IDX = 0
NAIL_HIT_LOCATION = 1

class NoNailFoundException(Exception):
    def __init__(self):
        pass

def findPosOfNail(nails, plank, previous_max):
    nail_idx = -1
    result = -1

    # logarithmic scan O(log(M))
    lower_idx = 0
    upper_idx = len(nails) - 1

    while lower_idx <= upper_idx:
        mid_idx = (lower_idx + upper_idx) // 2
        if nails[mid_idx][NAIL_HIT_LOCATION] < plank[PLANK_START]:
            lower_idx = mid_idx + 1
        elif nails[mid_idx][NAIL_HIT_LOCATION] > plank[PLANK_END]:
            upper_idx = mid_idx - 1
        else:
            upper_idx = mid_idx - 1
            result = nails[mid_idx][PLANK_START]
            nail_idx = mid_idx

    if result == -1:
        raise NoNailFoundException

    # linear scan O(M)
    nail_idx += 1
    while nail_idx < len(nails):
        if nails[nail_idx][NAIL_HIT_LOCATION] > plank[PLANK_END]:
            break
        result = min(result, nails[nail_idx][NAIL_ARR_IDX])
        if result <= previous_max:
            return result
        nail_idx += 1

    if result == -1:
        raise NoNailFoundException

    return result

def getNrNailsRequired(planks, nails):
    result = 0
    for plank in planks:
        result = max(result, findPosOfNail(nails, plank, result))

    return result+1

def solution(A, B ,C):
    planks = zip(A,B)

    nails = sorted(enumerate(C), key=lambda var: var[1])

    try:
        return getNrNailsRequired(planks, nails)
    except NoNailFoundException:
        return -1

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Zheng Xu

    Hello Martin,

    Your solution does not run fast enough when implemented in Java. I had the same solution as you, but written in Java and one test case failed to pass due to time out. I think you got 100/100 because the time limit for Python was set too high by Codility.

    Later, I came up with an optimal solution with time complexity of O((N+M)*log(M)). The problem with your solution is the part that begins at line #33 that does a linear scan of all possible solutions to get the smallest index. However, we can get the smallest index in O(logM) time by using Segment Tree to implement Range Minimum Query [1][2].

    [1] http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/
    [2] http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static

    My Code: https://codility.com/demo/results/demoZTYPGY-46B/

    Cheers,

    Zheng Xu

  • Hi Zheng,

    thank you so much for the update. I haven’t looked into the problem since I posted it, but it bother me great time back then. I did not think of RMQs.
    I have to update the post :).

    You said, that you first came up with an equivalent of my solution. How did you find a better way? Wanna walk me through your thinking process?

    cheers,
    Martin

    • Zheng Xu

      Hello Martin,

      I came up with an optimal solution almost by accident. After giving up on solving NailingPlanks, I was learning about Binary Index Tree on GeeksForGeeks. The author of the article on Binary Index Tree mentioned that Binary Index Tree is similar to Segment Tree, which is able to solve a problem known as Range Minimum Query. And that’s when I realized that finding the smallest index with a linear scan is one way of implementing Range Minimum Query. Afterwards, I found on Topcoder and GeeksForGeeks a few better ways of implementing Range Minimum Query. I picked Segment Tree to solve NailingPlanks because I felt it was easy to understand and implement. The Topcoder tutorial on Range Minimum Query has a few other ways, but they were more difficult to understand.

      Cheers,

      Zheng Xu

  • I just found a solution to the problem in log(M)*N time. One single RMQ, with use of additional space equivalent to O(M).

    https://codility.com/demo/results/demo8SEAN3-TP3/

    import math
    class RMQ:
    def __init__(self, n):
    self.sz = 1
    self.inf = (1 << 31) - 1
    self.sz = (1 << int(math.ceil(math.log(n) / math.log(2))))
    self.dat = [self.inf] * (2 * self.sz - 1)

    def update(self, idx, x):
    idx += self.sz - 1
    if self.dat[idx] 0:
    idx = (idx - 1) >> 1
    self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2])

    def fill(self, A):
    for index,value in enumerate(A):
    self.update(index,(value, index))

    def query(self, a, b):
    return self.query_help(a, b, 0, 0, self.sz)

    def query_help(self, a, b, k, l, r):
    if r <= a or b <= l:
    return self.inf
    elif a <= l and r >1),
    self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r))
    def __str__(self):
    return "RMQ of size " + str(self.sz) + " with " + str(self.dat)

    def solution(A, B, C):
    r = RMQ(max(C)+1)
    for idx in xrange(len(C)):
    r.update(C[idx], idx)

    min_nail_idx = 0
    for idx in xrange(len(A)):
    min_nail_idx = max(min_nail_idx, r.query(A[idx], B[idx]+1))

    if min_nail_idx == r.inf:
    return -1
    else:
    return min_nail_idx+1

  • BG

    This solution also got 100 / 100. complexity is ((N+M)logM)

    https://codility.com/demo/results/demo75ADW5-3PH/

    #include
    bool nails_enough( int j, vector &A, vector &B, vector &C);

    int solution(vector &A, vector &B, vector &C) {

    int last = (int)C.size();
    int bgn = 0;
    int mid=0;
    int result =-1;
    while(bgn<=last)
    {
    mid = (last+bgn)/2;
    if(nails_enough(mid,A,B,C))
    {

    last=mid-1;
    result = mid;
    }else
    bgn=mid+1;
    }
    return result;
    }

    bool nails_enough(int j,vector &A, vector &B, vector &C)
    {
    std::vector used_nails (C.begin(),C.begin()+j);
    //for(int j = 0; j < (int)used_nails.size();j++)
    // cout<<used_nails[j]<<endl;
    sort(used_nails.begin(),used_nails.end());
    // binary search again for fitted nail

    for(int j = 0; j < (int)A.size();j++)
    {
    int last = (int)used_nails.size()-1;
    int mid = 0;
    int bgn = 0;
    bool found = false;
    while (bgn = A[j] && used_nails[mid] <= B[j]) // fit
    {
    found = true;
    break;
    }
    if(used_nails[mid] B[j])
    {
    last = mid-1;
    }
    }
    if (found == false)
    return false;
    }
    return true;
    }

  • Dragan Bozanovic

    Thanks for posting the solution. I came to a solution with linear complexity. In my solution I first discard all planks that completely wrap other planks, because a nail used for a wrapped plank can be used for all planks that wrap it.

    I explained the algorithm in more details at:
    http://draganbozanovic.blogspot.rs/2016/04/codility-nailingplanks-linear-complexity.html

  • Yavor Yanev

    Hi Martin, this is the first time I write in your site, so thanks a lot for the great solutions and explanations.

    I understand this is an old topic but still I want to suggest my solution to the problem as I think it’s clear, meets the time and space complexity requirements and I couldn’t see a similar one in the comments. Here it is:

    public class NailingPlanks
    {
    public int solution(int[] A, int[] B, int[] C)
    {
    int minPlanks = 1;
    int maxPlanks = C.Length;
    int result = -1;
    while (minPlanks <= maxPlanks)
    {
    int midPlanks = (maxPlanks + minPlanks) / 2;
    if (AllNailed(midPlanks, A, B, C))
    {
    maxPlanks = midPlanks – 1;
    result = midPlanks;
    }
    else
    {
    minPlanks = midPlanks + 1;
    }
    }

    return result;
    }

    private bool AllNailed(int planksCount, int[] A, int[] B, int[] C)
    {
    int[] nailsMarked = new int[2 * C.Length + 1];
    for (int i = 0; i < planksCount; i++)
    {
    nailsMarked[C[i]] = 1;
    }

    // generate prefix sums so we can make queries for the plank range
    // for example plank(1,5) is nailed when the number of nails at start and end differs,
    // i.e. there is a nail in this range
    for (int i = 1; i < nailsMarked.Length; i++)
    {
    nailsMarked[i] += nailsMarked[i – 1];
    }

    bool allNailed = true;
    for (int i = 0; i 0;
    }

    return allNailed;
    }
    }

    • Hi Yevor,

      thanks for sharing!

    • Neto

      Hi,

      It works perfect , but whay if i pass the following input it gives indexoutofboundsexception :

      ([1, 4, 5, 8], [4, 5, 9, 10], [4, 6, 7, 55, 2])

      Isn’t this a valid input ?

      Thanks

      • Yavor Yanev

        Hi Neto,

        Thanks for the question. In the assignment you have:
        * each element of arrays A, B, C is an integer within the range [1..2*M];
        where M is the number of elements of C, which in your case is 5, so it could contain elements within the range [1, 10].

    • Charlie

      This is very clear thank you!