Hallo liebe Lötkolbenschwinger, Programmierfreunde und sonstige
Knobelfans,
das Wetter ist gerade maximal beschissen (trotz Gewitter schwül wie
sau). Was gibt es da besseres als seine eingerosteten Programmierkünste
etwas nachzufeilen?
Da habe ich doch direkt ein nettes kleines Problemchen aufgetan, welches
eigentlich garnicht so tragisch anmutet:
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2795
als PDF:
https://icpcarchive.ecs.baylor.edu/external/47/4794.pdf
Meine CPP-Lösung kommt auf 322 LOC und knapp durchs Zeitlimit (2.8xx
Sekunden), da frage ich mich doch was die geballte Kompetenz hier
zustande bringt und ob Yalu auch hier einen Hammer auspackt der mit
0.xxx läuft. Auch alle anderen sind herzlich eingeladen zu knobeln, zu
tüfteln und zu lösen bei so einem bescheidenen Abend :)
Ich habs noch geschafft die LOC um ein gutes Stück zu reduzieren und den
Algo etwas zu verbessern, aber die Laufzeit liegt noch bei 2,6s.
Fühlt sich jemand bemüßigt und hat ne Idee ob es algorithmisch noch
besser geht oder ob nur noch Optimierungspotenzial in den verwendeten
Datenstrukturen liegt, da map, set, etc und Objekte ja doch etwas
Laufzeit kosten, aber auf Pure C habe ich da keinen Bock.
Source siehe Anhang.
D. I. schrieb:> Yalu, bist du im Urlaub :D
Nein, nein, keineswegs :)
Deinen ersten Beitrag habe ich schlicht übersehen, beim zweiten habe ich
(wieder einmal) erfolglos versucht, mich bei icpcarchive.ecs.baylor.edu
zu registrieren (eine Anfrage diesbezüglich blieb bisher unbeantwortet),
dann habe ich gesehen, dass es dieselbe Aufgabe auch auf
uva.onlinejudge.org gibt, habe dort eine Lösung und ein paar optimierte
Derivate davon eingereicht, die aber alle das Zeitlimit überschritten.
Zudem habe ich im Moment gerade etliche andere Dinge zu tun
(Autoschrauben, Fahrradschrauben, Backen, geschraubtes Fahrrad benutzen
usw.).
Ich werde aber die Knobelei auf all meinen Wegen mit mir herumtragen.
Außerdem esse ich gerade Schokolade, um einen besseren Bezug zum Problem
zu bekommen. Irgenwann kommt dann sicher der Geistesblitz, wie man den
Algorithmus noch um ein paar Größenordnungen beschleunigen kann :)
Deinen Algorithmus werde ich mir erst anschauen, wenn wenigstens einer
meiner Versuche akzeptiert worden ist. Vielleicht können wir dann unsere
Ideen vereinen und damit den Highscore knacken :D
Hast du vielleicht noch ein paar gute Testcases? Meine eigenen sind zu
leicht und werden alle im zweistelligen Millisekundenbereich gelöst. Da
ist es schwer, Ansatzpunkte für eine Optimierung zu finden, zumal ich
natürlich auch keine Ahnung habe, um wieviel mein aktueller Algorithmus
zu langsam ist.
Yalu X. schrieb:> Deinen ersten Beitrag habe ich schlicht übersehen, beim zweiten habe ich> (wieder einmal) erfolglos versucht, mich bei icpcarchive.ecs.baylor.edu
Das ist sehr merkwürdig, Typo in der Mailadresse? Welcher Mailanbieter?
Mails brauchen dort ewig bis sie benatwortet werden, evtl ne andere
Adresse versuchen.
Yalu X. schrieb:> Ich werde aber die Knobelei auf all meinen Wegen mit mir herumtragen.> Außerdem esse ich gerade Schokolade, um einen besseren Bezug zum Problem> zu bekommen. Irgenwann kommt dann sicher der Geistesblitz, wie man den> Algorithmus noch um ein paar Größenordnungen beschleunigen kann :)
:)
Yalu X. schrieb:> Deinen Algorithmus werde ich mir erst anschauen, wenn wenigstens einer> meiner Versuche akzeptiert worden ist. Vielleicht können wir dann unsere> Ideen vereinen und damit den Highscore knacken :D
Sehr löblich, ja wenn dus raus hast bin ich sicher kann man noch was
machen.
Yalu X. schrieb:> Hast du vielleicht noch ein paar gute Testcases? Meine eigenen sind zu> leicht und werden alle im zweistelligen Millisekundenbereich gelöst. Da> ist es schwer, Ansatzpunkte für eine Optimierung zu finden, zumal ich> natürlich auch keine Ahnung habe, um wieviel mein aktueller Algorithmus> zu langsam ist.
Also ein TC der mir gereicht hat mich ins TL laufen zu lassen war:
Yalu X. schrieb:> habe dort eine Lösung und ein paar optimierte> Derivate davon eingereicht, die aber alle das Zeitlimit überschritten.
Wie lautet denn deine aktuelle Lösung, rein interessehalber? Also die
algorithmische Idee, nicht den Source :)
D. I. schrieb:> Also ein TC der mir gereicht hat mich ins TL laufen zu lassen war:> 15> 10 12> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15> 0
Lag das vllt. daran, dass es dafür keine Lösung gibt?!
S. J. schrieb:> D. I. schrieb:>> Also ein TC der mir gereicht hat mich ins TL laufen zu lassen war:>> 15>> 10 12>> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15>> 0>> Lag das vllt. daran, dass es dafür keine Lösung gibt?!
Auch ein Aspekt, ja. Aber in meiner Lösung rührte der TLE daher, dass
ich eine Optimierung gemacht habe die dann doch keine war :)
So, ich habe gestern meinen Algorithmus umgeschrieben, so dass er jetzt
effizientere Datenstrukturen benutzt. Zusammen mit ein paar weiteren
Optimierungen läuft er im UVA-Online Judge in 0,482s, was immerhin für
die Top 20 gereicht hat :)
Aber:
Beim Versuch, das Ganze weiter zu optimieren, erhielt ich eine "Wrong
Answer"-Meldung und habe den Verdacht, dass schon die vorige Version
fehlerhaft war, der Fehler aber bei der Ausführung auf dem UVA-Server
durch (un-)glückliche Umstände nicht aufgetreten ist :(
Ich werde heute Abend versuchen, den Fehler zu beheben und dann noch
Informationen zum Algorithmus liefern.
Sry hier den Thread so zu stören aber da hier im Moment die richten
Leute unterwegs sind:
Hat jemand ne Buchempfehlung zu Algorithmik in C++?
C und C++ behersche ich bereits mehr oder weniger. Da aber der größte
Teil über learning-by-doing gelaufen ist fehlt mir etwas der Blick dafür
effiziente Algorythmen zu finden und wie ich Lösungen optimiere und
bessere Strukturen wähle.
Das Buch sollte aber schon bei den Grundlagen der Algorithmik anfangen,
da es bei Bubblesort bei mir schon wieder aufhört mit dem Wissen.
Ich verstehe das Rätsel nicht richtig.
Eine Tafel Schokolade soll so unter Leuten aufgeteilt werden, daß jeder
die gewünschte Anzahl Stücke erhält. Das kann doch nicht funktionieren,
wenn einer nur ein Stück möchte und ein Vielfraß den Rest verschlingt.
Ich habe mir das übersetzen lassen, aber so richtig klar wird die
Aufgabe
nicht.
Das geht offenbar nicht nur mir so, denn sonst wäre die Beteiligung an
der Lösung doch viel größer.
MfG Paul
Moin,
ich habe auch mal mitgemacht.
Da bei icpcarchive.ecs.baylor die Registrierung nicht klappt, bin ich
nun auch auf UVa:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=problem_stats&problemid=3540&category=.
Meine Implementierung scheint gut auf die Testsuit abgestimmt zu sein.
:-)
Wer noch Test Cases sucht, ich habe ein paar generiert (Anhang).
Grüße, mikro
btw: Der (nicht lösbare) Test Case von D. I. hat mich fast zu
Verzweiflung getrieben: Da gibt es scheinbar sehr viele Kombinationen.
Paul Baumann schrieb:> Ich verstehe das Rätsel nicht richtig.
DAs Problem ist, dass du keine Ecken Rausbrechen darfst, und jeder die
geforderte Stückzahl in Form eines zusammenhängenden
Schokoladentafelstücks will.
das heißt du darfst jemanden, der 4 Stück will nicht (2x 1x2) oder (1x3
+ 1x1) geben, sondern entweder 1x4 oder 2x2.
Das Problem besteht also darin, die Tafel so aufzuteilen, dass sie mit
geraden Bruchkanten in die geforderten Stücke zerlegt werden kann.
(bzw zu entscheiden, ob dies möglich ist, oder nicht)
S. J. schrieb:> Meine Implementierung scheint gut auf die Testsuit abgestimmt zu sein.> :-)
Top 1 zu machen ist mal ein Statement, Respekt! Wie lang hast du
getüftelt?
S. J. schrieb:> Da bei icpcarchive.ecs.baylor die Registrierung nicht klappt, bin ich> nun auch auf UVa:
Ah, dann habe also nicht nur ich das Problem :)
> Meine Implementierung scheint gut auf die Testsuit abgestimmt zu sein.> :-)
Mist! Mein Ziel für heute Abend war, meinen Algorithmus noch einmal um
den Faktor 2 zu beschleunigen, dann wäre ich mit 2,4s auf Platz 1
gelandet. Jetzt muss ich mich schon deutlich mehr anstrengen, und die
Hoffnung sinkt gewaltig ;-)
Auf jeden Fall herzlichen Glückwunsch zur Verbesserung des bestehenden
Rekords um fast Faktor 2 :)
Wenn sich noch 17 weitere mikrocontroller.net-Teilnehmer aufraffen,
schaffen wir es vielleicht, die Hiscore-Liste komplett zu erobern :D
> Wer noch Test Cases sucht, ich habe ein paar generiert (Anhang).
Danke, die Beispiele werde ich mal testen. Ich habe zwar mittlerweile
auch einen einfachen Testgenerator gebastelt, aber inzwischen sind die
damit generierten Beispiele schon wieder zu leicht :)
> btw: Der (nicht lösbare) Test Case von D. I. hat mich fast zu> Verzweiflung getrieben: Da gibt es scheinbar sehr viele Kombinationen.
Die Zeit dafür liegt bei meinem Algorithmus im Millisekundenbereich.
Wenn man das Einlesen und Ausgeben der Daten nicht mitrechnet, sind es
sogar nur etwa 14µs (auf einem alten PC) :)
Das Beispiel ist aber auch wirklich einfach. Viel schwieriger ist es,
aus einer 10×12-Tafel ein rechteckiges Stück mit 13 Feldern
herausbrechen ;-)
Ist an euren Algorithmen grundlegend was anders als bei mir oder
"beschränken" sich eure Optimierung auf effizienteres Ausschließen von
unmöglichen Fällen. Eine offensichtliche Optimierung, die ich bei mir
sehe ist die Teilmengen effizienter zu generieren.
Ich hätte da noch ein Aufgäbchen, die erstmal garnicht so schwer
scheint, aber da fehlt mir noch die Idee, zumindest erscheint sie mir
dann doch nicht so einfach.
Aber ich stelle sie einfach mal zur Disposition:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=257&page=show_problem&problem=3535
Ist sogar aus demselben Wettbewerb.
Paul Baumann schrieb:> Ich verstehe das Rätsel nicht richtig. Eine Tafel Schokolade soll so> unter Leuten aufgeteilt werden, daß jeder> die gewünschte Anzahl Stücke erhält. Das kann doch nicht funktionieren,> wenn einer nur ein Stück möchte und ein Vielfraß den Rest verschlingt.
Genau. Du hast die Aufgabe also offensichtlich doch verstanden.
Ein einfaches Beispiel wäre: Eine klassische 6×4-Tafel imit 24 Feldern
und zwei Esser. Der eine will 23 Felder, der andere soll nur eins
bekommen. Das geht mit einem geradlinigen Bruch nicht, also muss das
Programm ausgeben:
1
Case 1: No
Möchte aber der eine 8 Felder und der andere 16, ist das kein Problem,
also
@Vlad & Yalu
Ich bedanke mich für Eure Erklärungen und Ausführungen.
Yalu schrub:
>Viel schwieriger ist es,>aus einer 10×12-Tafel ein rechteckiges Stück mit 13 Feldern>herausbrechen ;-)
Ja, soweit war ich vorhin auch schon einmal, als ich versuchte, einen
Algorithmus dafür auf Kästchenpapier durchzuspielen....
Das ist wirklich eine harte Nuss, die mich zu der Überlegung brachte,
Gästen nur ein Glas Nutella und einen Löffel zur Verfügung zu stellen.
;-)
MfG Paul
D. I. schrieb:> Ist an euren Algorithmen grundlegend was anders als bei mir oder> "beschränken" sich eure Optimierung auf effizienteres Ausschließen von> unmöglichen Fällen.
Im Prinzip passiert bei mir genau das. Und es sind nicht einmal arg
viele Kriterien, die dabei berücksichtigt werden. Allerdings verwende
ich noch Tabellen, um Dinge möglichst nicht mehrfach berechnen zu
müssen. So etwas verwendest du aber teilweise auch, wie ich gerade
gesehen habe.
> Eine offensichtliche Optimierung, die ich bei mir> sehe ist die Teilmengen effizienter zu generieren.
Die Teilmengengenerierung ist bei mir seit gestern so ultraeffizient,
dass ein Gelegenheits-C-Programmierer kaum eine Chance hat, sie auf
Anhieb zu verstehen ;-)
Es ist tatsächlich so, dass pro Testfall etwa 95% der Rechenzeit in
einen einzigen memset-Aufruf verbraten wird, der zu Beginn des
Algorithmus eine größeres Array mit Nullen belegt. Gestern Abend gelang
es mir, die Größe dieser Tabelle durch dichteres Packen der Inhalte zu
halbieren, was sofort eine Verringerung der Laufzeit von 0,9s auf unter
0,5s bewirkte. Aber dazu heute Abend mehr.
Paul Baumann schrieb:> Das ist wirklich eine harte Nuss, die mich zu der Überlegung brachte,> Gästen nur ein Glas Nutella und einen Löffel zur Verfügung zu stellen.
1 Glas und 1 Löffel für n Gäste? Wenn das nicht Tote und Verletzte
gibt :)
@D. I.:
Ich habe gerade mal kurz deinen Code überflogen. Er entspricht in vielen
Punkten dem meinigen. Du hast in computeHeight ein paar überflüssige
Berechnungen und Abfragen drin, so z. B.
if(possibleSize%width==0&&complimentarySize%width==0)// nur rechter Operand von &&
6
7
if(possibleSize%height==0&&complimentarySize%height==0)// nur rechter Operand von &&
Diese Abfragen sind immer wahr, wenn das Programm ansonsten korrekt ist.
Ich habe ähnliche Abfragen als Asserts eingebaut, um potentielle Fehler
aufzudecken, sie hinterher aber wieder entfernt.
Dass deine Teilmengengenerierung nicht optimal ist, hast du ja schon
geschrieben:
Wenn nur das erste und das letzte Element in der Menge enthalten sind,
macht die Schleife 16381 unnötige Durchläufe, in denen zwar nicht viel
gerechnet wird, aber in Summe doch einiges an Rechenzeit verbraten wird.
Dann scheint es so, dass du bei der Aufteilung der Menge in Teilmenge
und Komplementärmenge nicht berücksichtigst, dass die beiden
austauschbar sind. So hast du pro Rekursionsebene den doppelten Aufwand,
da jede Teilmenge in einem anderen Schleifendurchlauf als
Komplementärmenge auftaucht.
Ich habe zusätzlich noch folgende Features eingebaut:
Wenn der größte Primfaktor eines Zielstücks größer als die Länge und
Breite eine Tafelstücks ist, kann es nicht aus diesem herausgebrochen
werden. Man kann also an dieser Stelle die Rekursion abbrechen. Diese
größten Primfaktoren werden natürlich für jede mögliche Teilmenge
vorausberechnet.
Die Teilegrößen werden vorsortiert. Wenn die größten Zielstücke zuerst
bearbeitet werden, treten potentielle Sackgassen tendenziell schon in
den höheren Rekursionsebenen auf, was unnötig tiefes Absteigen in den
Suchbaum vermeidet. Der mittelere Gewinn dieser Maßnahme (etwa 30%) ist
aber geringer, als ich ewartet hatte.
Bei der horizontalen und vertikalen Teilung der Tafel kann man sich eine
von beiden sparen, wenn die Tafel quadratisch ist. Das bringt auch nicht
viel, kostet aber auch fast nichts.
Das Ergebnis jeder geprüften Teilmenge und Tafelgeometrie wird in einer
Tabelle abgelegt. Jeder Eintrag dieser Tabelle ist 2 Bits groß, um die
drei Zustände "unbekannt", "unlösbar" und "lösbar" zu speichern. Es gibt
maximal 2¹⁵·(100·(100+1)/2+100)≈1.7E8 Einträge. Tafelgeometrien mit
vertauschter Länge und Breite belegen dabei den gleichen Eintrag. Um die
Indizes leicht aus der Teilmenge und der Tafelgeometrien berechnen zu
können, werden diese zusammen als 15+13-Bit-Zahl codiert. Damit hat die
Tabelle eine Größe von 64 MiByte, weswegen das Löschen so lange dauert.
Ich habe aber mittlerweile festgestellt, dass von den 1.7E8 Einträgen im
Mittel nur ein paar Hunderttausend belegt werden, so dass man mit einer
anderen Datentstruktur (evtl. Hash-Table) trotz der etwas längeren
Zugriffszeiten in Summe besser liegt.
Und die Schleife zur Generierung aller möglichen Paare aus Teil- und
Komplementärmenge sieht bei mir so aus:
Das ist die etwas kürzere und obfusziertere Variante, von der ich
ursprünglich glaubte, dass der Compiler daraus maximal schnellen Code
generiert. Sie ist aber (zumindest theoretisch) nicht portabel, weil sie
die Darstellung negativer Zahlen im Zweierkomplement voraussetzt. Die
portable, aber immer noch ausreichend undurchsichtige Variante habe ich
verschlampt, kann sie aber bei Bedarf noch einmal aus irgendwelchen
Schmierzetteln rekonstruieren. Sie hat ein paar Zeichen mehr Quellcode,
der GCC erzeugt daraus aber exakt den gleichen, effizienten
Assembler-Code (was beweist, dass er diesen kryptischen Code
tatsächlich verstanden hat).
Ich habe noch ein paar andere Dinge ausprobiert:
Die Teilung in jedem Rekursionsschritt wird erst in Längs- und dann in
Querrichtung gemacht, in der Hoffnung, dass dies einen ähnlich positiven
Effekt wie die Vorsortierung (s.o.) hat.
Bei der Rekursion wird die kleinere der beiden Teilmengen (oder auch die
kleinere der beiden Tafelteile) zuerst bearbeitet.
Gebracht hat das aber außer LOCs so gut wie nichts.
Ich habe noch ein paar weitere Ideen im Hinterkopf, die ich aber heute
wahrscheinlich nicht mehr testen werde. Jetzt wird erst einmal gegessen
:)
Danke Yalu für deinen ausführlichen Post. Nicht alle aber einige Ideen
davon hatte ich auch, aber mir hat dann der sportliche Ehrgeiz gefehlt
die noch zu Coden nachdem das Problem mit dem eigentlichen Algorithmus
gelöst war, aber trotzdem sehr cool.
Yalu X. schrieb:> Und die Schleife zur Generierung aller möglichen Paare aus Teil- und> Komplementärmenge sieht bei mir so aus:> set1 = set & ~-set;> for (subset = -set1 & set1; subset; subset = -(~subset & set1) & set1)> {> complset = set ^ subset;> ...> }
Das wiederrum war sehr lehrreich und bis dato die absolut kaputteste Art
Bit-Teilmengen zu erzeugen, die ich je gesehen habe.
Entgegen meiner Aussage von oben ist diese Version sogar etwas schneller
(1 Instruktion weniger in der Schleife), da der konstante Ausdruck ~set1
vor der Schleife berechnet wird.
Wäre ich noch WiMi und Klausuraufgaben stellen, wär das ein toller
Kandidat für die 1er Bremse ;)
Jetzt betätige ich mich erstmal wie vor ein paar Posts erwähnt als
Kanalgräber, was sich als deutlich kniffliger erweist als als
Schokoladenbrecher... :/ das wird wohl ne kurze Nacht.
Hallo,
ich habe mir gerade D.I.s Quelltext angeguckt. Offensichtlich benutzen
wir alle den gleichen Ansatz.
Das mit den Bitfeldern ist ne hübsche Idee. Allerdings braucht man nicht
wirklich alle Kombinationen. Ich benutze einen Zähler, der durch die
notwendigen Kombinationen läuft. Solange das Problem lösbar ist, bringt
das möglicherweise einen Vorteil.
Zum Speichern meiner Zwischenergebnisse habe ich einige Varianten
probiert. Letztendlich war eine klassische Hash-Table (Kollisionen
werden entfernt und ggf. später wieder neu berechnet) am effizientesten.
Die Performance von Maps, Multimaps und Hashed Lists liegt aber auch
nicht so weit weg.
Um die Komplexität des Alorithmus zu verringern, müßte man imho iwie die
Teilergebnisse in den Algorithmus einfließen lassen (also eben nicht
über Lookup). Da fällt mir aber auf Anhieb nicht ein, wie man das
sinnvoll lösen könnte (falls es überhaupt möglich ist).
Meine submitteten Code habe ich mal angehangen. Ist relativ lang und
mehr oder weniger dokumentiert. Ist auch noch Debug Zeugs drin. 4%
Performancegewinn sind drin, wenn der Zähler die Chunk Size mitzählt
(ohne Compileroptimierung sind es gar 20%).
Grüße, mikro
Yalu X. schrieb:> Beim Versuch, das Ganze weiter zu optimieren, erhielt ich eine "Wrong> Answer"-Meldung und habe den Verdacht, dass schon die vorige Version> fehlerhaft war, der Fehler aber bei der Ausführung auf dem UVA-Server> durch (un-)glückliche Umstände nicht aufgetreten ist :(
Ich habe den Fehler nun behoben. Es war natürlich, wie so oft, ein ganz
dummer. Ihn zu finden hat aber trotzdem unendlich viel Zeit gekostet,
weil er bei meinen eigenen Testfällen nicht auftrat und ich ihn nur
durch entsprechend viele Testläufe auf dem Online-Judge eingrenzen
konnte.
Yalu X. schrieb:> Ich habe aber mittlerweile festgestellt, dass von den 1.7E8 Einträgen im> Mittel nur ein paar Hunderttausend belegt werden, so dass man mit einer> anderen Datentstruktur (evtl. Hash-Table) trotz der etwas längeren> Zugriffszeiten in Summe besser liegt.
Der Cache ist jetzt als Hash-Tabelle mit 512ki Einträgen realisiert.
Beides zusammen reduziert die Laufzeit auf 0,086s.
Den aktuellen Quellcode habe ich angehängt.
Yalu X. schrieb:> Den aktuellen Quellcode habe ich angehängt.
Wer braucht schon CleanCode :) 86ms ist klasse und der Code ist wirklich
kurz und knackig. Mich würden original Contestlösungen interessieren.
Soweit ich mich erinnern kann wurde diese Aufgabe nach 55 Min gelöst.
Also zwischen Conteststart damals bis zur korrekten Lösung im Contest
brauchte es nur 55 Min.
Thread beobachten
Seitenaufteilung abschalten