Kreise, die das Flugzeug teilen

23

Aufgabe

Sie erhalten eine Reihe von Kreisen in der Ebene mit ihren Mittelpunkten auf der Linie y = 0 . Es ist garantiert, dass kein Kreispaar mehr als einen gemeinsamen Punkt hat.

Sie müssen bestimmen, in wie viele Bereiche die Kreise die Ebene unterteilen. Eine Region ist eine einschlussmaximale zusammenhängende Menge von Punkten, die keinen der Kreise schneiden.

Sie sollten ein Programm schreiben, das diese Antwort berechnet, wenn Sie eine Beschreibung der Kreise erhalten.


Hier ist ein Beispiel:

Beispiel 1

Auf der linken Seite sehen Sie die in der Ebene gezeichneten Kreise. In der rechten Bildhälfte sind die durch die Kreise erzeugten Bereiche jedoch deutlich gefärbt (eine Farbe pro Bereich). In diesem Beispiel gibt es sechs Regionen.


Eingang

Die erste Zeile der Eingabe enthält eine Zahl N, die Anzahl der folgenden Kreisbeschreibungen. Diese Zeile ist optional. Wenn Ihre Lösung ohne sie funktioniert, ist dies in Ordnung.

Die folgenden NZeilen enthalten jeweils zwei Ganzzahlen, x i und r i > 0 , die einen Kreis mit Mittelpunkt (x i , 0) und Radius r i darstellen .

Es ist garantiert, dass kein Kreispaar mehr als einen gemeinsamen Punkt hat. Es ist weiterhin garantiert, dass x i und r i den10^9 absoluten Wert nicht überschreiten (so dass sie bequem in eine 32-Bit-Ganzzahl passen).


Die Eingabe kann sein:

  • aus STDIN lesen

  • Aus einer Datei Iim aktuellen Verzeichnis lesen

Alternativ könnte die Eingabe sein:

  • Verfügbar als Zeichenfolge (einschließlich Zeilenumbrüchen) in einer globalen Variablen

  • auf dem Stapel


Ausgabe

Dies sollte eine einzelne Ganzzahl sein, die Anzahl der produzierten Regionen. Dies sollte in STDOUT oder in eine Datei geschrieben werden, die Oim aktuellen Verzeichnis benannt ist.


Regeln

  • Kürzester Code in Bytes gewinnt

  • +200 Byte Strafe, wenn Ihr Code kein Laufzeit- + Raumkomplexitätspolynom enthält n

  • -100-Byte-Bonus für die im schlimmsten Fall zu erwartende Laufzeit + Speicherplatzkomplexität O(n log n)

  • -50-Byte-Bonus für die im schlimmsten Fall zu erwartende Laufzeit + Speicherplatzkomplexität O(n)

  • -100-Byte-Bonus für deterministische Laufzeit + Speicherplatzkomplexität O(n)

Bei der Beurteilung der Laufzeit:

  • Angenommen, Hash-Tabellen haben O(1)unabhängig von der Reihenfolge der Operationen und den Eingabedaten eine erwartete Laufzeit für das Einfügen, Löschen und Nachschlagen. Dies kann wahr sein oder nicht, abhängig davon, ob die Implementierung eine Randomisierung verwendet.

  • Angenommen, die eingebaute Art Ihrer Programmiersprache benötigt deterministische O(n log n)Zeit, wobei ndie Größe der Eingabesequenz angegeben wird.

  • Nehmen wir an, dass arithmetische Operationen an Eingabenummern nur O(1)Zeit in Anspruch nehmen .

  • Nehmen Sie nicht an, dass Eingabezahlen durch eine Konstante gebunden sind, obwohl dies aus praktischen Gründen der Fall ist. Dies bedeutet, dass Algorithmen wie radix sort oder counting sort keine lineare Zeit sind. Im Allgemeinen sollten sehr große konstante Faktoren vermieden werden.


Beispiele

Eingang:

2 
1 3
5 1

