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:
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 N
Zeilen 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
I
im 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 O
im 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, wobein
die 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:
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 C
die 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. :)
n log n
Bonus 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)Antworten:
Mathematica,
125,122-150 = -28 ZeichenIch kenne die Komplexität der eingebauten Funktion nicht
ConnectedComponents
.Verwendung:
quelle
ConnectedComponents
die 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?Ruby -
312306285273269259 ZeichenDiese 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 undO(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 nehmenO(n)
. Ich bin also insgesamt komplexO(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
:Ungolfed-Version (erwartet Eingabe in Variable
string
):quelle
11
. Für den in deinem Kommentar9
.10
und8
mit meiner ungolfed version, aber11
und9
mit meiner aktuellen golfed version: DRuby,
203183173133 - 100 = 33 ZeichenAlso 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 nurO(n)
eine Gesamtkomplexität, vonO(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 :
Ungolfed-Version (erwartet Eingabe in eine Variable
string
):quelle
-1 1 1 1 0 2 4 2 0 6
. Ich überlege mir, wie ich das morgen Abend beheben kann (hoffentlich).Julia - 260 -100 (Bonus?) = 160
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.
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 :
quelle
2 -10 1 10 1
.n=2
, die Kreise sind(C=(-10,0), r=1)
und(C=(10,0), r=1)
4 0 2 1 1 10 2 11 1
Aber ich glaube nicht, dass ich Ihnen viel mehr Testfälle geben kann, das wäre ein bisschen unfairSpidermonkey JS,
308, 287, 273 - 100 = 173Ich denke, wenn ich dies in Ruby oder Python umschreibe, könnte ich Zeichen speichern.
Code:
Algorithmus:
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?
quelle
r
Schleife und diel
Schleife in einer Anweisung kombiniert , würde ich es begrüßen.JavaScript (ES6) -
255254 Zeichen -100250 Bonus =1554Angenommen, die Eingabezeichenfolge befindet sich in der Variablen
S
und gibt die Anzahl der Regionen an die Konsole aus.Die zeitliche Komplexität ist nun O (N).
Testfall 1
Ausgänge:
3
Testfall 2
Ausgänge:
5
Testfall 3
Ausgänge:
6
Testfall 4
Ausgänge:
11
Testfall 5
Ausgänge:
105
Vorherige Version
Mit Kommentaren:
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.Getanquelle
O(n)
(in der TatO(n+k)
), aberO(n^2)
oderO(n log n)
schlimmstenfalls in Abhängigkeit von dem Sortieralgorithmus innerhalb Eimer verwendet, so dass Sie es in 50 Zeichen tun bräuchten.