The algorithm for calculating the number of intersecting disks

Question

Given an array A of N integers, we draw the disks N in the 2D plane, so the ith disk has a center at (0,i) and a radius A[i] . We say that the kth disk and the jth disk intersect if the kth and jth disks have at least one common point.

Write function

 int number_of_disc_intersections(int[] A); 

which defines an array A describing drives N , as described above, returns the number of pairs of intersecting drives. For example, taking into account N=6 and

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

There are 11 pairs of intersecting disks:

 0th and 1st 0th and 2nd 0th and 4th 1st and 2nd 1st and 3rd 1st and 4th 1st and 5th 2nd and 3rd 2nd and 4th 3rd and 4th 4th and 5th 

therefore, the function should return 11. The function should return -1 if the number of intersecting pairs exceeds 10,000,000. The function may assume that N does not exceed 10,000,000.

Answer 1

So, you want to find the number of intersections of the intervals [iA[i], i+A[i]] .

Maintain a sorted array (call it X) containing iA[i] (there is also additional space in which there is a value i+A[i] ).

Now go through array X, starting from the leftmost interval (smallest iA[i] ).

For the current interval, perform a binary search to see where the right endpoint of the interval will go (ie, i+A[i] ) (called the rank). Now you know that it intersects all the elements on the left.

Add a counter with a rank and subtract the current position (provided that it is indexed), since we do not want to double the counting and self-intersection intervals.

O (nlogn) time, O (n) space.

Answer 2

O (N) complexity and O (N) memory.

 private static int Intersections(int[] a) { int result = 0; int[] dps = new int[a.length]; int[] dpe = new int[a.length]; for (int i = 0, t = a.length - 1; i < a.length; i++) { int s = i > a[i]? i - a[i]: 0; int e = t - i > a[i]? i + a[i]: t; dps[s]++; dpe[e]++; } int t = 0; for (int i = 0; i < a.length; i++) { if (dps[i] > 0) { result += t * dps[i]; result += dps[i] * (dps[i] - 1) / 2; if (10000000 < result) return -1; t += dps[i]; } t -= dpe[i]; } return result; } 

Answer 3

Ok, I adapted the idea of ​​Falk Huffner to C ++ and made changes to the range. On the contrary, what is written above, there is no need to go beyond the bounds of the array (no matter how large the values ​​in it are). At Codility, this code got 100%. Thanks Falk for a great idea!

 int number_of_disc_intersections ( const vector<int> &A ) { int sum=0; vector<int> start(A.size(),0); vector<int> end(A.size(),0); for (unsigned int i=0;i<A.size();i++){ if ((int)i<A[i]) start[0]++; else start[iA[i]]++; if (i+A[i]>=A.size()) end[A.size()-1]++; else end[i+A[i]]++; } int active=0; for (unsigned int i=0;i<A.size();i++){ sum+=active*start[i]+(start[i]*(start[i]-1))/2; if (sum>10000000) return -1; active+=start[i]-end[i]; } return sum; } 

Answer 4

This can be done even in linear time. In fact, it becomes easier if you ignore the fact that at each point there is exactly one interval with the center, and just consider it as a set of start and end points of the intervals. Then you can simply scan it on the left (Python code for simplicity):

 from collections import defaultdict a = [1, 5, 2, 1, 4, 0] start = defaultdict(int) stop = defaultdict(int) for i in range(len(a)): start[i - a[i]] += 1 stop[i + a[i]] += 1 active = 0 intersections = 0 for i in range(-len(a), len(a)): intersections += active * start[i] + (start[i] * (start[i] - 1)) / 2 active += start[i] active -= stop[i] print intersections 

Answer 5

Here is O (N) time, O (N) is a spatial algorithm requiring 3 runs over the array and without sorting, the tested result is 100% :

You are interested in a pair of discs. Each pair includes one side of one disk and the other side of the other disk. Therefore, we will not have duplicate pairs if we process one side of each disk. Let me call the sides right and left (I rotated the space thinking about it).

