Tarea

Se le dará un conjunto de círculos en el plano con sus centros en la línea y = 0 . Se garantiza que ningún par de círculos tiene más de un punto común.

Su tarea es determinar en cuántas regiones se dividen los círculos en el plano. Una región es un conjunto contiguo de puntos de inclusión máxima que no se cruza con ninguno de los círculos.

Debería escribir un programa que calcule esta respuesta cuando se le dé una descripción de los círculos.

Aquí hay un ejemplo:

En el lado izquierdo ves los círculos dibujados en el avión. Sin embargo, en la mitad derecha de la imagen, las regiones producidas por los círculos tienen un color distinto (un color por región). Hay seis regiones en este ejemplo.

Entrada

La primera línea de la entrada contiene un número N, el número de descripciones de círculo a seguir. Esta línea es opcional, si su solución funciona sin ella, está bien.

NCada una de las siguientes líneas contiene dos enteros, x _i y r _i > 0 , que representan un círculo con centro (x _i , 0) y radio r _i .

Se garantiza que ningún par de círculos tiene más de un punto común. Además, se garantiza que x _i y r _i no exceden 10^9en valor absoluto (por lo que caben cómodamente en un entero de 32 bits).

La entrada puede ser:

• leer de STDIN

• leer desde un archivo nombrado Ien el directorio actual

Alternativamente, la entrada podría ser:

• disponible como una cadena (incluidas las nuevas líneas) en una variable global

• en la pila

Salida

Debe ser un número entero único, el número de regiones producidas. Esto debe escribirse en STDOUT o en un archivo nombrado Oen el directorio actual.

Reglas

• El código más corto en bytes gana

• Penalización de +200 bytes si su código no tiene un polinomio de tiempo de ejecución + complejidad espacial en n

• -Bono de 100 bytes para el peor tiempo de ejecución esperado + complejidad espacial O(n log n)

• -50 bono de bonificación para el peor tiempo de ejecución esperado + complejidad espacial O(n)

• -Bono de 100 bytes para tiempo de ejecución determinista + complejidad espacial O(n)

Mientras evalúa el tiempo de ejecución:

• Suponga que las tablas hash tienen O(1)tiempo de ejecución esperado para insertar, eliminar y buscar, independientemente de la secuencia de operaciones y los datos de entrada. Esto puede o no ser cierto, dependiendo de si la implementación utiliza la aleatorización.

• Suponga que el tipo de lenguaje de programación incorporado requiere O(n log n)tiempo determinista , donde nestá el tamaño de la secuencia de entrada.

• Suponga que las operaciones aritméticas en números de entrada toman solo O(1)tiempo.

• No asuma que los números de entrada están unidos por una constante, aunque, por razones prácticas, lo están. Esto significa que los algoritmos como la clasificación por radix o la clasificación por conteo no son de tiempo lineal. En general, se deben evitar factores constantes muy grandes.

Ejemplos

Entrada:

2 
1 3
5 1

Salida: 3

Entrada:

3
2 2
1 1
3 1

Salida: 5

4
7 5
-9 11
11 9
0 20

Entrada:

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

Salida: 11

Consejos

Podemos usar la siguiente idea para una solución muy compacta. Vamos a intersecar el conjunto de círculos con el eje X e interpretar los puntos de intersección como nodos en un gráfico plano:

Cada círculo produce exactamente 2 aristas en este gráfico y hasta dos nodos. Podemos contar el número de nodos mediante el uso de una tabla hash para realizar un seguimiento del número total de bordes distintos izquierdo o derecho.

Entonces podemos usar la fórmula característica de Euler para calcular el número de caras de un dibujo del gráfico:

V - E + F - C = 1

F = E - V + C + 1

Para calcular Cel número de componentes conectados, podemos usar una búsqueda de profundidad primero .

^{Nota: Esta idea problemática está tomada de un concurso de programación croata reciente , pero no hagas trampa mirando los esquemas de la solución. :)}

