Categories
coding solutions

Codility: NailingPlanks Solution

Task

You are given two non-empty arrays A and B consisting of N integers. These arrays represent N planks. More precisely, A[K] is the start and B[K] the end of the K−th plank.

Next, you are given a non-empty array C consisting of M integers. This array represents M nails. More precisely, C[I] is the position where you can hammer in the I−th nail.

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

The goal is to find the minimum number of nails that must be used until all the planks are nailed. In other words, you should find a value J such that all planks will be nailed after using only the first J nails. More precisely, for every plank (A[K], B[K]) such that 0 ≤ K < N, there should exist a nail C[I] such that I < J and A[K] ≤ C[I] ≤ B[K].

Write a function: int solution(vector<int> &A, vector<int> &B, vector<int> &C);

that, given two non-empty arrays A and B consisting of N integers and a non-empty array C consisting of M integers, returns the minimum number of nails that, used sequentially, allow all the planks to be nailed.

If it is not possible to nail all the planks, the function should return −1.

Write an efficient algorithm for the following assumptions:
  • N and M are integers within the range [1..30,000];
  • each element of arrays A, B, C is an integer within the range [1..2*M];
  • A[K] ≤ B[K].

Solution

While this is under the section for binary search algorithms, in fact there is no advantage to doing a binary search of the number of nails. So this algorithm simply increases the number of nails until all the planks are nailed.
One gotcha is that more than one nail may be in the same position, so we first have to build an array of the nail positions, populated by the lowest index of C that has a nail in that position. This is the array minNails[0].
Then we can iterate through the planks, for each plank calculating the minimum nail index that fixes that plank. The answer is the maximum of these minimum indexes.
This algorithm works, however it fails to pass the performance tests because for each plank we need to iterate over all of the nail positions.
As an optimisation then, the solution below builds indices of the minimum nail index in ranges starting at each position. The ranges increase in powers of two and are held in the arrays minNails[].
So minNails[x][pos] holds the minimum nail index from pos to pos+2x. Then to find the minimum in an arbitrary range, we split the range up into a sum of powers of two and find the minimum of each of these subranges using the array. This takes log(M) steps for a range of size M.
This is an implementation of the segment tree solution to the Range Minimum Query problem, storing the tree in arrays.
This takes the worst case time to find a minimum value to log(M), giving a total time complexity of N.log(M).
int minNailIndex(int pos, int end,const vector<vector<int>> &minNails) { int minIndex = __INT32_MAX__; int step = 0x10000; //1 << 16; for (int pow = 15; pow >= 0; pow–) { step >>= 1; if (pos + step <= end + 1) { minIndex = min(minIndex, minNails[pow][pos]); pos += step; } if(pos >= end+1) break; } return minIndex ; } int solution(vector<int> &A, vector<int> &B, vector<int> &C) { size_t N = A.size(); assert(N == B.size()); size_t M = C.size(); vector<vector<int>> minNails(16); // 2^15 = 32K // max M is 30000, values can be up to 2*M inclusive for (int i = 0; i < 16; i++) { minNails[i] = vector<int>(60001, __INT32_MAX__); // > max val } for (int i = 0; i < (int)M; i++) { int nailPos = C[i]; minNails[0][nailPos] = min(minNails[0][nailPos], i); } int step = 1; for (int pow = 1; pow < 16; pow++) { for (int pos = 0; pos < (int)60001 – step; pos++) { minNails[pow][pos] = min(minNails[pow – 1][pos], minNails[pow – 1][pos + step]); } step <<=1; } int minIndex = -2; for (size_t i = 0; i < N; i++) { int thisPlankMin = minNailIndex(A[i], B[i], minNails); if(thisPlankMin == __INT32_MAX__) return -1; minIndex = max(minIndex, thisPlankMin); } return minIndex + 1; }

Results

Codility Results

Correctness100%
Performance100%
Reported Time Complexity O((N + M) * log(M))

Test Function

This code tests the solution

int main() { const int N = 30000; vector<int> A(N); vector<int> B(N); vector<int> C(N); for (size_t i = 0; i < N; i++) { A[i] = 2*i+1; B[i] = 60000; C[i] = 2*i+1; } check(A,B,C,N); check({1}, {4}, {4}, 1); check({1, 4, 5, 8}, {4, 5, 9, 10}, {4, 6, 7, 10, 2}, 4); check({1, 4}, {4, 5}, {4, 6, 7, 10, 2}, 1); check({1, 4, 5}, {4, 5, 9}, {4, 6, 7, 10, 2}, 2); check({1}, {4}, {5}, -1); check({1000, 4000, 5000, 8000}, {4000, 5000, 9000, 10000}, {4000, 6000, 7000, 10000, 2000}, 4); }

Other Solutions

These are some other solutions to this problem on the web
This blog has an interesting alternative solution in Python. This sorts the nails by position, keeping track of the index into C, then for each plank it does a binary search to find the first nail in the plank and then iterates through the nails in the plank to find the minimum index. As the post author points out, in the worst case each plank contains all the nails and it has O(N * (log(M)+M)) run time.
This solution combines the segment tree solution to the Range Minimum Query problem with the idea of finding the first nail position for a plank by using a binary search tree. You would expect this to have a worst-case time of O((N + M) * log(M))but use less memory than my solution.

Index of solutions to Codility Lessons in C++

Leave a Reply

Your email address will not be published. Required fields are marked *