Ausgabe: 3


Eingang:

3
2 2
1 1
3 1

Ausgabe: 5

4
7 5
-9 11
11 9
0 20

Eingang:

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

Ausgabe: 11


Hinweise

Wir können die folgende Idee für eine sehr kompakte Lösung verwenden. Lässt uns die Menge der Kreise mit der X-Achse schneiden und die Schnittpunkte als Knoten in einem ebenen Graphen interpretieren:

Bildbeschreibung hier eingeben

Jeder Kreis erzeugt in diesem Diagramm genau 2 Kanten und bis zu zwei Knoten. Wir können die Anzahl der Knoten zählen, indem wir eine Hash-Tabelle verwenden, um die Gesamtzahl der unterschiedlichen linken oder rechten Ränder zu verfolgen.

Dann können wir die Euler-Kennlinienformel verwenden , um die Anzahl der Flächen einer Zeichnung des Graphen zu berechnen:

V - E + F - C = 1

F = E - V + C + 1

Um Cdie Anzahl der verbundenen Komponenten zu berechnen , können wir eine Tiefensuche verwenden .


Hinweis: Diese Problemidee stammt aus einem kürzlich durchgeführten kroatischen Programmierwettbewerb. Betrügen Sie jedoch nicht, indem Sie sich die Lösungsskizzen ansehen. :)

Niklas B.
quelle
Sind einige dieser Boni Lockvögel?
user2357112 unterstützt Monica
@ user2357112 Gehen Sie nicht davon aus, dass dies nicht möglich ist, wenn Sie es nicht beweisen können;)
Niklas B.
Nun, mit Eingaben, die garantiert in eine Maschinen-Ganzzahl passen, könnten wir eine Radix-Sortierung verwenden und sie O (n) nennen. Ich hasse es, eine eingeschränkte Eingabegröße anzunehmen, denn genau genommen bedeutet dies, dass es endlich viele mögliche Eingaben gibt.
user2357112 unterstützt Monica am
@ user2357112 Nein, ich sagte, Sie können bei der Beurteilung der Asymptotik nicht davon ausgehen, dass die Ganzzahlen begrenzt sind. Weder die Radix-Sortierung noch die Zählsortierung sind also linear in Zeit und Raum. Dass sie in ein Wort passen, dient nur dazu, die Arithmetik "real" zu machen O (1) und aus praktischen Gründen (begrenzte variable Breite in den meisten Sprachen)
Niklas B.
@ NiklasB. Wenn ich einen Algorithmus habe, bei dem die einzige Komponente mit superlinearer Komplexität die Sortierung ist, muss ich eine Zusammenführungssortierung implementieren, wenn meine Sprache eine schnelle Sortierung verwendet, um den n log nBonus zu erhalten. Außerdem habe ich neue konzeptionell neue Lösungen. Sollte ich eine neue Antwort posten oder die alte ersetzen? (Ich würde die frühere vorziehen, falls meine neue Lösung nicht wirklich korrekt ist)
Martin Ender

Antworten:

2

Mathematica, 125, 122-150 = -28 Zeichen

Ich kenne die Komplexität der eingebauten Funktion nicht ConnectedComponents.

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

Verwendung:

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

