Test results - Codility

Tasks Details

medium

1. NumberOfDiscIntersections

Compute the number of intersections in a sequence of discs.

100%

We draw N discs on a plane. The discs are numbered from 0 to N − 1. An array A of N non-negative integers, specifying the radiuses of the discs, is given. The J-th disc is drawn with its center at (J, 0) and radius A[J].

We say that the J-th disc and K-th disc intersect if J ≠ K and the J-th and K-th discs have at least one common point (assuming that the discs contain their borders).

The figure below shows discs drawn for N = 6 and A as follows:

A[0] = 1 A[1] = 5 A[2] = 2 A[3] = 1 A[4] = 4 A[5] = 0

There are eleven (unordered) pairs of discs that intersect, namely:

discs 1 and 4 intersect, and both intersect with all the other discs;

disc 2 also intersects with discs 0 and 3.

Write a function:

int solution(vector<int> &A);

that, given an array A describing N discs as explained above, returns the number of (unordered) pairs of intersecting discs. The function should return −1 if the number of intersecting pairs exceeds 10,000,000.

Given array A shown above, the function should return 11, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000];

each element of array A is an integer within the range [0..2,147,483,647].

Solution

Programming language used C++

Time spent on task 1 minutes

Notes

not defined yet

Task timeline

Code: 10:16:07 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

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;


int solution(vector<int> &A) {
  const int MAX_COUNT = 10000000;
  size_t N = A.size();
  // create arrays of frequency of left-hand edges, and rh edges
  auto lhes = new vector<int>(N);
  auto rhes = new vector<int>(N);

  for (size_t i = 0; i < N; i++) {
    // for all discs - count instances of edges at points
    int lhs = max(0, static_cast<int>(i) - A[i]);
    (*lhes)[lhs]++;
    int rhs = min(N - 1, static_cast<int>(A[i]) + i);
    (*rhes)[rhs]++;
  }
  int count = 0;
  int overlapping = 0;
  for (size_t i = 0; i < N; i++) {
    // find number of new discs at this point
    int newDiscs = (*lhes)[i];
    count += newDiscs * overlapping;
    count += newDiscs * (newDiscs - 1) / 2;
    if (count > MAX_COUNT)
      return -1;
    // update with number of new discs, minus number now passed
    overlapping += newDiscs - (*rhes)[i];
  }

  assert(count <= MAX_COUNT);
  return count;
}

Analysis

Compile error

func.cpp: In function 'int solution(std::vector<int>&)':
func.cpp:35:28: error: 'assert' was not declared in this scope
   assert(count <= MAX_COUNT);
                            ^

Code: 10:16:31 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

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

#include <cassert>
int solution(vector<int> &A) {
  const int MAX_COUNT = 10000000;
  size_t N = A.size();
  // create arrays of frequency of left-hand edges, and rh edges
  auto lhes = new vector<int>(N);
  auto rhes = new vector<int>(N);

  for (size_t i = 0; i < N; i++) {
    // for all discs - count instances of edges at points
    int lhs = max(0, static_cast<int>(i) - A[i]);
    (*lhes)[lhs]++;
    int rhs = min(N - 1, static_cast<int>(A[i]) + i);
    (*rhes)[rhs]++;
  }
  int count = 0;
  int overlapping = 0;
  for (size_t i = 0; i < N; i++) {
    // find number of new discs at this point
    int newDiscs = (*lhes)[i];
    count += newDiscs * overlapping;
    count += newDiscs * (newDiscs - 1) / 2;
    if (count > MAX_COUNT)
      return -1;
    // update with number of new discs, minus number now passed
    overlapping += newDiscs - (*rhes)[i];
  }

  assert(count <= MAX_COUNT);
  return count;
}

Analysis

▶

example1
example test

✔

Code: 10:16:36 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

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

#include <cassert>
int solution(vector<int> &A) {
  const int MAX_COUNT = 10000000;
  size_t N = A.size();
  // create arrays of frequency of left-hand edges, and rh edges
  auto lhes = new vector<int>(N);
  auto rhes = new vector<int>(N);

  for (size_t i = 0; i < N; i++) {
    // for all discs - count instances of edges at points
    int lhs = max(0, static_cast<int>(i) - A[i]);
    (*lhes)[lhs]++;
    int rhs = min(N - 1, static_cast<int>(A[i]) + i);
    (*rhes)[rhs]++;
  }
  int count = 0;
  int overlapping = 0;
  for (size_t i = 0; i < N; i++) {
    // find number of new discs at this point
    int newDiscs = (*lhes)[i];
    count += newDiscs * overlapping;
    count += newDiscs * (newDiscs - 1) / 2;
    if (count > MAX_COUNT)
      return -1;
    // update with number of new discs, minus number now passed
    overlapping += newDiscs - (*rhes)[i];
  }

  assert(count <= MAX_COUNT);
  return count;
}

Analysis

▶

example1
example test

✔

Code: 10:16:39 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

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

#include <cassert>
int solution(vector<int> &A) {
  const int MAX_COUNT = 10000000;
  size_t N = A.size();
  // create arrays of frequency of left-hand edges, and rh edges
  auto lhes = new vector<int>(N);
  auto rhes = new vector<int>(N);

  for (size_t i = 0; i < N; i++) {
    // for all discs - count instances of edges at points
    int lhs = max(0, static_cast<int>(i) - A[i]);
    (*lhes)[lhs]++;
    int rhs = min(N - 1, static_cast<int>(A[i]) + i);
    (*rhes)[rhs]++;
  }
  int count = 0;
  int overlapping = 0;
  for (size_t i = 0; i < N; i++) {
    // find number of new discs at this point
    int newDiscs = (*lhes)[i];
    count += newDiscs * overlapping;
    count += newDiscs * (newDiscs - 1) / 2;
    if (count > MAX_COUNT)
      return -1;
    // update with number of new discs, minus number now passed
    overlapping += newDiscs - (*rhes)[i];
  }

  assert(count <= MAX_COUNT);
  return count;
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

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

▶

example1
example test

✔

▶

simple1

✔

▶

simple2

✔

▶

simple3

✔

▶

extreme_small
empty and [10]

✔

▶

small1

✔

▶

small2

✔

▶

small3

✔

▶

overflow
arithmetic overflow tests

✔

▶

medium1

✔

▶

medium2

✔

▶

medium3

✔

▶

medium4

✔

▶

10M_intersections
10.000.000 intersections

✔

▶

big1

✔

▶

big2

✔

▶

big3
[0]*100.000

✔