Neueste Themen
-
Hallo,
jetzt wo auch die zweite Runde rum ist, könnten wir... mehrHallo,
jetzt wo auch die zweite Runde rum ist, könnten wir uns ja mal über Lösungen austauschen.
-
Hallo, der Abgabetermin ist ja laut Website Montag der... mehrHallo, der Abgabetermin ist ja laut Website Montag der 19.04.2021. Ist es wie bei der ersten Runde, dass dann die Abgabedeadline +- 24:00 am Montag, also der Nacht auf Dienstag ist?
-
Leider ist der alte BwInf-Chat-Matrix-Server (matrix.bwinf.de;... mehrLeider ist der alte BwInf-Chat-Matrix-Server (matrix.bwinf.de; riot.bwinf.de) seit gestern nicht mehr erreichbar. Es gab einen Datenverlust in der Datenbank und leider hatten wir keine Backups von diesem Server gemacht.
Wir haben aber bereits einen neuen Matrix-Server im Produktivbetrieb, der jetzt auch etwas ernsthafter und mit Backups betrieben wird.
Ihr findet den neuen BwInf-Chat daher ab sofort unter: https://chat.bwinf.de/#/room/#bwinf:bwinf.de .
Wer bereits auf einem anderen Matrix-Homeserver einen Account hat, kann einfach den Raum #bwinf:bwinf.de betreten. weniger
-
Laut den Regeln darf man in der 2. Runde keine Gruppenarbeit... mehrLaut den Regeln darf man in der 2. Runde keine Gruppenarbeit machen. Darf man aber untereinander die Outputs vergleichen, also sodass man dann Beispielsweise erkennt, dass es "bessere" Lösungen gibt? So wie bei Codeforces, wo man eine Rückmeldung bekommt, ob der Output passt oder nicht. Man erfährt dadurch ja nicht den Lösungsweg/-ansatz des Anderen, sondern nur dessen Ergebnis.
-
Hallo,
welche werte können die Schüsselnummern... mehrHallo,
welche werte können die Schüsselnummern annehmen? 0-Anzahl an Schüsseln oder beliebige Werte? Ich vermute ersteres, aber in der Aufgabenstellung steht dazu nichts genaues.
Vielen Dank
Moritz Hanke
Alle anzeigen
Neueste Forenbeiträge
-
Dann stelle ich mal auch Lösungen vor.
Aufgabe 2 habe ich... mehrDann stelle ich mal auch Lösungen vor.
Aufgabe 2 habe ich ähnlich zu einigen, die bisher vorgestellt haben, gelöst. (Ich habe nicht alles durchgelesen.) Der vollständigkeit halber hier meine Dokumentation.
Bei Aufgabe 3 habe ich eine Lösung mit O(N^3/K^2) im Averagecase. Man kann nämlich zeigen, dass sich bei einer stabilen Konfiguration die Anzahlen der Häuser zwischen Eisdiele 1 und 2, zwischen Eisdiele 2 und 3 sowie zwischen Eisdiele 3 und 1 jeweils höchstens um 3 unterscheiden, was den Suchraum deutlich verkleinert: Dokumentation
Weiß jemand aus den Vorjahren, wo die "Cutoffs" normalerweise liegen? weniger
-
Ich habe Aufgabe zwei und drei in C++ gelöst:... mehrIch habe Aufgabe zwei und drei in C++ gelöst: https://github.com/christopher-besch/bwinf_39_round2
Für Aufgabe drei habe ich ein Visualisierungsprogramm für's Web geschrieben. Man kann es hier benutzen. Der Source Code ist hier: https://github.com/christopher-besch/lake_visualizer
-
Bei Aufgabe 1 konnte ich Subset-Sum auf das Problem reduzieren... mehrBei Aufgabe 1 konnte ich Subset-Sum auf das Problem reduzieren und darüber die NP-Vollständigkeit zeigen. Ansonsten hat meine Heuristik denselben Ansatz wie die von den meisten hier, zuerst Reihenweise das Feld zu füllen.
Aufgabe 2 habe ich wie Jonathan auch per Matrix mit Einträgen a_f,s gelöst, die angeben, ob Frucht f in Schüssel s liegen kann. Zusätzlich habe ich die Aufgabe dahingehend erweitert, dass das Programm ausgibt, welche Informationen noch benötigt sind, um eine eineindeutige Zuordnung feststellen zu können (dabei soll die Anzahl der Informationen/Beobachtungen minimiert werden). weniger
-
Gerade auch nochmal Zeit gefunden ein paar Worte dazu zu... mehrGerade auch nochmal Zeit gefunden ein paar Worte dazu zu schreiben, was ich gemacht habe.
Bei Aufagbe 2 habe ich jeder Obstsorte auf Basis der Beobachtungen in denen sie vorkommen einen Wert zu gewiesen. Folgend sind also alle äquivalenten Obstsorten nicht voneinander zu unterscheiden. Dann kann man einfach alle Obstsorten raussuchen die die Werte der gesuchten Obstsorten besitzen. Worstcase ist der Ansatz O(k*n^2). Im Avargecase ist der Ansatz O(k*n).
Bei Aufgabe 3 habe ich zunächst Untersucht, wie sich ein einzelnes Zentrum auf dem Zahlenstrahl verhält. Unter der gegebenen Bedingung ist jeder Punkt zwischen unterem und oberen Median ein stabiles Zentrum. Das dies auch für alle 3 Zentren auf dem Kreis gilt (jeweils für die Menge an Punkten, zu denen sie die nächsten sind) habe ich einfach mal angenommen. Vielleicht ließe sich das auch beweisen, aber ich fand, dass das als Heuristik durchgehen kann. Durch diese und ein paar weitere Beobachtungen kann ich die... weniger
-
Ich habe die Aufgaben 2 und 3 bearbeitet:
In A2 stelle ich jede... mehrIch habe die Aufgaben 2 und 3 bearbeitet:
In A2 stelle ich jede Beobachtung als Matrix mit Aussagen (kann sich Obst X in Schüssel Y befinden?) dar, die Lösung erhält man, indem man die komponentenweise logische Konjunktion bildet. Laufzeit (b: Anzahl Beobachtungen, n: Anzahl Obstsorten) O(b * n^2)
A3 habe ich mit Brute-Force gelöst. Für jede mögliche Konstellation K lässt sich dabei in O(1) (nach Vorberechnung in O(U^3)) die andere Konstellation L' errechnen, die die meisten Stimmen erhalten würde - genau dann, wenn das mehr als die Hälfte der Anzahl der Häuser ist, ist K instabil. Gesamte Laufzeit: O(U^3)
Und hier die Einsendung: https://github.com/LinuxUserJTB/Einsendung_BwInf_39_2 weniger
Alle anzeigen
Share
