Du bist nicht angemeldet.

Werbeanzeige

$nooc

Alter Hase

Beiträge: 873

Wohnort: Österreich / Kärnten

Beruf: Schüler

  • Private Nachricht senden

91

23.07.2008, 21:51

poah..

@David:

wie kommt man denn bitte auf so eine lösung? ^^
Am Anfang der Weisheit steht die eigene Erkenntnis, dass man selbst nichts weiß! - Sokrates

S.Seegel

2x Contest-Sieger

  • Private Nachricht senden

92

24.07.2008, 14:33

Herzlichen Glückwunsch an Helmut !

Davids Lösung hat einen Moment gedauert nachzuvollziehen, und da David noch keine Zeit gefunden hat, seine Lösung zu erläutern, versuche ich einfach mal die Neugierigen zu erhellen.

Der Algorithmus geht alle Elemente des Quadrats rückwärts durch (i ist der Index des aktuellen Elements).
Für jedes Element wird dann die Anzahl der Vorkommen dieses Elements in den vorangegangenen Zeilen gezählt. Das wird dadurch bewerkstelligt, das j durch die Initialisierung in der Laufbedingung auf das erste Element der aktuellen Zeile (also derjenigen, in der sich i befindet) gesetzt wird.
Durch die Dekrementierung in der Laufbedingung der inneren while-Schleife läuft j also vom letzten Element der vorangehenden Zeile bis 0.
Wird das aktuelle Element in den vorangegangenen Zeilen gefunden, wird der Zähler num_equals_left dekrementiert, der zu Beginn mit der für ein lateinisches Quadrat erwarteten Anzahl an Übereinstimmungen initialisiert wurde.
Allerdings stecken hier zwei Tricks im Detail: der Zähler wurde mit der doppelten Anzahl der erwarteten Übereinstimmungen initialisiert, da die doppelte Anzahl mit weniger Token berechnet werden kann (spart /2), daher wird der Zähler immer um 2 verringert.
Zum anderen wird im Falle einer Übereinstimmung in der selben Zeile, die ja in einem lateinischen Quadrat nicht vorkommen darf, der Zähler um 1000 verringert, einfach um das Ergebnis der Zählung unabhängig von den übrigen Vergleichen in jedem Fall ungleich 0 werden zu lassen (erspart ein if(i % size == j % size) return false).

Bleibt die Frage, welche Anzahl an Übereinstimmungen wir für ein lateinisches Quadrat erwarten können. Alle size Elemente einer Zeile müssen in allen vorangegangenen Zeilen je einmal auftauchen.
Für die lezte Zeile erwarten wir also size*(size-1) Übereinstimmungen. Für die vorletzte Zeile, die ja ebenfalls size Elemente beinhaltet, aber eine Zeile weniger vor sich hat: size*(size-2). Das setzt sich fort bis zur ersten Zeile, die keine vorangehenden Zeilen mehr hat: size*0.
Faktor size ausklammern liefert: size*[(size-1) + (size-2) + ... + 1 + 0]
Die eckige Klammer entspricht der arithmetischen Reihe: die Summe aller Zahlen von 1 bis n ist (n*(n+1))/2, size-1 für n einsetzten: ((size-1)*size)/2, und das in die obige Gleichung eingesetzt liefert eine erwartete Anzahl an Übereinstimmungen in einem lateinischen Quadrat von (size*size*(size-1))/2 = (size^3 - size^2)/2
Auf die halbierung kann - wie bereits oben erwähnt - verzichtet werden, wenn immer doppelt gezählt wird.

Und warum funktioniert das Ganze nur für lateinische Quadrate ? Folgende Überlegungen machen es plausibel (den formalen Beweis überlasse ich David :p ):
1. Wenn mehr als n Symbole verwendet werden, existieren folglich weniger Übereinstimmungen
2. Wenn ein Symbol mehrfach in einer Spalte auftritt, wird die Summe durch -1000 "abgeschossen", die Summe kann nicht mehr 0 und damit das Ergebnis nicht mehr true werden
3. Wenn ein Symbol in einer Zeile mehrfach vorkommt, wird dieses von den vorangegangenen Zeilen gezählt. Darüber hinaus werden die Vorkommen dieses Symbols in den folgenden Zeilen doppelt gezählt, allerdings wird dadurch ein anderes Symbol in den folgenden Zeilen gar nicht gezählt, dieser Teil des Fehlers gleicht sich also potentiell wieder aus.

