Question: https://codility.com/demo/take-sample-test/nailing_planks

Question Name: Nailing Planks or NailingPlanks

This question is designed to be solved with binary search method (**BUT there is a better solution! It is updated at the end of this post.**). And the binary solution is as following:

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 | def _findFirstNail(plankBegin, plankEnd, nails, preResult): # Function: find the nails, that could nail this plank. # # Input: plankBegin: the begin position of current plank # plankEnd: the end position of current plank # nails: the nails' position and index # preResult: for all of the previous planks, the # first preResult+1 nails in original array # could be sequentially used to nail them. # # Return: If all these nails are after the preResult's # position, return the first nail's position in # the original nails' array. # Else, return the preResult as the result. result = -1 # The index of nail in the original array resultPos = -1 # The index of nail in the sorted array nailLower = 0 nailUpper = len(nails) - 1 nailMid = 0 # Find the first nail, whose postion >= plankBegin and # position <= plankEnd, with binary search algorithm while nailLower <= nailUpper: nailMid = (nailLower + nailUpper) / 2 nailPosMid = nails[nailMid][1] if nailPosMid < plankBegin: nailLower = nailMid + 1 elif nailPosMid > plankEnd: nailUpper = nailMid - 1 else: nailUpper = nailMid - 1 result = nails[nailMid][0] resultPos = nailMid # Cannot find one, which could nail the plank if result == -1: return -1 # Linear search all the quanlified nails, and find # out the one with the earliest position. resultPos += 1 while resultPos < len(nails): # Not quanlified anymore. if nails[resultPos][1] > plankEnd: break result = min(result, nails[resultPos][0]) resultPos += 1 # If we find a position before the preResult. We could # terminate our search and return. # With a position before the preResult, the result for # this round must <= preResult. And globally, the final # result is the maximum of ALL the results in each rounds. # So the result of this round actually does not affect # the final result. if preResult >= result: return preResult return max(result, preResult) def solution(A, B, C): # Sort the nails according to their positions nails = sorted(enumerate(C), key = lambda x: x[1]) result = -1 for plankIndex in xrange(len(A)): # Find a nail for the current plank result = _findFirstNail(A[plankIndex], B[plankIndex], nails, result) if result == -1: return -1 # Cannot find such a nail return result + 1 |

In addition, there is an alternative solution without binary algorithm. This solution has a different but similar time complexity and space complexity (O(M+N)). And it does pass all the tests. Actually, for all binary search algorithms, they have a common issue: they access the items in different and non-consecutive places, that makes the modern data cache system valueless and helpless. That is the battle between heap sort and merge sort. That is also the battle among binary algorithms and their non-binary competitors. At lease in this war, non-binary wins. In the test result, the non-binary algorithm costs noticeable less time.

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 | def solution(A, B, C): result = -1 # Global result # Sort the planks according to firstly their begin position, # and then their end position planks = zip(A, B) planks.sort() # Sort the nails according to their position nails = sorted(enumerate(C), key = lambda x: x[1]) nailsIndex = 0 # Travel for each plank for plankIndex in xrange(len(planks)): plank = planks[plankIndex] # Find the first quanified nail in linear manner. Beware # that the planks are sorted. For any two adjacent planks, # the begin position of the latter one will be: # either the same as the former's begin position # or after the former's # In both cases, the nails, which before the nailsIndex # of the former plank's round, would never be candidates # in the latter plank's round. Thus we only need to search # nails from the previous nailsIndex position. while nailsIndex < len(nails): if nails[nailsIndex][1] < plank[0]: nailsIndex += 1 elif nails[nailsIndex][1] > plank[1]: # And all the remaining nails > plank[1] # Impossible to find a quanlified nail return -1 else: # plank[0] <= nails[nailsIndex][1] <= plank[1] break else: # Cannot find one return -1 if plankIndex != 0 and plank[0] == planks[plankIndex-1][0]: # This plank and previous plank have the same begin # position. And the planks are sorted. So the end # position of this plank is after that of previous # plank. We continue the previous search. pass else: # This plank and previous plank have the different # begin position. We have to re-search from the # nailsIndex. tempRes = len(nails) # Local result for this round tempIndex = nailsIndex # Find the first one in all the quanlified nails while tempIndex < len(nails) and plank[0] <= nails[tempIndex][1] <= plank[1]: tempRes = min(tempRes, nails[tempIndex][0]) tempIndex += 1 # If we find a tempRes <= result, the final result # of current round will <= result. This tempRes # would never change the global result. Thus we # could ignore it, and continue the next round. if tempRes <= result: break result = max(result, tempRes) return result+1 |

