## понедельник, 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 = 1  A = 5  A = 2
A = 1  A = 4  A = 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 > B:
return iF

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