Alephalpha
quelle
Ich denke, wir können mit Sicherheit davon ausgehen, dass ConnectedComponentsdie linear erwartete Worst-Case-Komplexität vorliegt. Wenn es also O (n) -Komponenten gibt, wäre dies in Ordnung. Ich verstehe Mathematica nicht, kann also nicht sagen, ob es insgesamt O (n) ist und sich für den -150-Bonus qualifiziert? Ich denke schon. Führe ich es einfach mit der Eingabe in STDIN aus?
Niklas B.
@NiklasB. Bei seiner Eingabemethode wird lediglich eine Zeichenfolgenvariable an eine anonyme Funktion übergeben. also ich denke das sollte sich qualifizieren. Was die Ausgabe betrifft, führt dies in Mathematica einfach dazu, dass die Zahl in der Konsolenausgabe endet. Das sollte wahrscheinlich auch in Ordnung sein.
Martin Ender
Ich habe die Richtigkeit dieser Angaben überprüft, daher denke ich, dass dies mit einer Punktzahl von -28 der neue Anführer ist. Herzliche Glückwünsche!
Niklas B.
@NiklasB. warum nur 150? Welcher Teil des Algorithmus hat eine superlineare Worst-Case-Komplexität?
Martin Ender
@ m.buettner 150 ist für O (n) erwartete Zeit. Bei Graphen mit willkürlichen Zahlen als Knoten, die wie hier implizit definiert sind, können Sie die Anzahl der CCs in linearer Zeit nicht finden. Dies kann durch Verringern der Elementunterscheidbarkeit für verbundene Komponenten angezeigt werden . Ich denke, wir können die Unterscheidbarkeit von Elementen auch auf das ursprüngliche Problem reduzieren
Niklas B.
4

Ruby - 312 306 285 273 269 259 Zeichen

Diese Antwort wurde durch meinen anderen Ansatz abgelöst, bei dem wesentlich weniger Zeichen verwendet werden und die Eingabe erfolgt O(n log n).

Okay, los geht's. Für den Anfang wollte ich nur eine funktionierende Implementierung, daher ist diese noch nicht algorithmisch optimiert. Ich sortiere die Kreise vom größten zum kleinsten und baue einen Baum (Kreise in anderen Kreisen sind Kinder dieser größeren). Beide Operationen dauern O(n^2)im schlimmsten und O(n log n)besten Fall . Dann durchlaufe ich den Baum, um Bereiche zu zählen. Wenn die Kinder eines Kreises seinen gesamten Durchmesser ausfüllen, gibt es zwei neue Bereiche, ansonsten gibt es nur einen. Diese Iteration nehmen O(n). Ich bin also insgesamt komplex O(n^2)und qualifiziere mich weder für Belohnungen noch für Strafen.

Dieser Code erwartet, dass die Eingabe ohne die Anzahl der Kreise in einer Variablen gespeichert wird 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