Mathematica, 125 122 - 150 = -28 caracteres

No sé la complejidad de la función incorporada ConnectedComponents.

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

Uso:

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

Ruby - 312 306 285 273 269 259 caracteres

Esta respuesta ha sido reemplazada por mi otro enfoque que utiliza considerablemente menos caracteres y se ejecuta O(n log n).

De acuerdo, vamos. Para empezar, solo quería una implementación funcional, por lo que aún no está optimizada algorítmicamente. Ordeno los círculos de mayor a menor y construyo un árbol (los círculos incluidos en otros círculos son hijos de los más grandes). Ambas operaciones toman lo O(n^2)peor y lo O(n log n)mejor. Luego recorro el árbol para contar áreas. Si los hijos de un círculo llenan todo su diámetro, hay dos áreas nuevas; de lo contrario, solo hay una. Esta iteración toma O(n). Por lo tanto, tengo una complejidad general O(n^2)y no califico para recompensa ni penalización.

Este código espera que la entrada sin el número de círculos se almacene en una 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

Versión sin golf (espera entrada 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 caracteres

Así que aquí hay un enfoque diferente. Esta vez, clasifico los círculos por su punto más a la izquierda. Los círculos que se tocan en su punto más a la izquierda se ordenan de mayor a menor. Esto toma O(n log n)(bueno, Ruby usa la ordenación rápida, así que en realidad, O(n^2)pero implementar la ordenación de combinación / montón probablemente esté fuera del alcance de este desafío). Luego repito esta lista, recordando todas las posiciones de la izquierda y la derecha de los círculos que he visitado. Esto me permite detectar si una serie de círculos se conecta a través de un círculo más grande. En este caso, hay dos subáreas, de lo contrario, solo una. Esta iteración solo O(n)da una complejidad total de la O(n log n)cual califica para la recompensa de 100 caracteres.

Este fragmento espera que la entrada se suministre a través de un archivo en los argumentos de la línea de comandos sin el número de círculos:

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

Versión sin golf (espera entrada en una 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 (¿bonificación?) = 160

Al interpretar los círculos como figuras con vértices (intersecciones), aristas y caras (áreas del plano), podemos relacionarnos usando la característica de Euler , por lo que solo necesitamos saber el número de "vértices" y "aristas" para tener el número de "caras" o regiones del plano con la fórmula escrita a continuación:

ACTUALIZACIÓN: Al pensar un momento, descubrí que el problema con mi método era solo cuando los círculos no estaban conectados, así que se me ocurrió una idea, ¿por qué no conectarlos artificialmente? Entonces el conjunto satisfará la fórmula de Euler.

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

[No trabaje con círculos anidados, por lo que no es una respuesta al problema para casos generales]

Código :

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 , = 173

Creo que si reescribiera esto en Ruby o Python podría salvar personajes.

Código:

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)

Algoritmo:

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

No soy terriblemente bueno en la notación O grande, pero creo que es O (n) ya que estoy recorriendo cada círculo de manera efectiva 3 veces (crear, izquierda, derecha) y también ordenar las teclas del mapa (y ordenar por O ( n log n) pero eso desaparece). ¿Es esto determinista?

JavaScript (ES6) - 255 254 Caracteres - 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

Asume que la cadena de entrada está en la variable Sy genera el número de regiones en la consola.

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 complejidad temporal es ahora O (N).

Caso de prueba 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

Salidas: 3

Caso de prueba 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

Salidas: 5

Caso de prueba 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

Salidas: 6

Caso de prueba 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

Salidas: 11

Caso de prueba 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

Salidas: 105

Versión previa

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

Con comentarios:

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 complejidad de tiempo total es O (N) para todo excepto el tipo que es O (N.log (N)); sin embargo, al reemplazar esto con un tipo de depósito, esto reducirá la complejidad total a O (N).

La memoria requerida es O (N).

Adivina lo que sigue en mi lista de tareas pendientes ... clasifica en menos de 150 caracteres. Hecho