Ich hoffe, der Ansatz ist klar geworden. Ich ziehe den Hut vor David, für diese Lösung ! Respekt !

grek40

Alter Hase

Beiträge: 1 491

Wohnort: Dresden

  • Private Nachricht senden

93

24.07.2008, 15:11

Hmm... gibt es wirklich keine Möglichkeit nen großes Quadrat zu konstruieren, was durch die -1000 fälschlicherweise als lateinisches Quadrat gewertet wird? :lol:

(ja ich weiss, mit Bruteforcew bis zu 4x4 geht das nich, aber wenns nen großes Quadrat wird vielleicht^^)


// €dit:
das ändert natürlich in der Sache nichts an der genialen Lösung, man müsste halt nur im Fall der Fälle schaun, ob man vielleicht statt der -1000 mit MAX_SQUARE_SIZE bzw. MAX_SQUARE_SIZE_SQ arbeiten müsste um es allgemeingültig richtig zu haben

S.Seegel

2x Contest-Sieger

  • Private Nachricht senden

94

24.07.2008, 16:03

Die -1000 ist ja nicht ganz zufällig gewählt (hoffe ich zumindest ;-)). Damit die Lösung korrekt ist, also im Falle eines mehrfachen Auftretens eines Symbols in einer Spalte die Summe definitiv nicht 0 werden kann, ist es notwendig, die Summe unter 0 zu bringen (da immer subtrahiert wird, eine Summe kleiner 0 also nicht mehr auf 0 gebracht werden kann, einen möglichen int-Underflow für entsprechend groß gewählte MAX_SQUARE_SIZE lassen wir einfach mal außer Acht).
Die "Abschuss"konstante muss also lediglich größer als der maximal erwartete Wert für ein lateinisches Quadrat sein (size^3-size^2, siehe oben). Bei einer MAX_SQUARE_SIZE von 10 bedeutet das > 900.

Helmut

5x Contest-Sieger

Beiträge: 691

Wohnort: Bielefeld

  • Private Nachricht senden

95

25.07.2008, 17:02

Ah, cool, danke für die Erklärung:)

Jetzt macht das alles Sinn. Sicher bin ich mir zwar noch nicht, dass diese Bedingungen wirklich nur für lateinische Quadrate gelten, aber wenns den Brute-force-Test bis Größe 4 geschafft hat, wirds wohl richtig sein..

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

Mordrak

1x Contest-Sieger

Beiträge: 121

Wohnort: München

Beruf: Junior IT Consultant

  • Private Nachricht senden

96

25.07.2008, 20:05

Faszinierend :) Aber jetzt weiss ich nicht ob ich mich ueber den dritten Platz freuen soll oder nicht...

Die Aufgabenkategorie hat es aber auch in sich. Da freut man sich erst wie ein Schnitzel mit einem "tollen" Miniprogramm nur um nach 40 Millionen Zufallstests festzustellen, dass doch noch was falsch laeuft und man muss unter Aechzen und Wehklagen Token um Token hinzufuegen bis es wieder passt....

Gruesse,
Mordrak
What's yellow and equivalent to the axiom of choice? The Lemmon of Zorn!

Helmut

5x Contest-Sieger

Beiträge: 691

Wohnort: Bielefeld

  • Private Nachricht senden

97

29.07.2008, 20:26

Passt jetzt nicht wirklich zum Thread, aber ein neuer würde sich nicht lohnen. Ratet mal, was dieses Programm hier macht:

Quellcode

1
2
3
int f[9814],b,c=9814,g,i;long a=1e4,d,e,h;
main(){for(;b=c,c-=14;i=printf("%04d",e+d/a),e=d%a)
while(g=--b*2)d=h*b+a*(i?f[b]:a/5),h=d/--g,f[b]=d%g;}

(Ist von Arndt/Haenel)
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)

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 195

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

98

01.08.2008, 19:07

Ich melde mich mit diesem Beitrag zurück aus New York City und danke S.Seegel für die ausführliche Erklärung meines Algorithmus :)

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 195

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

99

14.08.2008, 16:17

Zum Wochenende dürft Ihr mit dem 8. Contest rechnen.
Dieser wird, wie ich hoffe, für viele sehr viel interessanter sein als die bisherigen Aufgaben.

Das Gurke

Community-Fossil

Beiträge: 1 999

Wohnort: Pinneberg

Beruf: Schüler

  • Private Nachricht senden

Werbeanzeige