понедельник, 13 января 2014 г.

Codility. Train. Number-of-disc-intersections ★★★

Given an array A of N integers, we draw N discs in a 2D plane such that the I-th disc is centered on (0,I) and has a radius of A[I]. We say that the J-th disc and K-th disc intersect if J ≠ K and J-th and K-th discs have at least one common point.
Write a function:
def solution(A)
that, given an array A describing N discs as explained above, returns the number of pairs of intersecting discs. For example, given N=6 and:
A[0] = 1  A[1] = 5  A[2] = 2 
A[3] = 1  A[4] = 4  A[5] = 0  
intersecting discs appear in eleven pairs of elements:
  • 0 and 1,
  • 0 and 2,
  • 0 and 4,
  • 1 and 2,
  • 1 and 3,
  • 1 and 4,
  • 1 and 5,
  • 2 and 3,
  • 2 and 4,
  • 3 and 4,
  • 4 and 5.
so the function should return 11.
The function should return −1 if the number of intersecting pairs exceeds 10,000,000.
Assume that:
  • N is an integer within the range [0..100,000];
  • each element of array A is an integer within the range [0..2147483647].
Complexity:
  • expected worst-case time complexity is O(N*log(N));
  • expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.



Solution:
def solution(A):
  B, M = [], 0
  for i in xrange(len(A)):
    M += len(B) - binF(B, i - A[i])
    if M > 10000000:
      return -1
    B.insert(binF(B, i + A[i]), i + A[i])
  return M

def binF(A, B):
  iF, iL = 0, len(A)
  if iL == 0 or \
    A[iL - 1] < B: 
    return iL
  if A[0] > B: 
    return iF

  while iF < iL:
    iM = iF + (iL - iF) / 2
    if B <= A[iM]:
      iL = iM
    else:
      iF = iM + 1
  return iF

Комментариев нет:

Отправить комментарий