Algorithme pour calculer le nombre de disques en intersection

Étant donné un tableau A de N nombres entiers, nous dessinons N disques dans un plan 2D, de sorte que le i-ème disque a son centre dans (0,i) et un rayon A[i] . Nous disons que le k-ème disque et le j-ième disque se croisent, si les k-ème et j-e disques ont au moins un point commun.

Ecrire une fonction

 int number_of_disc_intersections(int[] A); 

qui donne un tableau A décrivant N disques comme expliqué ci-dessus, renvoie le nombre de paires de disques qui se croisent. Par exemple, étant donné N=6 et

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

il y a 11 paires de disques qui se croisent:

 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 

donc la fonction devrait renvoyer 11. La fonction devrait renvoyer -1 si le nombre de paires intersectées dépasse 10 000 000. La fonction peut supposer que N ne dépasse pas 10 000 000.

Donc, vous voulez trouver le nombre d’intersections des intervalles [iA[i], i+A[i]] .

Conservez un tableau sortingé (appelez-le X) contenant l’ iA[i] (également un espace supplémentaire qui a la valeur i+A[i] ).

Maintenant, parcourez le tableau X en commençant par l’intervalle le plus à gauche (c’est-à-dire le plus petit iA[i] ).

Pour l’intervalle actuel, effectuez une recherche binary pour voir où le point final de l’intervalle (c.-à-d. i+A[i] ) ira (appelé le rang). Maintenant, vous savez qu’il coupe tous les éléments à gauche.

Incrémenter un compteur avec le rang et soustraire la position actuelle (en supposant un indexé) car nous ne voulons pas doubler les intervalles de comptage et les auto-intersections.

O (nlogn) temps, O (n) espace.

O (N) complexité et solution de mémoire O (N).

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

Eh bien, j’ai adapté l’idée de Falk Hüffner au c ++, et j’ai modifié la gamme. Contrairement à ce qui est écrit ci-dessus, il n’est pas nécessaire d’aller au-delà de la scope du tableau (quelle que soit la taille des valeurs). Sur Codility, ce code a reçu 100%. Merci Falk pour ta bonne idée!

 int number_of_disc_intersections ( const vector &A ) { int sum=0; vector start(A.size(),0); vector end(A.size(),0); for (unsigned int i=0;i=A.size()) end[A.size()-1]++; else end[i+A[i]]++; } int active=0; for (unsigned int i=0;i10000000) return -1; active+=start[i]-end[i]; } return sum; } 

Cela peut même être fait en temps linéaire. En fait, cela devient plus facile si vous ignorez le fait qu’il existe exactement un intervalle centré sur chaque point et que vous le traitez simplement comme un ensemble de points de début et de fin d’intervalles. Vous pouvez alors simplement le scanner depuis la gauche (code Python pour plus de simplicité):

 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 

Voici un O (N) temps, un algorithme d’espace O (N) nécessitant 3 exécutions sur le tableau et aucun sorting, vérifié avec une évaluation de 100% :

Vous êtes intéressé par des paires de disques. Chaque paire implique un côté d’un disque et l’autre côté de l’autre disque. Par conséquent, nous n’aurons pas de paires en double si nous traitons un côté de chaque disque. Appelons les côtés droit et gauche (j’ai fait pivoter l’espace en y réfléchissant).

Un chevauchement est dû à un côté droit chevauchant un autre disque directement au centre (donc des paires égales au rayon avec une certaine attention à la longueur du réseau) ou au nombre de côtés gauche existant au bord le plus à droite.

Nous créons donc un tableau contenant le nombre de côtés gauche à chaque point, puis une simple sum.

Code C:

 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=i) { C[0]++; } else { C[ia]++; } } // Sum of left side of disks at location for (int i=0; i10000000) return -1; } return S; } 

Python 100/100 (testé) sur la codilité, avec heure O (nlogn) et espace O (n).

Voici l’implémentation de python @ noisyboiler de la méthode @ Aryabhatta avec des commentaires et un exemple. Crédit complet aux auteurs originaux, toute erreur / mauvaise formulation est entièrement de ma faute.

 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 

Exemple travaillé: étant donné que [3, 0, 1, 6] le rayon du disque ressemblerait à ceci:

 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), 

J’ai eu 100 sur 100 avec cette implémentation C ++:

 #include  #include  inline bool mySortFunction(pair p1, pair p2) { return ( p1.first < p2.first ); } int number_of_disc_intersections ( const vector &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 > lowBounds(size); for(i=0; i(iA[i],i+A[i]); sort(lowBounds.begin(), lowBounds.end(), mySortFunction); // Browse discs int nbIntersect = 0; for(i=0; i 10000000 ) return -1; } } return nbIntersect; } 

Une réponse Python

 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 

Java 2 * 100%.

result est déclaré long pour une casse non vérifiée, à savoir 50k * 50k intersections en un 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=0) eastEnding[iA[i]]++; else eastEnding[0]++; if ((long)i+A[i]10000000) return -1; easts--; wests-= westEnding[i]; } return (int) result; } } 
 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++; } } 

C’est O(N^2) donc assez lent, mais ça marche.

Ceci est une solution de rbuy qui a marqué 100/100 sur la codilité. Je le poste maintenant parce que j’ai du mal à suivre la réponse Ruby déjà affichée.

 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 

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

Cela a eu 100/100 en c #

 class CodilityDemo3 { public static int GetIntersections(int[] A) { if (A == null) { return 0; } int size = A.Length; if (size <= 1) { return 0; } List lines = new List(); 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)); } } 

}

