Tâche

Vous recevrez un ensemble de cercles dans le plan avec leurs centres sur la ligne y = 0 . Il est garanti qu'aucune paire de cercles n'a plus d'un point commun.

Votre tâche consiste à déterminer le nombre de régions dans lesquelles les cercles divisent le plan. Une région est un ensemble de points contigus à inclusion maximale ne coupant aucun des cercles.

Vous devez écrire un programme qui calcule cette réponse lorsque vous recevez une description des cercles.

Voici un exemple:

Sur le côté gauche, vous voyez les cercles dessinés dans l'avion. Cependant, dans la moitié droite de l'image, les régions produites par les cercles sont colorées distinctement (une couleur par région). Il y a six régions dans cet exemple.

Contribution

La première ligne de l'entrée contient un nombre N, le nombre de descriptions de cercle à suivre. Cette ligne est facultative, si votre solution fonctionne sans elle, c'est très bien.

Les Nlignes suivantes contiennent chacune deux entiers, x _i et r _i > 0 , représentant un cercle de centre (x _i , 0) et de rayon r _i .

Il est garanti qu'aucune paire de cercles n'a plus d'un point commun. Il est en outre garanti que x _i et r _i ne dépassent pas 10^9en valeur absolue (ils s'intègrent donc confortablement dans un entier 32 bits).

L'entrée peut être:

• lire de STDIN

• lire à partir d'un fichier nommé Idans le répertoire courant

Alternativement, l'entrée pourrait être:

• disponible sous forme de chaîne (y compris les sauts de ligne) dans une variable globale

• sur la pile

Sortie

Il doit s'agir d'un seul entier, le nombre de régions produites. Cela doit être écrit dans STDOUT ou dans un fichier nommé Odans le répertoire courant.

Règles

• Le code le plus court en octets gagne

• +200 octets de pénalité si votre code n'a pas de polynôme d'exécution + complexité spatiale dans n

• Bonus de -100 octets pour le pire cas d'exécution attendu + complexité de l'espace O(n log n)

• Bonus de -50 octets pour le pire cas d'exécution attendu + complexité de l'espace O(n)

• Bonus de -100 octets pour une exécution déterministe + complexité de l'espace O(n)

Lors de l'évaluation de l'exécution:

• Supposons que les tables de hachage aient un O(1)temps d'exécution prévu pour l'insertion, la suppression et la recherche, quelle que soit la séquence d'opérations et les données d'entrée. Cela peut être vrai ou non, selon que l'implémentation utilise la randomisation.

• Supposons que le tri intégré de votre langage de programmation prenne un O(n log n)temps déterministe , où nest la taille de la séquence d'entrée.

• Supposons que les opérations arithmétiques sur les nombres saisis ne prennent que du O(1)temps.

• Ne présumez pas que les nombres saisis sont liés par une constante, bien que, pour des raisons pratiques, ils le soient. Cela signifie que les algorithmes comme le tri par radix ou le tri par comptage ne sont pas du temps linéaire. En général, les très grands facteurs constants doivent être évités.

Exemples

Contribution:

2 
1 3
5 1

Sortie: 3

Contribution:

3
2 2
1 1
3 1

Sortie: 5

4
7 5
-9 11
11 9
0 20

Contribution:

9
38 14
-60 40
73 19
0 100
98 2
-15 5
39 15
-38 62
94 2

Sortie: 11

Astuces

Nous pouvons utiliser l'idée suivante pour une solution très compacte. Permet d'intersecter l'ensemble des cercles avec l'axe X et d'interpréter les points d'intersection comme des nœuds dans un graphique plan:

Chaque cercle produit exactement 2 arêtes dans ce graphique et jusqu'à deux nœuds. Nous pouvons compter le nombre de nœuds en utilisant une table de hachage pour garder une trace du nombre total de bordures gauche ou droite distinctes.

Ensuite, nous pouvons utiliser la formule caractéristique d'Euler pour calculer le nombre de faces d'un dessin du graphique:

V - E + F - C = 1

F = E - V + C + 1

