Du bist nicht angemeldet.

Werbeanzeige

BlueCobold

Community-Fossil

Beiträge: 10 870

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

21

18.07.2011, 17:15

oben/unten nehme ich mal an
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Beiträge: 775

Beruf: Student

  • Private Nachricht senden

22

18.07.2011, 17:28

Theoretisch der Punkt mitte oben und mitte unten. Das ganze äußert sich dann so, dass dein Borderwert immer größer 0 und kleiner 256 sein muss. Hat mich anfangs auch irritiert.

Habe übrigens versucht mal eine Karte zu bruten... auch nach mehreren Stunden kein Ergebnis ^^. Gut ich hätte vllt zur Auswertung nicht die interne Funktion wählen sollen, aber ich wollte sicher gehn.
Leider hatte ich auch keine Fortschrittsanzeige (Anzahl der Versuche mitzuzählen ist bei knapp 10^1233 auch ein nicht triviales Problem) und kann nicht gaanz sicher sagen, ob ich alles richtig gemacht habe.

Helmut

5x Contest-Sieger

Beiträge: 691

Wohnort: Bielefeld

  • Private Nachricht senden

23

18.07.2011, 19:22

Leider hatte ich auch keine Fortschrittsanzeige (Anzahl der Versuche mitzuzählen ist bei knapp 10^1233 auch ein nicht triviales Problem) und kann nicht gaanz sicher sagen, ob ich alles richtig gemacht habe.

Nein, so ne Fortschrittsanzeige wäre ganz einfach: cout << "0% done" << endl; ;)
Bevor es 1% erreichen würde dürfte die Erde schon nicht mehr existieren. ;)
Sei stets geduldig gegenüber Leuten, die nicht mit dir übereinstimmen. Sie haben ein Recht auf ihren Standpunkt - trotz ihrer lächerlichen Meinung. (F. Hollaender)

24

18.07.2011, 19:46

Das Problem ist zu einfach.

Es gibt einen O(n^2*m) Algorithmus (mit m = anzahl Spalten und n = Anzahl Zeilen) basierend auf dynamischer Programmierung, der die optimale Lösung liefert. Und das sollte von der Komplexität her noch in 1 sekunde zu berechnen sein. Ich habs jetzt nicht ausprogrammiert, aber... :)

//edit auf n^2 korrigiert. wobei ich mir da nicht 100% sicher bin, ob es nicht doch schneller geht.

@Mastermind Nein, ich weiß nicht, wo die Mail landen würde, dafür kenne ich dich zu wenig und ich will den anderen den Wettbewerb nicht verderben, die spaß am knobel haben. Und der Algorithmus ist einfach genug, dass ich mir sicher bin, dass ich nicht der Einzige bin, der drauf kommt.

Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von »otze« (18.07.2011, 19:57)


Mastermind

unregistriert

25

18.07.2011, 19:50

Dann sag den Algo mal bitte. Ggf. auch per PN. Ich werd nicht teilnehmen, bin aber neugierig.

Architekt

Community-Fossil

Beiträge: 2 497

Wohnort: Hamburg

Beruf: Student

  • Private Nachricht senden

26

18.07.2011, 19:58

Da ich aus Zeitgründen eh nicht teilnehmen kann, schließ ich mich Mastermind an :o
Der einfachste Weg eine Kopie zu entfernen ist sie zu löschen.
- Stephan Schmidt -

Mastermind

unregistriert

27

18.07.2011, 20:19

Wenn es einen optimalen und effizienten Algorithmus gibt, macht der Wettbewerb an sich keinen Sinn, und es kommt nur darauf an auf selbigen auch zu kommen. Ich wüsste nicht wie man da noch jemandem den Spaß verderben könnte. Wenn du deine Erkenntnis nicht teilen willst, gut, aber das Argument finde ich schwach. Eine Diskussion über die optimale Lösung finde ich persönlich jedenfalls wesentlich spannender als den Wettbewerb an sich.

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 184

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

28

18.07.2011, 20:26

Ich bin jetzt nicht der Fachmann in Sachen dynamische Programmierung.
Bei Wikipedia steht:

Zitat

"Dynamische Programmierung kann dann erfolgreich eingesetzt werden, wenn das Optimierungsproblem aus vielen gleichartigen Teilproblemen besteht, und eine optimale Lösung des Problems sich aus optimalen Lösungen der Teilprobleme zusammensetzt"


Ist dies denn hier der Fall?

Ich denke nicht! Denn wenn ich z.B. die Karte in zwei Hälften teile und jede davon optimal löse, dann kann ich beim Zusammensetzen immer noch durch die Nahtstelle und den damit verbundenen Punktabzug suboptimal werden. Außerdem könnte es sein, dass ich bei einer der beiden Lösungen gezwungenermaßen eine der beiden Zivilisationen benachteilige. Das könnte ich in der anderen Hälfte theoretisch wieder ausgleichen. Löse ich jedoch beide getrennt, weiß ich davon garnichts und kann das nicht berücksichtigen.

An den oben genannten O(n²)-Algorithmus glaube ich jedenfalls nicht.
Zumal da "n" die Anzahl der Zeilen sein soll - und die Anzahl der Spalten ist dann völlig irrelevant, was die Komplexität angeht?

FalkT

Treue Seele

Beiträge: 125

Wohnort: AC

  • Private Nachricht senden

29

18.07.2011, 20:35

Dürfen wir die Lösung für den Contest in eine Klasse packen und es wird vor Programm-Ausführung ein Objekt dieser Klasse instanziiert ?
Dein benötigtes Interface wäre dann eine statische Member-Funktion.

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 184

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

30

18.07.2011, 20:37

Dürfen wir die Lösung für den Contest in eine Klasse packen und es wird vor Programm-Ausführung ein Objekt dieser Klasse instanziiert ?
Dein benötigtes Interface wäre dann eine statische Member-Funktion.

Du kannst auch einfach eine (lokale, von mir aus auch außerhalb der Funktion befindliche) Klasse definieren und davon dann eine Instanz innerhalb der "dividePlanet" erzeugen und damit machen, was Du willst.

Werbeanzeige