The overlay is either due to the fact that the right side overlaps another disk directly in the center (therefore, the pairs are equal in radius with some caution with respect to the length of the array) or because of the number of left sides existing on the very right edge.

So, we create an array containing the number of left sides at each point, and then this is a simple sum.

C code:

 int solution(int A[], int N) { int C[N]; int a, S=0, t=0; // Mark left and middle of disks for (int i=0; i<N; i++) { C[i] = -1; a = A[i]; if (a>=i) { C[0]++; } else { C[ia]++; } } // Sum of left side of disks at location for (int i=0; i<N; i++) { t += C[i]; C[i] = t; } // Count pairs, right side only: // 1. overlaps based on disk size // 2. overlaps based on disks but not centers for (int i=0; i<N; i++) { a = A[i]; S += ((a<Ni) ? a: Ni-1); if (i != N-1) { S += C[((a<Ni) ? i+a: N-1)]; } if (S>10000000) return -1; } return S; } 

Answer 6

Python 100/100 (tested) on coding, with O (nlogn) time and O (n) space.

The following is an implementation of @noisyboiler python @Aryabhatta method with comments and an example. Full credit to the original authors, any errors / poor wording - this is completely my mistake.

 from bisect import bisect_right def number_of_disc_intersections(A): pairs = 0 # create an array of tuples, each containing the start and end indices of a disk # some indices may be less than 0 or greater than len(A), this is fine! # sort the array by the first entry of each tuple: the disk start indices intervals = sorted( [(iA[i], i+A[i]) for i in range(len(A))] ) # create an array of starting indices using tuples in intervals starts = [i[0] for i in intervals] # for each disk in order of the *starting* position of the disk, not the centre for i in range(len(starts)): # find the end position of that disk from the array of tuples disk_end = intervals[i][1] # find the index of the rightmost value less than or equal to the interval-end # this finds the number of disks that have started before disk i ends count = bisect_right(starts, disk_end ) # subtract current position to exclude previous matches # this bit seemed 'magic' to me, so I think of it like this... # for disk i, i disks that start to the left have already been dealt with # subtract i from count to prevent double counting # subtract one more to prevent counting the disk itsself count -= (i+1) pairs += count if pairs > 10000000: return -1 return pairs 

The given example: taking into account [3, 0, 1, 6], the radius of the disk will look like this:

 disk0 ------- start= -3, end= 3 disk1 . start= 1, end= 1 disk2 --- start= 1, end= 3 disk3 ------------- start= -3, end= 9 index 3210123456789 (digits left of zero are -ve) intervals = [(-3, 3), (-3, 9), (1, 1), (1,3)] starts = [-3, -3, 1, 1] the loop order will be: disk0, disk3, disk1, disk2 0th loop: by the end of disk0, 4 disks have started one of which is disk0 itself none of which could have already been counted so add 3 1st loop: by the end of disk3, 4 disks have started one of which is disk3 itself one of which has already started to the left so is either counted OR would not overlap so add 2 2nd loop: by the end of disk1, 4 disks have started one of which is disk1 itself two of which have already started to the left so are either counted OR would not overlap so add 1 3rd loop: by the end of disk2, 4 disks have started one of which is disk2 itself two of which have already started to the left so are either counted OR would not overlap so add 0 pairs = 6 to check: these are (0,1), (0,2), (0,2), (1,2), (1,3), (2,3), 

Answer 7

I got 100 out of 100 with this C ++ implementation:

 #include <map> #include <algorithm> inline bool mySortFunction(pair<int,int> p1, pair<int,int> p2) { return ( p1.first < p2.first ); } int number_of_disc_intersections ( const vector<int> &A ) { int i, size = A.size(); if ( size <= 1 ) return 0; // Compute lower boundary of all discs and sort them in ascending order vector< pair<int,int> > lowBounds(size); for(i=0; i<size; i++) lowBounds[i] = pair<int,int>(iA[i],i+A[i]); sort(lowBounds.begin(), lowBounds.end(), mySortFunction); // Browse discs int nbIntersect = 0; for(i=0; i<size; i++) { int curBound = lowBounds[i].second; for(int j=i+1; j<size && lowBounds[j].first<=curBound; j++) { nbIntersect++; // Maximal number of intersections if ( nbIntersect > 10000000 ) return -1; } } return nbIntersect; } 

Answer 8

Python answer

 from bisect import bisect_right def number_of_disc_intersections(li): pairs = 0 # treat as a series of intervals on the y axis at x=0 intervals = sorted( [(i-li[i], i+li[i]) for i in range(len(li))] ) # do this by creating a list of start points of each interval starts = [i[0] for i in intervals] for i in range(len(starts)): # find the index of the rightmost value less than or equal to the interval-end count = bisect_right(starts, intervals[i][1]) # subtract current position to exclude previous matches, and subtract self count -= (i+1) pairs += count if pairs > 10000000: return -1 return pairs 

Answer 9

Java 2 * 100%.

result declared for so long that the case code is not checked, namely 50k * 50k intersections at one point.

 class Solution { public int solution(int[] A) { int[] westEnding = new int[A.length]; int[] eastEnding = new int[A.length]; for (int i=0; i<A.length; i++) { if (iA[i]>=0) eastEnding[iA[i]]++; else eastEnding[0]++; if ((long)i+A[i]<A.length) westEnding[i+A[i]]++; else westEnding[A.length-1]++; } long result = 0; //long to contain the case of 50k*50k. codility doesn't test for this. int wests = 0; int easts = 0; for (int i=0; i<A.length; i++) { int balance = easts*wests; //these are calculated elsewhere wests++; easts+=eastEnding[i]; result += (long) easts*wests - balance - 1; // 1 stands for the self-intersection if (result>10000000) return -1; easts--; wests-= westEnding[i]; } return (int) result; } } 

Answer 10

 count = 0 for (int i = 0; i < N; i++) { for (int j = i+1; j < N; j++) { if (i + A[i] >= j - A[j]) count++; } } 

This O(N^2) so slow, but it works.

Answer 11

This is a ruby ​​solution, gaining 100/100 on the coding. I am sending it now because it is difficult for me to follow the already published ruby ​​answer.

 def solution(a) end_points = [] a.each_with_index do |ai, i| end_points << [i - ai, i + ai] end end_points = end_points.sort_by { |points| points[0]} intersecting_pairs = 0 end_points.each_with_index do |point, index| lep, hep = point pairs = bsearch(end_points, index, end_points.size - 1, hep) return -1 if 10000000 - pairs + index < intersecting_pairs intersecting_pairs += (pairs - index) end return intersecting_pairs end # This method returns the maximally appropriate position # where the higher end-point may have been inserted. def bsearch(a, l, u, x) if l == u if x >= a[u][0] return u else return l - 1 end end mid = (l + u)/2 # Notice that we are searching in higher range # even if we have found equality. if a[mid][0] <= x return bsearch(a, mid+1, u, x) else return bsearch(a, l, mid, x) end end 

Answer 12

100/100 C #

  class Solution { class Interval { public long Left; public long Right; } public int solution(int[] A) { if (A == null || A.Length < 1) { return 0; } var itervals = new Interval[A.Length]; for (int i = 0; i < A.Length; i++) { // use long to avoid data overflow (eg. int.MaxValue + 1) long radius = A[i]; itervals[i] = new Interval() { Left = i - radius, Right = i + radius }; } itervals = itervals.OrderBy(i => i.Left).ToArray(); int result = 0; for (int i = 0; i < itervals.Length; i++) { var right = itervals[i].Right; for (int j = i + 1; j < itervals.Length && itervals[j].Left <= right; j++) { result++; if (result > 10000000) { return -1; } } } return result; } } 

Answer 13

Probably very fast. ON). But you have to check it out. 100% on Codility. The main idea: 1. At any point on the table there are a number of circles "open" to the right edge of the circle, say "o". 2. Thus, there are (o-1-used) possible pairs for the circle at this point. "used" means the processed circle and the calculated pairs for them.

  public int solution(int[] A) { final int N = A.length; final int M = N + 2; int[] left = new int[M]; // values of nb of "left" edges of the circles in that point int[] sleft = new int[M]; // prefix sum of left[] int il, ir; // index of the "left" and of the "right" edge of the circle for (int i = 0; i < N; i++) { // counting left edges il = tl(i, A); left[il]++; } sleft[0] = left[0]; for (int i = 1; i < M; i++) {// counting prefix sums for future use sleft[i]=sleft[i-1]+left[i]; } int o, pairs, total_p = 0, total_used=0; for (int i = 0; i < N; i++) { // counting pairs ir = tr(i, A, M); o = sleft[ir]; // nb of open till right edge pairs = o -1 - total_used; total_used++; total_p += pairs; } if(total_p > 10000000){ total_p = -1; } return total_p; } private int tl(int i, int[] A){ int tl = i - A[i]; // index of "begin" of the circle if (tl < 0) { tl = 0; } else { tl = i - A[i] + 1; } return tl; } int tr(int i, int[] A, int M){ int tr; // index of "end" of the circle if (Integer.MAX_VALUE - i < A[i] || i + A[i] >= M - 1) { tr = M - 1; } else { tr = i + A[i] + 1; } return tr; } 

Answer 14

There are already many good answers here, including a great explanation from the accepted answer. However, I would like to mention a small remark about the details of the implementation in Python.

I originally came up with the solution shown below. I expected to get O(N*log(N)) time complexity as soon as we have one for loop with N iterations, and each iteration performs a binary search that takes no more than log(N) .

 def solution(a): import bisect if len(a) <= 1: return 0 cuts = [(c - r, c + r) for c, r in enumerate(a)] cuts.sort(key=lambda pair: pair[0]) lefts, rights = zip(*cuts) n = len(cuts) total = 0 for i in range(n): r = rights[i] pos = bisect.bisect_right(lefts[i+1:], r) total += pos if total > 10e6: return -1 return total 

However, I received O(N**2) and a timeout failure. You see what is wrong here? Right, this line:

 pos = bisect.bisect_right(lefts[i+1:], r) 

On this line, you actually take a copy of the original list to pass it to the binary search function, and this completely destroys the effectiveness of the proposed solution! This makes your code a little more convenient (i.e. you do not need to write pos - - 1 ), but greatly reduces performance. So, as shown above, the solution should be:

 def solution(a): import bisect if len(a) <= 1: return 0 cuts = [(c - r, c + r) for c, r in enumerate(a)] cuts.sort(key=lambda pair: pair[0]) lefts, rights = zip(*cuts) n = len(cuts) total = 0 for i in range(n): r = rights[i] pos = bisect.bisect_right(lefts, r) total += (pos - i - 1) if total > 10e6: return -1 return total 

It seems that sometimes it would be too difficult to make slices and copies, because Python allows you to do this very easily :) It may not be a good idea, but for me it was a good lesson to pay more attention to these "technical" points, when converting ideas and algorithms into real solutions.

Answer 15

Swift 4 Solution 100% (Codility does not check the worst case for this solution)

 public func solution(_ A : inout [Int]) -> Int { // write your code in Swift 4.2.1 (Linux) var count = 0 let sortedA = A.sorted(by: >) if sortedA.isEmpty{ return 0 } let maxVal = sortedA[0] for i in 0..<A.count{ let maxIndex = min(i + A[i] + maxVal + 1,A.count) for j in i + 1..<maxIndex{ if j - A[j] <= i + A[i]{ count += 1 } } if count > 10_000_000{ return -1 } } return count } 

Answer 16

It got 100/100 in C #

 class CodilityDemo3 { public static int GetIntersections(int[] A) { if (A == null) { return 0; } int size = A.Length; if (size <= 1) { return 0; } List<Line> lines = new List<Line>(); for (int i = 0; i < size; i++) { if (A[i] >= 0) { lines.Add(new Line(i - A[i], i + A[i])); } } lines.Sort(Line.CompareLines); size = lines.Count; int intersects = 0; for (int i = 0; i < size; i++) { Line ln1 = lines[i]; for (int j = i + 1; j < size; j++) { Line ln2 = lines[j]; if (ln2.YStart <= ln1.YEnd) { intersects += 1; if (intersects > 10000000) { return -1; } } else { break; } } } return intersects; } } public class Line { public Line(double ystart, double yend) { YStart = ystart; YEnd = yend; } public double YStart { get; set; } public double YEnd { get; set; } public static int CompareLines(Line line1, Line line2) { return (line1.YStart.CompareTo(line2.YStart)); } } 

}

Answer 17

Thanks Falk for a great idea! Here is a ruby ​​implementation that uses sparseness.

 def int(a) event = Hash.new{|h,k| h[k] = {:start => 0, :stop => 0}} a.each_index {|i| event[i - a[i]][:start] += 1 event[i + a[i]][:stop ] += 1 } sorted_events = (event.sort_by {|index, value| index}).map! {|n| n[1]} past_start = 0 intersect = 0 sorted_events.each {|e| intersect += e[:start] * (e[:start]-1) / 2 + e[:start] * past_start past_start += e[:start] past_start -= e[:stop] } return intersect end puts int [1,1] puts int [1,5,2,1,4,0] 

Answer 18

Here is the PHP code that scored 100 on coding:

 $sum=0; //One way of cloning the A: $start = array(); $end = array(); foreach ($A as $key=>$value) { $start[]=0; $end[]=0; } for ($i=0; $i<count($A); $i++) { if ($i<$A[$i]) $start[0]++; else $start[$i-$A[$i]]++; if ($i+$A[$i] >= count($A)) $end[count($A)-1]++; else $end[$i+$A[$i]]++; } $active=0; for ($i=0; $i<count($A);$i++) { $sum += $active*$start[$i]+($start[$i]*($start[$i]-1))/2; if ($sum>10000000) return -1; $active += $start[$i]-$end[$i]; } return $sum; 

However, I do not understand the logic. This is just the converted C ++ code on top. People, could you talk about what you are doing here, please?

Answer 19

 #include <stdio.h> #include <stdlib.h> void sortPairs(int bounds[], int len){ int i,j, temp; for(i=0;i<(len-1);i++){ for(j=i+1;j<len;j++){ if(bounds[i] > bounds[j]){ temp = bounds[i]; bounds[i] = bounds[j]; bounds[j] = temp; temp = bounds[i+len]; bounds[i+len] = bounds[j+len]; bounds[j+len] = temp; } } } } int adjacentPointPairsCount(int a[], int len){ int count=0,i,j; int *bounds; if(len<2) { goto toend; } bounds = malloc(sizeof(int)*len *2); for(i=0; i< len; i++){ bounds[i] = ia[i]; bounds[i+len] = i+a[i]; } sortPairs(bounds, len); for(i=0;i<len;i++){ int currentBound = bounds[i+len]; for(j=i+1;a[j]<=currentBound;j++){ if(count>100000){ count=-1; goto toend; } count++; } } toend: free(bounds); return count; } 

Answer 20

Implementation of the idea outlined in Java above:

 public class DiscIntersectionCount { public int number_of_disc_intersections(int[] A) { int[] leftPoints = new int[A.length]; for (int i = 0; i < A.length; i++) { leftPoints[i] = i - A[i]; } Arrays.sort(leftPoints); // System.out.println(Arrays.toString(leftPoints)); int count = 0; for (int i = 0; i < A.length - 1; i++) { int rpoint = A[i] + i; int rrank = getRank(leftPoints, rpoint); //if disk has sifnificant radius, exclude own self if (rpoint > i) rrank -= 1; int rank = rrank; // System.out.println(rpoint+" : "+rank); rank -= i; count += rank; } return count; } public int getRank(int A[], int num) { if (A==null || A.length == 0) return -1; int mid = A.length/2; while ((mid >= 0) && (mid < A.length)) { if (A[mid] == num) return mid; if ((mid == 0) && (A[mid] > num)) return -1; if ((mid == (A.length - 1)) && (A[mid] < num)) return A.length; if (A[mid] < num && A[mid + 1] >= num) return mid + 1; if (A[mid] > num && A[mid - 1] <= num) return mid - 1; if (A[mid] < num) mid = (mid + A.length)/2; else mid = (mid)/2; } return -1; } public static void main(String[] args) { DiscIntersectionCount d = new DiscIntersectionCount(); int[] A = //{1,5,2,1,4,0} //{0,0,0,0,0,0} // {1,1,2} {3} ; int count = d.number_of_disc_intersections(A); System.out.println(count); } } 

Answer 21

93% rating http://codility.com/demo/results/demoUWFUDS-6XY/ Only one test does not work why?

 // you can also use includes, for example: #include <algorithm> #include <map> inline bool mySortFunction(pair<int,int> p1, pair<int,int> p2) { return ( p1.first < p2.first ); } int solution ( const vector<int> &A ) { int i, size = A.size(); if ( size <= 1 ) return 0; // Compute lower boundary of all discs and sort them in ascending order vector< pair<int,int> > lowBounds(size); for(i=0; i<size; i++) lowBounds[i] = pair<int,int>(iA[i],i+A[i]); sort(lowBounds.begin(), lowBounds.end(), mySortFunction); // Browse discs long nbIntersect = 0; for(i=0; i<size; i++) { int curBound = lowBounds[i].second; for(int j=i+1; j<size && lowBounds[j].first<=curBound; j++) { nbIntersect++; // Maximal number of intersections if ( nbIntersect > 10000000 ) return -1; } } return nbIntersect; } 

I also tried to set a limit in case the size> 100000, and I lost the point in this case, so he did not understand what test they were doing to fail.

Answer 22

Implementing 100/100 C # as described by Aryabhatta (binary search solution).

 using System; class Solution { public int solution(int[] A) { return IntersectingDiscs.Execute(A); } } class IntersectingDiscs { public static int Execute(int[] data) { int counter = 0; var intervals = Interval.GetIntervals(data); Array.Sort(intervals); // sort by Left value for (int i = 0; i < intervals.Length; i++) { counter += GetCoverage(intervals, i); if(counter > 10000000) { return -1; } } return counter; } private static int GetCoverage(Interval[] intervals, int i) { var currentInterval = intervals[i]; // search for an interval starting at currentInterval.Right int j = Array.BinarySearch(intervals, new Interval { Left = currentInterval.Right }); if(j < 0) { // item not found j = ~j; // bitwise complement (see Array.BinarySearch documentation) // now j == index of the next item larger than the searched one j = j - 1; // set index to the previous element } while(j + 1 < intervals.Length && intervals[j].Left == intervals[j + 1].Left) { j++; // get the rightmost interval starting from currentInterval.Righ } return j - i; // reduce already processed intervals (the left side from currentInterval) } } class Interval : IComparable { public long Left { get; set; } public long Right { get; set; } // Implementation of IComparable interface // which is used by Array.Sort(). public int CompareTo(object obj) { // elements will be sorted by Left value var another = obj as Interval; if (this.Left < another.Left) { return -1; } if (this.Left > another.Left) { return 1; } return 0; } /// <summary> /// Transform array items into Intervals (eg. {1, 2, 4} -> {[-1,1], [-1,3], [-2,6]}). /// </summary> public static Interval[] GetIntervals(int[] data) { var intervals = new Interval[data.Length]; for (int i = 0; i < data.Length; i++) { // use long to avoid data overflow (eg. int.MaxValue + 1) long radius = data[i]; intervals[i] = new Interval { Left = i - radius, Right = i + radius }; } return intervals; } } 

Answer 23

100% points in Codility .

Below is the adaptation to C # Tolya :

  public int solution(int[] A) { long result = 0; Dictionary<long, int> dps = new Dictionary<long, int>(); Dictionary<long, int> dpe = new Dictionary<long, int>(); for (int i = 0; i < A.Length; i++) { Inc(dps, Math.Max(0, i - A[i])); Inc(dpe, Math.Min(A.Length - 1, i + A[i])); } long t = 0; for (int i = 0; i < A.Length; i++) { int value; if (dps.TryGetValue(i, out value)) { result += t * value; result += value * (value - 1) / 2; t += value; if (result > 10000000) return -1; } dpe.TryGetValue(i, out value); t -= value; } return (int)result; } private static void Inc(Dictionary<long, int> values, long index) { int value; values.TryGetValue(index, out value); values[index] = ++value; } 

Answer 24

Here's a two-pass solution in C ++ that does not require any libraries, binary search, sorting, etc.

 int solution(vector<int> &A) { #define countmax 10000000 int count = 0; // init lower edge array vector<int> E(A.size()); for (int i = 0; i < (int) E.size(); i++) E[i] = 0; // first pass // count all lower numbered discs inside this one // mark lower edge of each disc for (int i = 0; i < (int) A.size(); i++) { // if disc overlaps zero if (i - A[i] <= 0) count += i; // doesn't overlap zero else { count += A[i]; E[i - A[i]]++; } if (count > countmax) return -1; } // second pass // count higher numbered discs with edge inside this one for (int i = 0; i < (int) A.size(); i++) { // loop up inside this disc until top of vector int jend = ((int) E.size() < (long long) i + A[i] + 1 ? (int) E.size() : i + A[i] + 1); // count all discs with edge inside this disc // note: if higher disc is so big that edge is at or below // this disc center, would count intersection in first pass for (int j = i + 1; j < jend; j++) count += E[j]; if (count > countmax) return -1; } return count; } 

Answer 25

My answer is in Swift; gets 100% points.

 import Glibc struct Interval { let start: Int let end: Int } func bisectRight(intervals: [Interval], end: Int) -> Int { var pos = -1 var startpos = 0 var endpos = intervals.count - 1 if intervals.count == 1 { if intervals[0].start < end { return 1 } else { return 0 } } while true { let currentLength = endpos - startpos if currentLength == 1 { pos = startpos pos += 1 if intervals[pos].start <= end { pos += 1 } break } else { let middle = Int(ceil( Double((endpos - startpos)) / 2.0 )) let middlepos = startpos + middle if intervals[middlepos].start <= end { startpos = middlepos } else { endpos = middlepos } } } return pos } public func solution(inout A: [Int]) -> Int { let N = A.count var nIntersections = 0 // Create array of intervals var unsortedIntervals: [Interval] = [] for i in 0 ..< N { let interval = Interval(start: iA[i], end: i+A[i]) unsortedIntervals.append(interval) } // Sort array let intervals = unsortedIntervals.sort { $0.start < $1.start } for i in 0 ..< intervals.count { let end = intervals[i].end var count = bisectRight(intervals, end: end) count -= (i + 1) nIntersections += count if nIntersections > Int(10E6) { return -1 } } return nIntersections } 

Answer 26

Solution C # 100/100

 using System.Linq; class Solution { private struct Interval { public Interval(long @from, long to) { From = @from; To = to; } public long From { get; } public long To { get; } } public int solution(int[] A) { int result = 0; Interval[] intervals = A.Select((value, i) => { long iL = i; return new Interval(iL - value, iL + value); }) .OrderBy(x => x.From) .ToArray(); for (int i = 0; i < intervals.Length; i++) { for (int j = i + 1; j < intervals.Length && intervals[j].From <= intervals[i].To; j++) result++; if (result > 10000000) return -1; } return result; } } 

Answer 27

Ruby solution. Score 100%.

 def solution(a) # write your code in Ruby 2.2 open = Hash.new close = Hash.new (0..(a.length-1)).each do |c| r = a[c] open[ cr ] ? open[ cr ]+=1 : open[ cr ]=1 close[ c+r ] ? close[ c+r ]+=1 : close[ c+r ]=1 end open_now = 0 intersections = 0 open.merge(close).keys.sort.each do |v| intersections += (open[v]||0)*open_now open_now += (open[v]||0) - (close[v]||0) if(open[v]||0)>1 # sum the intersections of only newly open discs intersections += (open[v]*(open[v]-1))/2 return -1 if intersections > 10000000 end end intersections end 

Answer 28

# 100/100 O(N*log(N)) O(N) .

:

• 2 : .
• , true "", false "" .
• , .

_

 public int solution(int[] A) { var sortedStartPoints = A.Select((value, index) => (long)index-value).OrderBy(i => i).ToArray(); var sortedEndPoints = A.Select((value, index) => (long)index+value).OrderBy(i => i).ToArray(); // true - increment, false - decrement, null - stop var points = new bool?[2*A.Length]; // merge arrays for(int s=0, e=0, p=0; p < points.Length && s < sortedStartPoints.Length; p++) { long startPoint = sortedStartPoints[s]; long endPoint = sortedEndPoints[e]; if(startPoint <= endPoint) { points[p] = true; s++; } else { points[p] = false; e++; } } int result = 0; int opened = 0; // calculate intersections foreach(bool? p in points.TakeWhile(_ => _.HasValue)) { if(result > 10000000) return -1; if(p == true) { result += opened; opened++; } else { opened--; } } return result; } 

Answer 29

@Aryabhatta , @Aryabhatta

 fun calculateDiscIntersections(A: Array<Int>): Int { val MAX_PAIRS_ALLOWED = 10_000_000L //calculate startX and endX for each disc //as y is always 0 so we don't care about it. We only need X val ranges = Array(A.size) { i -> calculateXRange(i, A[i]) } //sort Xranges by the startX ranges.sortBy { range -> range.start } val starts = Array(ranges.size) {index -> ranges[index].start } var count = 0 for (i in 0 until ranges.size) { val checkRange = ranges[i] //find the right most disc whose start is less than or equal to end of current disc val index = bisectRight(starts, checkRange.endInclusive, i) //the number of discs covered by this disc are: //count(the next disc/range ... to the last disc/range covered by given disc/range) //example: given disc index = 3, last covered (by given disc) disc index = 5 //count = 5 - 3 = 2 //because there are only 2 discs covered by given disc // (immediate next disc with index 4 and last covered disc at index 5) val intersections = (index - i) //because we are only considering discs intersecting/covered by a given disc to the right side //and ignore any discs that are intersecting on left (because previous discs have already counted those // when checking for their right intersects) so this calculation avoids any duplications count += intersections if (count > MAX_PAIRS_ALLOWED) { return -1 } } return if (count > MAX_PAIRS_ALLOWED) { -1 } else { count } } private fun calculateXRange(x: Int, r: Int): LongRange { val minX = x - r.toLong() val maxX = x + r.toLong() return LongRange(minX, maxX) } fun bisectRight(array: Array<Long>, key: Long, arrayStart: Int = 0): Int { var start = arrayStart var end = array.size - 1 var bisect = start while (start <= end) { val mid = Math.ceil((start + end) / 2.0).toInt() val midValue = array[mid] val indexAfterMid = mid + 1 if (key >= midValue) { bisect = mid } if (key >= midValue && (indexAfterMid > end || key < array[indexAfterMid])) { break } else if (key < midValue) { end = mid - 1 } else { start = mid + 1 } } return bisect } 

Codility Solution 100% .

Answer 30

Python ( ). .

100% Codility - : O (Nlog (N)) - : O (N)

, .

 def solution(A): start, end = [], [] for i, val in enumerate(A): start.append(i-val) end.append(i+val) start.sort() end.sort() count, currCircles, aux1, aux2 = 0, 0, 0, 0 while aux1 != len(start) and aux2 != len(end): if aux1 < len(start) and start[aux1] <= end[aux2]: count += currCircles currCircles +=1 aux1 +=1 if currCircles > 10000000: return -1 else: currCircles -=1 aux2 +=1 return count