Zadanie

Otrzymasz zestaw kół w płaszczyźnie z ich środkami na linii y = 0 . Gwarantujemy, że żadna para kół nie ma więcej niż jednego wspólnego punktu.

Twoim zadaniem jest określenie, w ilu regionach dzielą płaszczyznę okręgi. Region jest maksymalnym włączeniem ciągłym zestawem punktów, które nie przecinają żadnego z okręgów.

Powinieneś napisać program, który oblicza tę odpowiedź po otrzymaniu opisu kręgów.

Oto przykład:

Po lewej stronie widać koła narysowane w płaszczyźnie. Jednak w prawej połowie obrazu regiony utworzone przez kółka są wyraźnie kolorowe (jeden kolor na region). W tym przykładzie jest sześć regionów.

Wkład

Pierwszy wiersz danych wejściowych zawiera liczbę, Nliczbę opisów kół do naśladowania. Ta linia jest opcjonalna, jeśli twoje rozwiązanie działa bez niej, jest w porządku.

Poniższe Nlinie każdy zawiera dwie liczby całkowite, x _I i r _I > 0 , co stanowi okrąg o środku (x _I , 0) i promień r _I .

Gwarantujemy, że żadna para kół nie ma więcej niż jednego wspólnego punktu. Jest ponadto zapewnione, że x _I i r _i nie przekracza 10^9wartości bezwzględnej (tak, że wygodnie mieści się w 32-bitową liczbę całkowitą).

Dane wejściowe mogą być:

• czytane ze STDIN

• czytać z pliku o nazwie Iw bieżącym katalogu

Alternatywnie, dane wejściowe mogą być:

• dostępny jako ciąg (w tym znaki nowej linii) w zmiennej globalnej

• na stosie

Wydajność

Powinna to być pojedyncza liczba całkowita, liczba wyprodukowanych regionów. To powinno być zapisane do STDOUT lub pliku o nazwie Ow bieżącym katalogu.

Zasady

• Najkrótszy kod w bajtach wygrywa

• +200 bajtów kary, jeśli twój kod nie ma wielomianu złożoności środowiska wykonawczego n

• -100 bajtów premii za najgorszy oczekiwany czas działania + złożoność przestrzeni O(n log n)

• -50 bajtów premii za najgorszy oczekiwany czas działania + złożoność przestrzeni O(n)

• -100 bajtów premii za deterministyczne środowisko wykonawcze + złożoność przestrzeni O(n)

Podczas oceny środowiska wykonawczego:

• Załóżmy, że tabele skrótów O(1)oczekiwały czasu wykonywania wstawiania, usuwania i wyszukiwania, niezależnie od sekwencji operacji i danych wejściowych. Może to być prawda lub nie, w zależności od tego, czy implementacja używa randomizacji.

• Załóżmy, że wbudowany rodzaj języka programowania zajmuje deterministyczny O(n log n)czas, gdzie njest wielkość sekwencji wejściowej.

• Załóżmy, że operacje arytmetyczne na liczbach wejściowych zajmują tylko O(1)czas.

• Nie zakładaj, że liczby wejściowe są ograniczone stałą, chociaż są one ze względów praktycznych. Oznacza to, że algorytmy takie jak sortowanie radix lub sortowanie zliczające nie są czasem liniowym. Zasadniczo należy unikać bardzo dużych stałych czynników.

Przykłady

Wkład:

2 
1 3
5 1

Wydajność: 3

Wkład:

3
2 2
1 1
3 1

Wydajność: 5

4
7 5
-9 11
11 9
0 20

Wkład:

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

Wydajność: 11

Poradnik

Możemy zastosować następujący pomysł, aby uzyskać bardzo kompaktowe rozwiązanie. Przecinamy zbiór okręgów z osią X i interpretujemy punkty przecięcia jako węzły na wykresie planarnym:

Każde koło tworzy dokładnie 2 krawędzie na tym wykresie i maksymalnie dwa węzły. Możemy policzyć liczbę węzłów za pomocą tabeli skrótów, aby śledzić całkowitą liczbę wyraźnych lewej lub prawej krawędzi.

Następnie możemy użyć wzoru charakterystycznego dla Eulera, aby obliczyć liczbę ścian rysunku wykresu:

V - E + F - C = 1

F = E - V + C + 1

Aby obliczyć Cliczbę podłączonych komponentów, możemy użyć wyszukiwania w pierwszej kolejności .

^{Uwaga: ten pomysł na problem został zapożyczony z ostatniego chorwackiego konkursu programistycznego , ale proszę nie oszukiwać, patrząc na zarysy rozwiązania. :)}

Mathematica, 125 122-150 = -28 znaków