Ungolfed-Version (erwartet Eingabe in 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
Martin Ender
quelle
@NiklasB. ja der Testfall wäre schön. Die Beziehung, die die Kanten in meinem Baum definiert, besteht einfach darin, einen Kreis in einen anderen einzubeziehen. Da on circle nicht in zwei Kreisen enthalten sein kann, die sich nicht enthalten (aufgrund der Bedingung "one intersection"), sehe ich nicht, wie dies eine DAG sein könnte.
Martin Ender
Sind die Enkel eines Knotens auch seine Kinder?
user2357112 unterstützt Monica
@ user2357112 nein, da sie nur ihre direkten Eltern teilen können
Martin Ender
@NiklasB. Wenn ich es mit dem Beispiel in Ihrer Frage laufen lasse, bekomme ich 11. Für den in deinem Kommentar 9.
Martin Ender
@NiklasB. warte, ich bekomme tatsächlich 10und 8mit meiner ungolfed version, aber 11und 9mit meiner aktuellen golfed version: D
Martin Ender
2

Ruby, 203 183 173 133 - 100 = 33 Zeichen

Also hier ist ein anderer Ansatz. Dieses Mal sortiere ich die Kreise nach dem Punkt ganz links. Kreise, die sich am äußersten linken Punkt berühren, werden vom größten zum kleinsten sortiert. Dies dauert O(n log n)(nun, Ruby verwendet die schnelle Sortierung, O(n^2)aber das Implementieren der Zusammenführungs- / Heap-Sortierung sprengt wahrscheinlich den Rahmen dieser Herausforderung). Dann durchlaufe ich diese Liste und erinnere mich an alle Positionen ganz links und ganz rechts der Kreise, die ich besucht habe. Auf diese Weise kann ich erkennen, ob eine Reihe von Kreisen über einen umschließenden größeren Kreis verbunden ist. In diesem Fall gibt es zwei Unterbereiche, ansonsten nur einen. Diese Iteration erfordert nur O(n)eine Gesamtkomplexität, von O(n log n)der sich die 100-Zeichen-Belohnung qualifiziert.

Dieses Snippet erwartet, dass die Eingabe über eine Datei in den Befehlszeilenargumenten ohne die Anzahl der Kreise bereitgestellt wird :

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

Ungolfed-Version (erwartet Eingabe in eine 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
Martin Ender
quelle
Leider schlägt dies bei allen größeren Testfällen fehl. Es ist zwar schnell;) Ich habe diesmal kein kleines Fehlerbeispiel, aber Sie können die Testdaten auf der Website des Wettbewerbs finden, auf die ich verlinkt habe (es ist Wettbewerb # 6)
Niklas B.
Der erste fehlerhafte Testfall ist kruznice / kruznice.in.2. Dies ist der erste "echte" Testfall. Ich gehe also davon aus, dass etwas grundlegend falsch mit dem Algorithmus oder der Implementierung ist. Funktioniert es korrekt mit beliebig verschachtelten Kreisen?
Niklas B.
@NiklasB. danke, ich werde einen Blick in die Testfälle werfen (es könnte aber bis morgen abend dauern, bis ich das Problem behoben habe)
Martin Ender
@NiklasB. Ich dachte , das Problem und die minimale Beispiel erfordert 5 Kreise versagt: -1 1 1 1 0 2 4 2 0 6. Ich überlege mir, wie ich das morgen Abend beheben kann (hoffentlich).
Martin Ender
Ihre Komplexitätsanalyse scheint davon auszugehen, dass der assoziative Array-Zugriff eine konstante Zeit ist. Das scheint im schlimmsten Fall unwahrscheinlich zu sein.
Peter Taylor
1

Julia - 260 -100 (Bonus?) = 160

Wenn wir die Kreise als Figuren mit Scheitelpunkten (Schnittpunkten), Kanten und Flächen (Flächen der Ebene) interpretieren, können wir sie mit der Euler-Eigenschaft in Beziehung setzen , sodass wir nur die Anzahl der "Scheitelpunkte" und "Kanten" kennen müssen, um die Anzahl zu erhalten von "Flächen" oder Regionen der Ebene mit der folgenden Formel:Euler-Kennlinie

UPDATE: Nachdem ich eine Weile nachgedacht hatte, stellte ich fest, dass das Problem mit meiner Methode nur dann bestand, wenn Kreise nicht verbunden waren. Deshalb kam mir die Idee, warum man sie nicht künstlich verbindet. Das Ganze wird also die Euler-Formel erfüllen.

Kreise Beispiel

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

[Arbeiten Sie nicht mit verschachtelten Kreisen, daher ist dies keine Antwort auf das Problem für allgemeine Fälle.]

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
CCP
quelle
Ich denke, Ihr Programm wird scheitern 2 -10 1 10 1.
Niklas B.
"Es ist garantiert, dass kein Kreispaar mehr als einen gemeinsamen Punkt hat." Also denke ich, es wird nicht zutreffen :)
KPCh
@CCP Sie haben keine gemeinsamen Punkte. n=2, die Kreise sind (C=(-10,0), r=1)und(C=(10,0), r=1)
Niklas B.
1
Muss der Graph nicht verbunden sein, um die Euler-Charakteristik anzuwenden?
user2357112 unterstützt Monica
1
Ah, hier ist ein einfacher Fall: 4 0 2 1 1 10 2 11 1Aber ich glaube nicht, dass ich Ihnen viel mehr Testfälle geben kann, das wäre ein bisschen unfair
Niklas B.
1

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

Ich denke, wenn ich dies in Ruby oder Python umschreibe, könnte ich Zeichen speichern.

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)

Algorithmus:

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