Pour calculer Cle nombre de composants connectés, nous pouvons utiliser une recherche en profondeur d'abord .

^{Remarque: Cette idée de problème est empruntée à un récent concours de programmation croate , mais ne trichez pas en regardant les contours de la solution. :)}

Mathematica, 125 122 - 150 = -28 caractères

Je ne connais pas la complexité de la fonction intégrée ConnectedComponents.

1+{-1,2,1}.Length/@{VertexList@#,EdgeList@#,ConnectedComponents@#}&@Graph[(+##)<->(#-#2)&@@@Rest@ImportString[#,"Table"]]&

Usage:

1+{-1,2,1}.Length/@{VertexList@#,EdgeList@#,ConnectedComponents@#}&@Graph[(+##)<->(#-#2)&@@@Rest@ImportString[#,"Table"]]&[
"9
38 14
-60 40
73 19
0 100
98 2
-15 5
39 15
-38 62
94 2"]

11

Rubis - 312 306 285 273 269 259 caractères

Cette réponse a été remplacée par mon autre approche qui utilise beaucoup moins de caractères et s'exécute O(n log n).

Okay allons-y. Pour commencer, je voulais juste une implémentation fonctionnelle, donc ce n'est pas encore optimisé algorithmiquement. Je trie les cercles du plus grand au plus petit et je construis un arbre (les cercles inclus dans les autres cercles sont les enfants de ces plus grands). Les deux opérations prennent O(n^2)au pire et O(n log n)au mieux. Ensuite, je parcourt l'arbre pour compter les zones. Si les enfants d'un cercle remplissent tout son diamètre, il y a deux nouvelles zones, sinon il n'y en a qu'une. Cette itération prend O(n). J'ai donc une complexité globale O(n^2)et je n'ai droit ni à une récompense ni à une pénalité.

Ce code attend que l'entrée sans le nombre de cercles soit stockée dans une variable s:

t=[]
s.lines.map{|x|x,r=x.split.map &:to_i;{d:2*r,l:x-r,c:[]}}.sort_by!{|c|-c[:d]}.map{|c|i=-1;n=t
while o=n[i+=1]
if 0>d=c[:l]-o[:l]
break
elsif o[:d]>d
n=o[:c]
i=-1
end
end
n[i,0]=c}
a=1
t.map &(b=->n{d=0
n[:c].each{|c|d+=c[:d]}.map &b
a+=d==n[:d]?2:1})
p a

Version non golfée (attend l'entrée en variable string):

list = []
string.split("\n").map { |x|
  m = x.split
  x,radius = m.map &:to_i
  list<<{x:x, d:2*radius, l:x-radius, r:x+radius, children:[]}
}
list.sort_by! { |circle| -circle[:d] }
tree = []
list.map { |circle|
  i = -1
  node = tree
  while c=node[i+=1]
    if circle[:x]<c[:l]
      break
    elsif circle[:x]<c[:r]
      node = c[:children]
      i = -1
    end
  end
  node[i,0] = circle
}
areas = 1
tree.map &(count = -> node {
  d = 0
  i = -1
  while c=node[:children][i+=1]
    count.call c
    d += c[:d]
  end
  areas += d == node[:d] ? 2 : 1
})
p areas

Ruby, 203 183 173 133 - 100 = 33 caractères

Voici donc une approche différente. Cette fois, je trie les cercles par leur point le plus à gauche. Les cercles se touchant à leur point le plus à gauche sont triés du plus grand au plus petit. Cela prend O(n log n)(enfin, Ruby utilise le tri rapide, donc en fait, O(n^2)mais l'implémentation du tri par fusion / segment de mémoire dépasse probablement la portée de ce défi). Ensuite, j'itère cette liste en me souvenant de toutes les positions les plus à gauche et à droite des cercles que j'ai visités. Cela me permet de détecter si une série de cercles se connecte tout au long d'un cercle plus grand englobant. Dans ce cas, il existe deux sous-zones, sinon une seule. Cette itération ne prend que O(n)donner une complexité totale O(n log n)qui se qualifie pour la récompense de 100 caractères.

Cet extrait s'attend à ce que l'entrée soit fournie via un fichier dans les arguments de ligne de commande sans le nombre de cercles:

l,r={},{}
a=1
$<.map{|x|c,q=x.split.map &:to_r;[c-q,-2*q]}.sort.map{|x,y|a+=r[y=x-y]&&l[x]?2:1
l[y]=1 if l[x]&&!r[y]
l[x]=r[y]=1}
p a

Version non golfée (attend l'entrée dans une variable string):

list = []
string.split("\n").map { |x|
  m = x.split
  x,radius = m.map &:to_r
  list<<{x:x, d:2*radius, l:x-radius, r:x+radius}
}
list.sort_by! { |circle| circle[:l] + 1/circle[:d] }
l,r={},{}
areas = 1
list.map { |circle|
  x,y=circle[:l],circle[:r]
  if l[x] && r[y]
    areas += 2
  else
    areas += 1
    l[y]=1 if l[x]
  end
  r[y]=1
  l[x]=1
}
p areas

Julia - 260-100 (bonus?) = 160

En interprétant les cercles comme des figures avec des sommets (intersections), des arêtes et des faces (zones du plan), nous pouvons nous relier les uns aux autres en utilisant la caractéristique d'Euler , nous avons donc seulement besoin de connaître le nombre de "sommets" et "arêtes" pour avoir le nombre de "faces" ou régions du plan avec la formule écrite ci-dessous:

MISE À JOUR: En réfléchissant un moment, j'ai compris que le problème avec ma méthode n'était que lorsque les cercles n'étaient pas connectés, alors j'ai eu une idée, pourquoi ne pas les connecter artificiellement? Le tout satisfera donc la formule d'Euler.

F = 2 + EV (V = 6, E = 9)

[Ne pas travailler avec des cercles imbriqués, donc ce n'est pas une réponse au problème pour les cas généraux]

Code :

s=readlines(open("s"))
n=int(s[1])
c=zeros(n,2)
t=[]
for i=1:n
    a=int(split(s[i+1]))
    c[i,1]=a[1]-a[2]
    c[i,2]=a[1]+a[2]
    if i==1 t=[c[1]]end
    append!(t,[c[i,1]:.5:c[i,2]])
end
e=0
t=sort(t)
for i in 1:(length(t)-1) e+=t[i+1]-t[i]>=1?1:0end #adds one edge for every gap
2+2n+e-length(unique(c)) # 2+E-V = 2+(2n+e)-#vertices

Spidermonkey JS, 308, 287 , 273 - 100 = 173

Je pense que si je réécrivais cela en Ruby ou Python, je pourrais enregistrer des caractères.

Code:

for(a=[d=readline],e={},u=d(n=1);u--;)[r,q]=d().split(' '),l=r-q,r-=-q,e[l]=e[l]||[0,0],e[r]=e[r]||[0,0],e[r][1]++,e[l][0]++
for(k=Object.keys(e).sort(function(a,b)b-a);i=k.pop();a.length&&a.pop()&a.push(0)){for([l,r]=e[i];r--;)n+=a.pop()
for(n+=l;l--;)a.push(l>0)}print(n)

Algorithme:

n = 1 // this will be the total
e = {x:[numLeftBounds,numRightBounds]} // imagine this as the x axis with a count of zero-crossings
a = [] // this is the stack of circles around the "cursor".  
       // values will be 1 if that circle's never had alone time, else 0
k = sort keys of e on x
for each key in k: // this is the "cursor"
  n += key[numLeftBounds] // each circle that opens has at least one space.
  k[numRightBounds].times {n += a.pop()} // pop the closing circles. if any were never alone, add 1
  k[numLeftBounds].times {a.push(alwaysAlone)} // push the opening circles
  if !a.empty():
     set the innermost circle (top of stack) to false (not never alone)
  fi
loop

Je ne suis pas terriblement doué pour la notation O, mais je pense que c'est O (n) car je boucle effectivement dans chaque cercle 3 fois (création, gauche, droite) et trie également les clés de la carte (et je trie pour O ( n log n) mais qui disparaît). Est-ce déterministe?

JavaScript (ES6) - 255 254 Caractères - 100 250 Bonus = 155 4

R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Suppose que la chaîne d'entrée se trouve dans la variable Set renvoie le nombre de régions à la console.

R=/(\S+) (\S+)/ym;                  // Regular expression to find centre and width.
N=1;                                // Number of regions
w=l=0;                              // Maximum width and minimum left boundary.
X=[];                               // A 1-indexed array to contain the circles.
                                    // All the above are O(1)
for(;m=R.exec(S);){                 // For each circle
    X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};
                                    // Create an object with w (width), l (left boundary)
                                    // and r (right boundary) attributes.
    l=k<l?k:l;                      // Update the minimum left boundary.
    w=j<w?w:j                       // Update the maximum width.
}                                   // O(1) per iteration = O(N) total.
M=[];                               // An array.
X.map(x=>M[(x.l-l+1)*w-x.w]=x);     // Map the 1-indexed array of circles (X) to a
                                    // sparse array indexed so that the elements are
                                    // sorted by ascending left boundary then descending
                                    // width.
                                    // If there are N circles then only N elements are
                                    // created in the array and it can be treated as if it
                                    // is a hashmap (associative array) with a built in
                                    // ordering and as per the rules set in the question
                                    // is O(1) per insert so is O(N) total cost.
                                    // Since the array is sparse then it is still O(N)
                                    // total memory.
s=[];                               // An empty stack
i=0;                                // The number of circles on the stack.
M.map(x=>{                          // Loop through each circle
    while(i&&s[i-1][1]<x[1])        // Check to see if the current circle  is to the right
                                    // of the circles on the stack;
      N+=s[--i][0]?0:1;             // if so, decrement the length of the stack and if the
                                    // circle that pops off has radius equal to the total
                                    // radii of its children then increment the number of
                                    // regions by 1.

                                    // Since there can be at most N items on the stack then
                                    // there can be at most N items popped off the stack
                                    // over all the iterations; therefore this operation
                                    // has an O(N) total cost.
    i&&(s[i-1][0]-=x[0]);           // If there is a circle on the stack then this circle
                                    // is its child. Decrement the parent's radius by the
                                    // current child's radius.
                                    // O(1) per iteration
    s[i++]=x                        // Add the current circle to the stack.
  });
while(i)N+=s[--i][0]?0:1            // Finally, remove all the remaining circles from the
                                    // stack and if the circle that pops off has radius
                                    // equal to the total radii of its children then
                                    // increment the number of regions by 1.
                                    // Since there will always be at least one circle on the
                                    // stack then this has the added bonus of being the final
                                    // command so the value of N is printed to the console.
                                    // As per the previous comment on the complexity, there
                                    // can be at most N items on the stack so between this
                                    // and the iterations over the circles then there can only
                                    // be N items popped off the stack so the complexity of
                                    // all these tests on the circles on the stack is O(N).

La complexité temporelle est maintenant O (N).

Cas de test 1

S='2\n1 3\n5 1';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Les sorties: 3

Cas de test 2

S='3\n2 2\n1 1\n3 1';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Les sorties: 5

Cas de test 3

S='4\n7 5\n-9 11\n11 9\n0 20';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Les sorties: 6

Cas de test 4

S='9\n38 14\n-60 40\n73 19\n0 100\n98 2\n-15 5\n39 15\n-38 62\n94 2';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Les sorties: 11

Cas de test 5

S='87\n-730 4\n-836 2\n-889 1\n-913 15\n-883 5\n-908 8\n-507 77\n-922 2\n-786 2\n-782 2\n-762 22\n-776 2\n-781 3\n-913 3\n-830 2\n-756 4\n-970 30\n-755 5\n-494 506\n-854 4\n15 3\n-914 2\n-840 2\n-833 1\n-505 75\n-888 10\n-856 2\n-503 73\n-745 3\n-903 25\n-897 1\n-896 2\n-848 10\n-878 50\n-864 2\n0 1000\n-934 6\n-792 4\n-271 153\n-917 1\n-891 3\n-833 107\n-847 3\n-758 2\n-754 2\n-892 2\n-738 2\n-876 2\n-52 64\n-882 2\n-270 154\n-763 3\n-868 72\n-846 4\n-427 3\n-771 3\n-767 17\n-852 2\n-765 1\n-772 6\n-831 1\n-582 2\n-910 6\n-772 12\n-764 2\n-907 9\n-909 7\n-578 2\n-872 2\n-848 2\n-528 412\n-731 3\n-879 1\n-862 4\n-909 1\n16 4\n-779 1\n-654 68\n510 490\n-921 3\n-773 5\n-653 69\n-926 2\n-737 3\n-919 1\n-841 1\n-863 3';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Les sorties: 105

La version précédente

C=S.split('\n');N=1+C.shift()*1;s=[];C.map(x=>x.split(' ')).map(x=>[w=x[1]*1,x[i=0]*1+w]).sort((a,b)=>(c=a[1]-2*a[0])==(d=b[1]-2*b[0])?b[0]-a[0]:c-d).map(x=>{while(i&&s[i-1][1]<x[1])N+=s[--i][0]?0:1;i&&(s[i-1][0]-=x[0]);s[i++]=x});while(i)N+=s[--i][0]?0:1

Avec commentaires:

C=S.split('\n');                    // Split the input into an array on the newlines.
                                    // O(N)
N=1+C.shift()*1;                    // Remove the head of the array and store the value as
                                    // if there are N disjoint circles then there will be
                                    // N+1 regions.
                                    // At worst O(N) depending on how .shift() works.
s=[];                               // Initialise an empty stack.
                                    // O(1)
C .map(x=>x.split(' '))             // Split each line into an array of the two values.
                                    // O(1) per line = O(N) total.
  .map(x=>[w=x[1]*1,x[i=0]*1+w])    // Re-map the split values to an array storing the
                                    // radius and the right boundary.
                                    // O(1) per line = O(N) total.

  .sort((a,b)=>(c=a[1]-2*a[0])==(d=b[1]-2*b[0])?b[0]-a[0]:c-d)
                                    // Sort the circles on increasing left boundary and
                                    // then descending radius.
                                    // O(1) per comparison = O(N.log(N)) total.
  .map(x=>{                         // Loop through each circle
    while(i&&s[i-1][1]<x[1])        // Check to see if the current circle  is to the right
                                    // of the circles on the stack;
      N+=s[--i][0]?0:1;             // if so, decrement the length of the stack and if the
                                    // circle that pops off has radius equal to the total
                                    // radii of its children then increment the number of
                                    // regions by 1.

                                    // Since there can be at most N items on the stack then
                                    // there can be at most N items popped off the stack
                                    // over all the iterations; therefore this operation
                                    // has an O(N) total cost.
    i&&(s[i-1][0]-=x[0]);           // If there is a circle on the stack then this circle
                                    // is its child. Decrement the parent's radius by the
                                    // current child's radius.
                                    // O(1) per iteration
    s[i++]=x                        // Add the current circle to the stack.
  });
while(i)N+=s[--i][0]?0:1            // Finally, remove all the remaining circles from the
                                    // stack and if the circle that pops off has radius
                                    // equal to the total radii of its children then
                                    // increment the number of regions by 1.
                                    // Since there will always be at least one circle on the
                                    // stack then this has the added bonus of being the final
                                    // command so the value of N is printed to the console.
                                    // As per the previous comment on the complexity, there
                                    // can be at most N items on the stack so between this
                                    // and the iterations over the circles then there can only
                                    // be N items popped off the stack so the complexity of
                                    // all these tests on the circles on the stack is O(N).

La complexité temporelle totale est O (N) pour tout sauf le tri qui est O (N.log (N)) - cependant en le remplaçant par un tri par compartiment, cela réduira la complexité totale à O (N).

La mémoire requise est O (N).

Devinez ce qui est le prochain sur ma liste de tâches ... trier en moins de 150 caractères.Terminé