Finally, thanks to @Guillermo (StackOverflow Profile) again, here is the C++ solution.

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 | #include <algorithm> #include <iostream> #include <climits> int binsearch(vector< pair<int,int> > &CP,int PlankB,int PlankE,int jmin) { int b,mid,e,value,resultpos,sjmin,j,CPsize; CPsize=CP.size(); b=0; e=CP.size()-1; resultpos=-1; // BinSearch for nail>=LeftPlankSide while (b<=e) { mid = ( b + e) / 2; value = CP[mid].first; if ( value >= PlankB ) { e=mid-1; resultpos=mid; } else { b=mid+1; } } if (-1 == resultpos) return -1; value = CP[resultpos].first; if (value > PlankE) return -1; // Linear Search for nail <= RightPlankSide // with j<jmin or smaller j sjmin=INT_MAX; while ( (value <= PlankE) && (resultpos < CPsize) ) { j=CP[resultpos].second; if (j <= jmin ) return jmin; if (j < sjmin ) sjmin=j; resultpos++; if ( resultpos < CPsize ) value = CP[resultpos].first; } return sjmin; } int solution(vector<int> &A, vector<int> &B, vector<int> &C) { int i,j,n,m,jmin; n = A.size(); m = C.size(); pair<int,int> p(0,0); vector< pair<int,int> > CP(m,p); for (j=0;j<m;j++) { CP[j].first =C[j]; CP[j].second=j; } sort( CP.begin(), CP.end() ); jmin=-1; for (i=0;i<n;i++) { jmin = binsearch(CP,A[i],B[i],jmin); if (-1==jmin) return -1; } return jmin+1; } |

