Алгоритм вычисления числа пересекающихся дисков

O(N) сложность и 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;
}

Ну, я адаптировал идею Фалька Хюффнера к c++ и внес изменения в диапазон. В отличие от того, что написано выше, нет необходимости выходить за рамки массива (независимо от того, насколько велики значения в нем). На Codility этот код получил 100%. Спасибо Фальк за вашу замечательную идею!

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[i-A[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;
}

Это можно сделать даже в линейном времени. Фактически, становится легче, если вы игнорируете тот факт, что в каждой точке есть ровно один интервал, и просто рассматриваете его как набор начальных и конечных точек интервалов. Затем вы можете просто сканировать его слева (код Python для простоты):

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

здесь O (N) времени O (N) космический алгоритм, требующий 3 работает через массив и без сортировки, проверенный скоринг 100%:

вас интересуют пары дисков. Каждая пара включает в себя одну сторону одного диска и другую сторону другого диска. Поэтому у нас не будет повторяющихся пар, если мы будем обрабатывать одну сторону каждого диска. Давайте назовем стороны справа и слева (я повернул пространство, думая об этом).

дублирование либо из-за правой стороны, перекрывающей другой диск непосредственно в центре (поэтому пары равны радиусу с некоторой заботой о длине массива), либо из-за количества левых сторон, существующих на самом правом краю.

Итак, мы создаем массив, который содержит количество левых сторон в каждой точке, а затем это простая сумма.

код 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<N; i++) {
        C[i] = -1;
        a = A[i];
        if (a>=i) {
            C[0]++;
        } else {
            C[i-a]++;
        }
    }
    // 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<N-i) ? a: N-i-1);
        if (i != N-1) {
          S += C[((a<N-i) ? i+a: N-1)];
        }
        if (S>10000000) return -1;
    }
    return S;
}

Python 100 / 100 (проверено) на кодируемость, с O(nlogn) временем и o(n) пространством.

вот реализация python @noisyboiler метода @Aryabhatta с комментариями и примером. Полный кредит оригинальным авторам, любые ошибки / плохие формулировки полностью моя вина.

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( [(i-A[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

рабочий пример: учитывая [3, 0, 1, 6] радиусы диска будут выглядеть так:

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

Я получил 100 из 100 с этой реализацией C++:

#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>(i-A[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;
}

ответ питона

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 объявляется до тех пор, пока кодируемость случая не проверяется, а именно 50k*50k пересечений в одной точке.

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 (i-A[i]>=0) eastEnding[i-A[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;
    }
}

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

Это O(N^2) Так что довольно медленно, но это работает.

Это решение на Ruby, который набрал 100/100 на codility. Я отправляю его сейчас, потому что мне трудно следовать уже опубликованному ответу ruby.

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

Это получил 100/100 в 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));

    }
}

}

спасибо Фальку за отличную идею! Вот реализация ruby, которая использует разреженность.

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 <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] = i-a[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;   
}

реализация идеи, изложенной выше в 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);
}
}

вот PHP-код, который набрал 100 на codility:

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

однако я не понимаю логики. Это просто преобразованный код C++ сверху. Ребята, не могли бы вы подробнее рассказать, что вы здесь делали, пожалуйста?

93% результат http://codility.com/demo/results/demoUWFUDS-6XY/ только один тест не работает почему?

// 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>(i-A[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;
}

Я попытался поставить также ограничение в случае, если размер >100000, и я потерял точку в этом случае, поэтому неясно, какой тест они делают, чтобы потерпеть неудачу.

реализация 100/100 C#, как описано Aryabhatta (решение для двоичного поиска).

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

100% результат в Codility.

вот адаптация к C# из Толярешение:

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

вот двухпроходное решение C++, которое не требует никаких библиотек, двоичного поиска, сортировки и т. д.

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

мой ответ в Swift; получает 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: i-A[i], end: i+A[i])
        unsortedIntervals.append(interval)
    }

    // Sort array
    let intervals = unsortedIntervals.sort {
        .start < .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
}

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

решение Руби. Баллы 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[ c-r ]  ? open[ c-r ]+=1  : open[ c-r ]=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 С O(N*log(N)) сложность и O(N) сложность пространства.

основные идеи:

1. сделайте 2 отсортированных массива: левые точки и правые точки.
2. объединить эти массивы в один логический массив, где true означает "открытие" и false означает "закрытие" интервал.
3. выполнить через логический массив и count открыл интервалы, суммируйте их.

_

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

наверное, очень быстро. O (N). Но вы должны это проверить. 100% на Codility. Основная идея: 1. В любой точке таблицы есть количество кругов, " открытых "до правого края круга, скажем,"o". 2. Таким образом, существуют (O-1-used) возможные пары для круга в этой точке. "использованный" означает круг, который был обработан и пары для них подсчитаны.

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

один для копирования-вставки детей там:

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

вы получите 100/100 для приведенного ниже решения на языке Java

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 версия Aryabhattas. Я немного изменил его, сделав его более JS и более эффективной производительностью, а также добавил комментарии, чтобы объяснить, что делает алгоритм. Надеюсь, это поможет.

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