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

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 с #

  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 2

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

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 3

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

  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 4

Рубиновое решение. 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

Answer 5

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 6

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

Answer 7

Мой ответ в 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 {
        $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 8

Вы получите 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;

Answer 9

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

Answer 10

Здесь уже есть много хороших ответов, включая замечательное объяснение из принятого ответа. Тем не менее, я хотел бы отметить небольшое замечание о деталях реализации на языке Python.

Первоначально я придумал решение, показанное ниже. Я ожидал получить O(N*log(N)) сложность времени, как только у нас будет один цикл for с N итерациями, и каждая итерация выполняет двоичный поиск, который занимает максимум 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

Однако у меня O(N**2) и сбой тайм-аута. Вы видите, что здесь не так? Правильно, эта строка:

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

В этой строке вы на самом деле берете копию исходного списка, чтобы передать его в функцию бинарного поиска, и это полностью разрушает эффективность предложенного решения! Это делает ваш код немного более удобным (т. Е. Вам не нужно писать pos - i - 1), но сильно снижает производительность. Итак, как было показано выше, решение должно быть:

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

Кажется, что иногда было бы слишком жаль делать срезы и копии, потому что Python позволяет вам делать это так легко :) Возможно, это не очень хорошая идея, но для меня это был хороший урок, чтобы уделять больше внимания этим "техническим моменты при преобразовании идей и алгоритмов в решения на основе реальных слов.