Algorithme pour calculer le nombre de disques se croisant

Question

Ce qui suit a été le cadre d'un test en ligne, mais il a été retiré maintenant donc Im espérant que son ok pour poster ici. J'ai du mal avec la réponse, alors j'ai pensé que je demande à des gens intelligents sur StackOverflow. Toute langue est belle!

Étant donné un tableau de N entiers nous attirons N disques dans un plan 2D, tels que la i-ème disque de centre (0,i) et un rayon d'Un[i]. Nous disons que la k-ième disque et de la j-ème disque se croisent, s'

et k-ième et la j-ème disques ont au moins un point commun.

Écrire une fonction

int number_of_disc_intersections(int[] A);

qui étant donné un tableau décrivant Un N disques comme expliqué ci-dessus, renvoie le nombre de paires de l'intersection de disques. Par exemple, pour 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 l'intersection de disques: 0e et 1er 0e et 2ème 0e et 4ème 1ère et 2ème Les 1er et 3ème Le 1er et le 4ème 1er et le 5ème 2e et 3e Le 2ème et le 4ème 3ème et 4ème 4ème et 5ème

donc la fonction est de retour 11. La fonction doit retourner -1 si le nombre de croisement des paires dépasse de 10 000 000. La fonction peut supposer que N ne dépasse pas 10 000 000 de.

Quelqu'un capable de m'aider à sortir de cette s'il vous plaît?

Answer 1

Complexité O (N) et solution 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; i < a.Length; i++)
    {
        dps[Math.Max(0, i - a[i])]++;
        dpe[Math.Min(a.Length - 1, i + a[i])]++;
    }

    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;
            t += dps[i];
        }
        t -= dpe[i];
    }

    return result;
}
 

Answer 2

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

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

Answer 3

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épart et d’intervalle. Vous pouvez ensuite simplement le scanner à partir de la gauche (code Python par souci 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
 

Answer 4

Python 100/100 (testé) sur la codilité, avec le temps O (nlogn) et l’espace O (n).

Voici l'implémentation en python de la méthode de @ Aryabhatta par @ noisyboiler avec des commentaires et un exemple. Crédits 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( [(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
 

Exemple travaillé: étant donné [3, 0, 1, 6], les rayons du disque ressemblent à 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),