Ich bin nicht besonders gut in der großen O-Notation, aber ich denke, das ist O (n), da ich effektiv drei Mal durch jeden Kreis laufe (erstellen, links, rechts) und auch die Schlüssel der Karte sortiere (und ich sortiere nach O ( n log n) aber das verschwindet). Ist das deterministisch?

Nicht dieser Charles
quelle
Wenn jemand einen Rat hat, wie man die rSchleife und die lSchleife in einer Anweisung kombiniert , würde ich es begrüßen.
Nicht dass Charles
Prost :) Sieht für mich so aus, als ob deine Laufzeit tatsächlich O (n log n) ist, aufgrund der Sortierung, die -100 wäre. Ich werde Sie wissen lassen, ob es alle Testfälle besteht.
Niklas B.
Schön, Ihr Programm besteht alle Testfälle beim ersten Versuch. Ich denke, so etwas (Sweepline mit einem Status, der in einem Stapel gespeichert ist) war die offizielle Lösung der Problemautoren. Ihr Programm erhält eine Gesamtpunktzahl von 173
Niklas B.
@NiklasB. Vielen Dank!
Nicht dass Charles
Ich habe versucht, eine viel robustere Lösung mit überlappenden Kreisen zu finden. Dann habe ich gesehen, dass sie sich nur an einem Punkt schneiden können.
Nicht dass Charles
-1

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

Angenommen, die Eingabezeichenfolge befindet sich in der Variablen Sund gibt die Anzahl der Regionen an die Konsole aus.

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

Die zeitliche Komplexität ist nun O (N).

Testfall 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

Ausgänge: 3

Testfall 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

Ausgänge: 5

Testfall 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

Ausgänge: 6

Testfall 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

Ausgänge: 11

Testfall 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

Ausgänge: 105

Vorherige Version

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

Mit Kommentaren:

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

Die Gesamtzeitkomplexität ist O (N) für alles außer der Sortierung O (N.log (N)). Wenn Sie diese jedoch durch eine Bucket-Sortierung ersetzen, wird die Gesamtkomplexität auf O (N) reduziert.

Der benötigte Speicher ist O (N).

Ratet mal, was als nächstes auf meiner ToDo-Liste steht ... Bucket-Sortierung in weniger als 150 Zeichen. Getan

MT0
quelle
Bucket hat Art nur durchschnittliche Komplexität O(n)(in der Tat O(n+k)), aber O(n^2)oder O(n log n)schlimmstenfalls in Abhängigkeit von dem Sortieralgorithmus innerhalb Eimer verwendet, so dass Sie es in 50 Zeichen tun bräuchten.
Martin Ender
@ m.buettner - Bucket-Sortierung kann in O (N) Worst-Case-Komplexität durchgeführt werden. Es basiert auf einer sorgfältigen Auswahl der Buckets und einem O (1) -Algorithmus für die Zuordnung zu Buckets. Ich habe es schon einmal gemacht (und es bewiesen) und muss nur den Code nach JavaScript übertragen. Der obige Algorithmus ist bereits O (N.log (N)), daher besteht die einzige Verbesserung darin, einen O (N) -Sortieralgorithmus zu erhalten.
MT0
Mich würde dieser Beweis und die entsprechende Auswahl an Eimern interessieren. :)
Martin Ender
cs.princeton.edu/~dpd/Papers/SCG-09-invited/… (auf Seite 556) enthält ein Beispiel für eine O (N) -Behälter-Sortierung. archive.org/stream/PlanarityTestingByPathAddition/… (Seite 75) enthält ein Beispiel für eine O (N) kombinierte DFS-Suche und Bucket-Sortierung (die zeitliche Komplexität wird auf Seite 76 erläutert).
MT0
1
@ Mt0 Moment mal, vielleicht liest du meinen Zusatz zum Komplexitätsteil der Frage. Mit unbegrenzten Zahlen ist eine Sortierung in linearer Zeit definitiv unmöglich
Niklas B.