Nie znam złożoności wbudowanej funkcji ConnectedComponents.

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

Stosowanie:

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

Rubinowy - 312 306 285 273 269 259 znaków

Ta odpowiedź została zastąpiona przez moje inne podejście, które wykorzystuje znacznie mniej znaków i działa O(n log n).

Dobra, chodźmy. Na początek chciałem tylko działającej implementacji, więc nie jest to jeszcze zoptymalizowana algorytmicznie. Kręgi sortuję od największych do najmniejszych i buduję drzewo (kręgi zawarte w innych kręgach są dziećmi tych większych). Obie operacje trwają O(n^2)w najgorszym i O(n log n)najlepszym przypadku. Następnie iteruję przez drzewo, aby policzyć obszary. Jeśli dzieci koła wypełnią całą swoją średnicę, istnieją dwa nowe obszary, w przeciwnym razie jest tylko jeden. Ta iteracja trwa O(n). Mam więc ogólną złożoność O(n^2)i nie kwalifikuję się do nagrody ani kary.

Ten kod oczekuje, że dane wejściowe bez liczby okręgów zostaną zapisane w zmiennej 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

Wersja bez golfa (oczekuje danych wejściowych w zmiennej 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 znaków

Oto inne podejście. Tym razem sortuję okręgi według punktu najbardziej na lewo. Kręgi dotykające ich najbardziej wysuniętego na lewo punktu są sortowane od największego do najmniejszego. To zajmuje O(n log n)(no cóż, Ruby używa szybkiego sortowania, więc w rzeczywistości O(n^2)wdrożenie sortowania / scalania prawdopodobnie nie wchodzi w zakres tego wyzwania). Następnie iteruję tę listę, pamiętając wszystkie skrajnie lewe i prawe pozycje kręgów, które odwiedziłem. To pozwala mi wykryć, czy seria okręgów łączy się na całej długości przez otaczające większe koło. W takim przypadku istnieją dwa podobszary, w przeciwnym razie tylko jeden. Ta iteracja wymaga jedynie O(n)całkowitej złożoności, O(n log n)która kwalifikuje się do nagrody w postaci 100 znaków.

Ten fragment oczekuje, że dane wejściowe będą dostarczane przez plik w argumentach wiersza polecenia bez liczby okręgów:

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

Wersja bez golfa (oczekuje danych wejściowych w zmiennej 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

Interpretując okręgi jako figury z wierzchołkami (przecięciami), krawędziami i powierzchniami (obszary płaszczyzny) możemy odnosić się nawzajem za pomocą charakterystyki Eulera , więc musimy znać tylko liczbę „wierzchołków” i „krawędzi”, aby mieć liczbę „ścian” lub obszarów płaszczyzny za pomocą poniższego wzoru:

AKTUALIZACJA: Przez chwilę zastanawiałem się, że problem z moją metodą był tylko wtedy, gdy kręgi nie były połączone, więc wpadłem na pomysł, dlaczego nie sztucznie je połączyć? Tak więc całość spełni formułę Eulera.

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

[Nie działa z zagnieżdżonymi kręgami, więc nie jest to odpowiedź na problem w ogólnych przypadkach]

Kod :

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

Myślę, że jeśli przepisałem to w Ruby lub Python, mógłbym zapisać postacie.

Kod:

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)

Algorytm:

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

Nie jestem strasznie dobry w notowaniu dużych O, ale myślę, że to O (n), ponieważ efektywnie zapętlam każde koło 3 razy (tworzę, lewo, prawo), a także sortuję klucze mapy (i sortuję według O ( n log n) ale to znika). Czy to jest deterministyczne?

JavaScript (ES6) - 255 254 znaków - 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

Zakłada, że ​​łańcuch wejściowy znajduje się w zmiennej Si wyświetla w konsoli liczbę regionów.

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

Złożoność czasowa wynosi teraz O (N).

Przypadek testowy 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

Wyjścia: 3

Przypadek testowy 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

Wyjścia: 5

Przypadek testowy 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

Wyjścia: 6

Przypadek testowy 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

Wyjścia: 11

Przypadek testowy 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

Wyjścia: 105

Poprzednia wersja

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

Z komentarzami:

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

Całkowity czas złożoności wynosi O (N) dla wszystkiego oprócz sortowania, którym jest O (N.log (N)) - jednak zastąpienie go sortowaniem kubełkowym spowoduje zmniejszenie całkowitej złożoności do O (N).

Wymagana pamięć to O (N).

Zgadnij, co będzie dalej na mojej liście rzeczy do zrobienia ... sortowanie wiader w mniej niż 150 znaków. Gotowy