Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » kniffliges Rätsel
Autor
Universität/Hochschule kniffliges Rätsel
dvdlly
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 28.12.2016
Mitteilungen: 288
  Themenstart: 2022-07-03

Hallo miteinander, Das hier ist eine Aufgabe aus einem Programmierwettbewerb, niemand konnte sie lösen und mich würden eure Ideen hierzu interessieren. Wir befinden uns im Finale eines Gärtnerwettbewerbes, es treten Zwei Gärtner gegeneinander an. Sie besitzen eine Vielzahl von Gewächsen, die miteinander verglichen werden und dann wird eines der beiden Gewächse zum "Sieger" gekührt. Dieser Prozess findet 7 Tage in Folge statt. Es werden insgesamt an allen 7 Tagen zusammen \(d_1 + ... + d_7 \leq 10^5\) Gewächse verglichen. Nun gibt es eine Gruppe von Freunden, die das folgende Spiel erfunden haben: sie versuchen zu erraten, wer von den beiden Gärtnern in einer bestimmten Runde gewinnt. Liegt einer der Freunde mit seinem Tipp richtig, so erhält er einen Punkt. Es darf pro Tag nur ein Tipp pro Freund auf einen Vergleich abgegeben werden. Einer der Freunde, nennen wir ihn Peter, hat seine Tipps zu spät abgegeben, so dass nur noch seine Tipps für Samstag und Sonntag zählen und er fragt sich, ob er noch die Chance hat zu gewinnen. Ziel ist es herauszufinden, ob er gewinnen kann oder nicht. Die Anzahl der Freunde ist \(n \leq 10^5\). Die maximale "Rechenzeit" ist 3 Sekunden, Brute-Force Lösungen sind also auszuschließen. Meine Idee wäre es für die ersten 5 Tage eine Belegung zu finden. die die Punkte aller Teilnehmer minimiert. Es kann natürlich sein, dass zwei Spieler auf den selben Vergleich komplementär tippen, so dass einer garantiert einen Punkt kriegt. In diesem Fall sind beide Mögichkeiten als "Ereignispfade" weiter zu betrachten. Dann prüft man, ob jemand mindestens 2 Punkte erreicht hat, ist das der Fall können wir aufhören. Falls nicht, fährt man fort. indem man eine Belegung findet, die die Punkte von Peter maximieren und die der andern minimieren. Dann prüft man, ob Peter so gewinnen kann. Das ist eigentlich recht einfach deswegen frage ich mich, ob ich etwas übersehen habe (einen Fehler gemacht, oder ob es noch schneller geht).


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3211
  Beitrag No.1, eingetragen 2022-07-04

So wäre es in der Tat trivial. Alle Freunde haben fünf Tage lang auf die hübsche Gärtnerin mit den Fruchbarkeit versprechenden ... ähhh ... Daumen getippt. Gewonnen hat aber immer der schrullige Alte mit seinem Chemiebaukasten, dessen Auberginen schneller wachsen und schöner glänzen als die eingeölten Muskelpakete der Wrestlingqueen Ana Bolica. Also hat noch niemand einen Punkt und der Nachzügler kann problemlos gewinnen. So wird die Aufgabe jedoch nicht gemeint sein. Gibt es einen Originallaut?


   Profil
dvdlly
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 28.12.2016
Mitteilungen: 288
  Beitrag No.2, vom Themenstarter, eingetragen 2022-07-04

Das hier ist die originale Aufgabenstellung: https://judge.gcpc.nwerc.eu/public/problems/418/text


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3211
  Beitrag No.3, eingetragen 2022-07-04

OK, so macht das natürlich Sinn. Das Problem mit deinem Weg ist der Rechenaufwand. Einen Algorithmus zu implementieren, der die Aufgabe löst, sollte vergleichsweise einfach sein. Schwierig ist es, einen Algorithmus zu finden, der die Aufgabe effizient löst, selbst wenn es hunderte "+/- Paare" mit entsprechender Verzweigung gibt. Im Wesentlichen hast du eine Matrix, deren Zeilen aus je 7 boolschen Werten bestehen, entweder Variablen, wahr oder falsch. Gesucht ist eine Belegung der Variablen, sodass keine Zeile mehr als einmal wahr enthält. Im Fall der Musterbeispiele sollte das so aussehen: Beispiel 1: 3 4 4 4 4 4 4 4 1 1 1 1 4 -2 1 2 2 2 2 -4 1 -1 3 3 3 3 -3 3 3 -2 -1 Matrix 1: 0 0 0 0 a 1 0 0 0 0 0 !a 0 1 0 0 0 0 0 0 0 Beispiel 2: 3 4 4 4 4 4 4 4 4 3 2 1 4 1 1 2 4 4 2 2 4 2 2 3 3 4 1 3 2 -2 -1 Matrix 2: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0


   Profil
dvdlly
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 28.12.2016
Mitteilungen: 288
  Beitrag No.4, vom Themenstarter, eingetragen 2022-07-04

Hast du einen Ansatz der schneller läuft?


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3211
  Beitrag No.5, eingetragen 2022-07-04

Vielleicht liege ich auch falsch. Hast du deinen Ansatz denn mal implementiert und auf Korrektheit und Geschwindigkeit getestet?


   Profil
dvdlly
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 28.12.2016
Mitteilungen: 288
  Beitrag No.6, vom Themenstarter, eingetragen 2022-07-04

Bisher und in absehbarer Zeit fehlt mir ebendiese zum implementieren. Ich bin davon ausgegangen, dass der Ansatz zu einfach ist, als das ihn alle Teams übersehen hätten.


   Profil
dvdlly hat die Antworten auf ihre/seine Frage gesehen.
dvdlly wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]