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

Question

Учитывая массив A из N целых чисел, мы рисуем N диски в 2D-плоскости, так что i-й диск имеет центр в (0,i) и радиус A[i].Мы говорим, что k-й диск и j-й диск пересекаются, если k-й и j-й диски имеют хотя бы одну общую точку.

Напишите функцию

int number_of_disc_intersections(int[] A);

, которая с массивом A, описывающим диски N, как описано выше, возвращает количество пар пересекающихся дисков.Например, для N=6 и

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

существует 11 пар пересекающихся дисков:

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

, поэтому функция должна возвращать 11. Функция должна возвращать -1, если числопересекающихся пар превышает 10 000 000.Функция может предполагать, что N не превышает 10 000 000.

Answer 1

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

    }
}

}

Answer 2

Спасибо Фальку за отличную идею!Вот реализация 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]

Answer 3

Ниже приведена реализация принятого ответа @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 4

Вот код PHP, который набрал 100 баллов по кодируемости:

$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 ++ сверху.Ребята, не могли бы вы рассказать, что вы здесь делали, пожалуйста?

Answer 5

C # 100/100 с O(N*log(N)) сложностью времени и O(N) сложностью пространства.

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

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

_

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 6

100% баллов в Кодируемость .

Вот адаптация к 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;
    }

Answer 7

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

Answer 8

Решение Swift 4 100% (Codility не проверяют наихудший случай для этого решения)

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 9

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

Answer 10

Вот мое чистое решение на 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