Test results - Codility

Tasks Details

medium

1. NailingPlanks

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

100%

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].

For example, given arrays A, B such that:

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

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

C[0] = 4 C[1] = 6 C[2] = 7 C[3] = 10 C[4] = 2

if we use the following nails:

0, then planks [1, 4] and [4, 5] will both be nailed.

0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.

0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.

0, 1, 2, 3, then all the planks will be nailed.

Thus, four is the minimum number of nails that, used sequentially, allow all the planks to be nailed.

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.

For example, given arrays A, B, C such that:

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

the function should return 4, as explained above.

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 and C is an integer within the range [1..2*M];

A[K] ≤ B[K].

Solution

Programming language used C++

Time spent on task 1 minutes

Notes

not defined yet

Task timeline

Code: 20:09:19 UTC, cpp, verify, result: Failed

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


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;
}

Analysis

Compile error

func.cpp: In function 'int solution(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
func.cpp:18:23: error: 'assert' was not declared in this scope
   assert(N == B.size());
                       ^

Code: 20:09:40 UTC, cpp, 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

#include <algorithm>
#include <cassert>
#include <iostream>
#include <math.h>
#include <vector>

using namespace std;
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;
}

Analysis

▶

example
example test

✔

Code: 20:09:45 UTC, cpp, 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

#include <algorithm>
#include <cassert>
#include <iostream>
#include <math.h>
#include <vector>

using namespace std;
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;
}

Analysis

▶

example
example test

✔

Code: 20:09:48 UTC, cpp, final, score: 100

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

#include <algorithm>
#include <cassert>
#include <iostream>
#include <math.h>
#include <vector>

using namespace std;
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;
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O((N + M) * log(M))

▶

example
example test

✔

▶

extreme_single
single nail and single plank

✔

▶

extreme_point
nail is a point [1, 1]

✔

▶

few_nails_in_the_same_place
few nails are in the same place

✔

▶

random_small
random sequence, length = ~100

✔

▶

random_medium
random sequence, length = ~10,000

✔

▶

random_large
random sequence, length = ~30,000

✔

▶

extreme_large_planks
all large planks, length = ~30,000

✔

▶

large_point
all planks are points, length = ~30,000

✔