Merci à Falk pour la bonne idée! Voici une mise en œuvre de rbuy qui profite de la rareté.

 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] 
 #include  #include  void sortPairs(int bounds[], int len){ int i,j, temp; for(i=0;i<(len-1);i++){ for(j=i+1;j 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;i100000){ count=-1; goto toend; } count++; } } toend: free(bounds); return count; } 

Une mise en œuvre de l’idée mentionnée ci-dessus en Java:

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

Voici le code PHP qui a marqué 100 sur la codilité:

 $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)) $end[count($A)-1]++; else $end[$i+$A[$i]]++; } $active=0; for ($i=0; $i10000000) return -1; $active += $start[$i]-$end[$i]; } return $sum; 

Cependant, je ne comprends pas la logique. Ceci est juste du code C ++ transformé par le haut. Les gars, pouvez-vous préciser ce que vous faisiez ici, s’il vous plaît?

93% score http://codility.com/demo/results/demoUWFUDS-6XY/ Un seul test ne fonctionne pas pourquoi?

 // you can also use includes, for example: #include  #include  inline bool mySortFunction(pair p1, pair p2) { return ( p1.first < p2.first ); } int solution ( const vector &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 > lowBounds(size); for(i=0; i(iA[i],i+A[i]); sort(lowBounds.begin(), lowBounds.end(), mySortFunction); // Browse discs long nbIntersect = 0; for(i=0; i 10000000 ) return -1; } } return nbIntersect; } 

J’ai essayé de mettre aussi une limite au cas où la taille est> 100000 et j’ai perdu le point dans ce cas donc il n’est pas clair quel est le test qu’ils échouent.

Une implémentation 100/100 C # décrite par Aryabhatta (la solution de recherche binary).

 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; } ///  /// Transform array items into Intervals (eg. {1, 2, 4} -> {[-1,1], [-1,3], [-2,6]}). ///  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; } } 

100% de score en codilité .

Voici une adaptation à la solution C # de Толя :

  public int solution(int[] A) { long result = 0; Dictionary dps = new Dictionary(); Dictionary dpe = new Dictionary(); 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 values, long index) { int value; values.TryGetValue(index, out value); values[index] = ++value; } 

Voici une solution C ++ en deux passes qui ne nécessite aucune bibliothèque, recherche binary, sorting, etc.

 int solution(vector &A) { #define countmax 10000000 int count = 0; // init lower edge array vector 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; } 

Ma réponse dans Swift; obtient un score de 100%.

 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 } 

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

Une solution de rbuy. Scores 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 

C # 100/100 avec la complexité temporelle O(N*log(N)) et la complexité de l’espace O(N) .

Les idées principales:

  1. Faites 2 tableaux sortingés: points de gauche et points de droite.
  2. Fusionner ces tableaux dans un tableau booléen où true signifie “ouvrir” et false signifie “fermer” un intervalle.
  3. Parcourez le tableau booléen et comptez les intervalles ouverts , résumez-les.

_

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

Probably extremely fast. O(N). But you need to check it out. 100% on Codility. Main idea: 1. At any point of the table, there are number of circles “opened” till the right edge of the circle, lets say “o”. 2. So there are (o-1-used) possible pairs for the circle in that point. “used” means circle that have been processed and pairs for them counted.

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

One for the copy-paste kids out there:

 function number_of_disc_intersections ( $A ) { $intersects = array(); $len = count($A); foreach($A as $i => $r ){ if( $r > 0 ){ $range = array(); if( $i > 0 ){ $range = range(max(0, $i-$r), max(0,$i-1)); } if( $i < $len ){ $range = array_merge( $range, range($i+1, min($len-1, $i+$r))); } foreach($range as $j){ $intersects[] = array(min($i,$j), max($i,$j)); } } if( count($intersects) > 100000000 ){ return -1; } } return array_unique($intersects, SORT_REGULAR); } 

You will get 100/100 for the below solution in Java language

 if (A == null || A.length < 2) { return 0; } int[] B = Arrays.copyOf(A, A.length); Arrays.sort(B); int biggest = B[A.length - 1]; int intersections = 0; for (int i = 0; i < A.length; i++) { for (int j = i + 1; j < A.length; j++) { if (j - biggest > i + A[i]) { break; } if (j - A[j] <= i + A[i]) { intersections++; } if (intersections > 10000000) { return -1; } } } return intersections; 

JavaScript 2016

JavaScript version of Aryabhattas. I’ve changed it a bit making it more JS and more efficient performance wise and also added comments to explain what the algorithm does. J’espère que cela t’aides.

 function solution(A) { var result = 0, len = A.length, dps = new Array(len).fill(0), dpe = new Array(len).fill(0), i, active = len - 1, s, e; for (i = 0; i < len; i++) { // adds to the begin array how many discs begin at the specific position given if (i > A[i]) s = i - A[i]; else s = 0; // adds to the end array the amount of discs that end at this specific position if (active - i > A[i]) e = i + A[i] else e = active; // a disc always begins and ends somewhere, s and e are the starting and ending positions where this specific disc for the element in A at position i reside dps[s] += 1; dpe[e] += 1; } // no discs are active as the algorithm must calculate the overlaps first, then the discs can be made active, hence why it begins with 0 active active = 0; for (i = 0; i < len; i++) { if (dps[i] > 0) { // new discs has entered the zone, multiply it with the current active discs as the new discs now overlap with the older active ones result += active * dps[i]; // new discs must also be counted against each other and not just the ones which were active prior result += dps[i] * (dps[i] - 1) / 2; // assignment rules if (10000000 < result) return -1; // add new discs to the active list that have started at this position active += dps[i]; } // remove discs as they have ended at this position active -= dpe[i]; } // return the result return result; } var A = [1, 5, 2, 1, 4, 0]; // should return 11 console.log(solution(A));