**UPDATE (May 2nd, 2016)**: Many thanks toĀ Dragan@ (blog): he proposed a wonderful solution with linear time complexity. HisĀ blog includesĀ a Java solution. And here is my Python.

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 | from collections import deque class MinQueue(): ''' Implement a queue with min() function. ''' def __init__(self): # all_data is used to store all the raw data for this queue. self.all_data = deque() # min_data is used to store the data for min() function. The values # in min_data is in non-decreasing order. self.min_data = deque() return def enqueue(self, val): self.all_data.append(val) while self.min_data and self.min_data[-1] > val: self.min_data.pop() self.min_data.append(val) return def dequeue(self): # Check if the queue is empty. if not self.all_data: return None # The to-dequeue value is the minimum in current queue. if self.all_data[0] == self.min_data[0]: self.min_data.popleft() return self.all_data.popleft() def dequeue_all_if(self, cond): ''' Remove all heading values, if they satisfy the condition "cond". ''' while self.all_data and cond(self.all_data[0]): self.dequeue() return def min(self): ''' Return the minimal item in current queue. min() is O(1). ''' if self.min_data: return self.min_data[0] else: return None def solution(A, B, C): # Step 1: Clear all wrapper planks. If there are two planks A and B: # A.start <= B.start <= B.end <= A.end # A is a wrapper plank to B. # Step 1.1: all these planks having the same start point, remove the # longer wrapper planks. The time complexity is O(N). # There are at most 2 * len(C) planks. # If plank_end_points[i] is not zero, there is a plank, starting at i, # and ending at plank_end_points[i]. plank_end_points = [0] * (len(C) * 2 + 1) for index in xrange(len(A)): if plank_end_points[A[index]] == 0: plank_end_points[A[index]] = B[index] elif plank_end_points[A[index]] > B[index]: # Replace with the new and shorter one. plank_end_points[A[index]] = B[index] else: # Keep the old and shorter one. pass # Step 1.2: Remove all the other planks, who do not share the same start # points. The time complexity is O(N), because every plank # after step 1.1 will enter the stack "planks" once and may or # may not exit the queue (once or never). # All position values are in range [1..2*M]. Therefore 0 is never used. planks = [] # Pairs of (begin, end), sorting with begin position. for index in xrange(1, len(plank_end_points)): if plank_end_points[index] != 0: # Here is a plank. while planks and planks[-1][1] >= plank_end_points[index]: # Remove all the wrapper planks to current one. planks.pop() planks.append((index, plank_end_points[index])) del plank_end_points # Step 2: counting sort the nails, while removing the duplicate nails. # The time complexity is O(M). # If nails[i] is zero, there is not any nail in this place. Otherwise, if # nails[i] = j, the j(th) nail in C is placed in the i position of the # board. nails = [-1] * (len(C) * 2 + 1) for index in xrange(len(C)): if nails[C[index]] == -1: # If multiple nails hold the same position, we only keep the # earliest one. nails[C[index]] = index # Step 3: find the minimum number of nails that must be used until all the # planks are nailed. The time complexity is O(N+M), because: # a) Every plank after step 1 is checked once and only once; O(N) # b) After step 2, the nails, who are on top of any plank from a), # will be enqueued once and only once; otherwise, the remaining # nails are never touched; O(M) # c) The enqueued nails will dequeue once OR never dequeue. O(M) previous_plank = (0, 0) # The content in nails_queue is (nail order in C, nail position in board) # Nail order in C is used to compute min() function. # Nail position in board is determining when to enter and exit queue. nails_queue = MinQueue() result = (-1, -1) # An impossible result as the initial value. for plank in planks: # Remove all nails before this planks. nails_queue.dequeue_all_if(lambda x: x[1] < plank[0]) # Add all nails on this plank, if they are not in the queue. # When this plank is overlapping with the previous one, the nails # between plank[0] and previous_plank[1]] are already included in # queue. for index in xrange(max(plank[0], previous_plank[1]), plank[1] + 1): if nails[index] != -1: # Enqueue value: (nail order, nail position) nails_queue.enqueue((nails[index], index)) # Maybe there is no nail on this plank. if nails_queue.min() == None: return -1 # Find the earliest nail, which can fix this plank. result = max(result, nails_queue.min()) return result[0] + 1 |

While codility will give you 100% for these solutions, they exceed specified time complexity. Worst case – they are O(m*n). Below is a test sample to demonstrate this. It has the same number of planks and nails (n) and clearly shows that if you double the input, the total runtime time is quadrupled.

Yes, in the first solution:

Linear search all the quanlified nails.

So in the worst-case, it is N*M.

# This solution in python, takes O((N+M)*log(M) * log(log(M))), but passes the test suite on codility

Thanks for sharing!

I used different approach:

Thanks for sharing!

Can you please explain the logic of your code? What is the purpose of

nailsCounter?My solution has an optimal time complexity. Instead of doing a linear scan to find the earliest position, I used Segment Tree, which is O(logM). Thus, the overall time complexity of my solution is O((N + M) * log(M)).

A link to a blog post about my solution:

https://zhengxucoding.wordpress.com/2015/03/21/solution-to-codility-nailingplanks/

Thanks for sharing a different solution!

I managed to find 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.

More details at: http://draganbozanovic.blogspot.rs/2016/04/codility-nailingplanks-linear-complexity.html

Great idea!!! Many thanks!