Tarefa

Você receberá um conjunto de círculos no plano com seus centros na linha y = 0 . É garantido que nenhum par de círculos tenha mais de um ponto em comum.

Sua tarefa é determinar em quantas regiões as quais os círculos dividem o plano. Uma região é um conjunto contíguo máximo de pontos de inclusão que não cruza nenhum dos círculos.

Você deve escrever um programa que calcule essa resposta quando receber uma descrição dos círculos.

Aqui está um exemplo:

No lado esquerdo, você vê os círculos desenhados no avião. No entanto, na metade direita da imagem, as regiões produzidas pelos círculos são coloridas distintamente (uma cor por região). Existem seis regiões neste exemplo.

Entrada

A primeira linha da entrada contém um número N, o número de descrições de círculo a seguir. Essa linha é opcional, se sua solução funcionar sem ela, tudo bem.

As seguintes Nlinhas de cada uma contém dois números inteiros, x _i e r _i > 0 , o que representa um círculo com o centro (x _i , 0) e raio r _i .

É garantido que nenhum par de círculos tenha mais de um ponto em comum. É ainda garantido que x _i e r _i não exceder 10^9em valor absoluto (de modo que eles se encaixam confortavelmente em um número inteiro de 32-bit).

A entrada pode ser:

• leia de STDIN

• ler de um arquivo nomeado Ino diretório atual

Como alternativa, a entrada pode ser:

• disponível como uma sequência (incluindo novas linhas) em uma variável global

• na pilha

Saída

Deve ser um número inteiro único, o número de regiões produzidas. Isso deve ser gravado em STDOUT ou em um arquivo nomeado Ono diretório atual.

Regras

• O menor código em bytes ganha

• Pena de 200 bytes, se o seu código não tiver um polinômio de tempo de execução + complexidade de espaço em n

• Bônus de -100 bytes para pior execução esperada + complexidade de espaço O(n log n)

• Bônus de -50 bytes para pior execução esperada + complexidade de espaço O(n)

• Bônus de -100 bytes para tempo de execução determinístico + complexidade de espaço O(n)

Ao avaliar o tempo de execução:

• Suponha que as tabelas de hash tenham O(1)tempo de execução esperado para inserção, exclusão e pesquisa, independentemente da sequência de operações e dos dados de entrada. Isso pode ou não ser verdade, dependendo se a implementação usa randomização.

• Suponha que o tipo interno da sua linguagem de programação leve O(n log n)tempo determinístico , onde né o tamanho da sequência de entrada.

• Suponha que as operações aritméticas nos números de entrada levem apenas O(1)tempo.

• Não assuma que os números de entrada estejam vinculados por uma constante, embora, por razões práticas, sejam. Isso significa que algoritmos como classificação de raiz ou classificação de contagem não são tempo linear. Em geral, fatores constantes muito grandes devem ser evitados.

Exemplos

Entrada:

2 
1 3
5 1

Saída: 3

Entrada:

3
2 2
1 1
3 1

Saída: 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

Saída: 11

Dicas

Podemos usar a seguinte idéia para uma solução muito compacta. Vamos cruzar o conjunto de círculos com o eixo X e interpretar os pontos de interseção como nós em um gráfico planar:

Cada círculo produz exatamente 2 arestas neste gráfico e até dois nós. Podemos contar o número de nós usando uma tabela de hash para acompanhar o número total de bordas esquerdas ou direitas distintas.

Em seguida, podemos usar a fórmula da característica de Euler para calcular o número de faces de um desenho do gráfico:

V - E + F - C = 1

F = E - V + C + 1

Para calcular Co número de componentes conectados, podemos usar uma pesquisa profunda .

^{Nota: Esta ideia do problema foi emprestada de um concurso recente de programação croata , mas não trapaceie olhando os contornos da solução. :)}

Mathematica, 125 122-150 = -28 caracteres

Não conheço a complexidade da função interna 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 resposta foi substituída por minha outra abordagem, que usa consideravelmente menos caracteres e é executada O(n log n).

OK, vamos lá. Para iniciantes, eu só queria uma implementação funcional, portanto isso ainda não está otimizado por algoritmo. Classifico os círculos do maior para o menor e construo uma árvore (os círculos incluídos em outros círculos são filhos dos maiores). Ambas as operações levam O(n^2)na pior e O(n log n)na melhor das hipóteses. Então eu percorro a árvore para contar as áreas. Se os filhos de um círculo preenchem todo o seu diâmetro, existem duas novas áreas, caso contrário, há apenas uma. Essa iteração leva O(n). Portanto, tenho complexidade geral O(n^2)e não me qualifico para recompensa nem penalidade.

Este código espera que a entrada sem o número de círculos seja armazenada em uma variável 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

Versão ungolfed (espera entrada na variável 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

Então, aqui está uma abordagem diferente. Desta vez, ordeno os círculos pelo ponto mais à esquerda. Os círculos que tocam no ponto mais à esquerda são classificados do maior para o menor. Isso é necessário O(n log n)(bem, Ruby usa classificação rápida, portanto, na verdade, a O(n^2)implementação da classificação de mesclagem / heap provavelmente está além do escopo desse desafio). Depois, percorro esta lista, lembrando todas as posições da esquerda e da direita dos círculos que visitei. Isso me permite detectar se uma série de círculos se conecta por todo o círculo maior. Nesse caso, existem duas subáreas, caso contrário, apenas uma. Essa iteração requer apenas O(n)uma complexidade total O(n log n)qualificada para a recompensa de 100 caracteres.

Esse snippet espera que a entrada seja fornecida por meio de um arquivo nos argumentos da linha de comando sem o 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

Versão ungolfed (espera entrada em uma variável 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 (bônus?) = 160

Interpretando os círculos como figuras com vértices (interseções), arestas e faces (áreas do plano), podemos nos relacionar usando a característica de Euler , portanto, precisamos saber apenas o número de "vértices" e "arestas" para ter o número de "faces" ou regiões do plano com a fórmula escrita abaixo:

ATUALIZAR: Ao pensar um pouco, descobri que o problema com o meu método era apenas quando os círculos não estavam conectados, então tive uma ideia: por que não conectá-los artificialmente? Portanto, o todo satisfará a fórmula de Euler.

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

[Não trabalhe com círculos aninhados, por isso não é uma resposta do problema para casos gerais]

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

Eu acho que se eu reescrevesse isso em Ruby ou Python eu poderia salvar caracteres.

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

Eu não sou muito bom com a notação O grande, mas acho que é O (n), pois estou efetivamente percorrendo cada círculo três vezes (criar, esquerda, direita) e também classificando as chaves do mapa (e eu classifico para O ( n log n) mas isso desaparece). Isso é determinístico?

JavaScript (ES6) - 255 254 caracteres - 100 250 bônus = 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

Supõe que a sequência de entrada esteja na variável Se emita o número de regiões para o 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).

A complexidade do tempo agora é O (N).

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

Saídas: 3

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

Saídas: 5

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

Saídas: 6

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

Saídas: 11

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

Saídas: 105

Versão anterior

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

Com comentários:

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

A complexidade do tempo total é O (N) para tudo, exceto a classificação que é O (N.log (N)) - no entanto, substituindo-o por uma classificação em bucket, isso reduz a complexidade total para O (N).

A memória necessária é O (N).

Adivinhe o que vem a seguir na minha lista de tarefas ... classifique com menos de 150 caracteres. Feito