WPC-Aufgabe (Programmierwettbewerb)
-
So, hab's gelöst. Ich hatte einen Rechenfehler in meiner Implementierung. Nunerhalte ich die gleichen Ergebnisse wie volkard und ponto. Die Lösung von volkard ist damit die einzige vollständig korrekte Einsendung.
Pontos Lösung mußte ich zuvor ja noch korrigieren. MichaelEs Lösung liefert falsche Ergebnisse. Also hat volkard als einziger eine vollständig korrekte Lösung abgeliefert.
Das offizielle Endergebnis sieht also so aus:
1. Volkard
Meinen Glückwunsch an den Sieger.
Laufzeitmäßig ist volkards Lösung am schnellsten. MichaelEs Lösung liegt dort trotz der eigentlich quadratischen Laufzeit garnicht so schlecht (meine Eingaben sind ja zufällig generiert) und braucht für meine Eingaben etwa doppelt so lange wie volkard. Ponto ist dabei stark abgeschlagen, woran das liegt kann ich nur spekulieren. Vermutlich an seinem Cache-unfreundlichen Zugriff auf das Datenarray.
Hier noch der Siegercode:
u64 wpc_expert(std::vector<unsigned int> const& weights){ u64 result=0; //geschenke kopieren in meine kleine liste, die sich die //ursprüngliche platznummer zu jedem geschenk merkt. size_t size=weights.size(); vector<Geschenk> geschenk(size); for(size_t i=0;i!=size;++i){ geschenk[i].gewicht=weights[i]; geschenk[i].platz=i; } //sortieren sort(geschenk.begin(),geschenk.end()); //kleinstes gewicht überhaupt merken u64 globalMin=geschenk[0].gewicht; //jetzt kann ich anhand der platznummern die zyklen erkennen for(size_t start=0;start!=size;++start){ if(geschenk[start].platz!=start){ // cout<<geschenk[start].gewicht<<' '; unsigned int min=geschenk[start].gewicht; size_t len=1; u64 sum=min; size_t ende=geschenk[start].platz; geschenk[start].platz=start; while(ende!=start){ // cout<<geschenk[ende].gewicht<<' '; if(geschenk[ende].gewicht<min) min=geschenk[ende].gewicht; sum+=geschenk[ende].gewicht; size_t neuEnde=geschenk[ende].platz; ++len; geschenk[ende].platz=ende; ende=neuEnde; }while(ende!=start); // cout<<" "<<len<<' '<<min<<' '<<sum<<'\n'; //so, jetzt habe ich vom zyklus die laenge, die summe das minimum. //nun kommt die überlegung. //der weihnachtsmann arbeitet immer zyklus nach zyklus ab. //dabei macht er einen polygontausch. pfiffigerweise beginnt er dabei //mit dem leichtesten geschenk im zyklus. dadurch hebt er immer das //leichteste und das, was auf seinen zielplatz kommt. //er macht also len-1 vertauschungen, jeweils das leichteste und //ein anderes. u64 arbeitOhneTrick=sum+(len-2)*u64(min); //machmal kommt es vor, daß es ein trick es noch leichter macht. //beispiel: 1 32 33 34 31 //hier hat er nur den zyklus 32 33 34 31 zu vertauschen, aber das //kostet so zu viel. wenn er zuerst die 31 mit der 1 vertauscht, //kann er dann 34, 33, 32 und 31 mit 1, hat er so viel arbeit gespart, //daß es sich gelohnt hat, das leichte paket zu benutzen und mehr als //die minimale anzahl an vertauschungen durchzuführen. u64 arbeitMitTrick=sum+min+(len+1)*globalMin; if(arbeitOhneTrick<arbeitMitTrick) result+=arbeitOhneTrick; else result+=arbeitMitTrick; } } return result; }Wer die funktionsweise verstehen will, sollte sich das vielleicht einfach mal bei nem kleinen Array veranschaulichen. Lohnend dürfte auch eine google-Suche mit den Begriffen Permutation und Zykel/Zykelzerlegung sein.
-
Wann denkst du, bist du mit der Auswertung der anderen Aufgabe fertig?
-
Könntet ihr mal folgendes einbauen, damit man die Ergebnisse überprüfen kann.
class Verifier { struct SwapPair { size_t p1; size_t p2; }; std::vector<SwapPair> swaps; public: void add(size_t p1, size_t p2) { SwapPair sp; sp.p1 = p1; sp.p2 = p2; swaps.push_back(sp); } bool isOK(std::vector<unsigned int> const& weights, u64 calculatedSum) { u64 sum = 0; std::vector<unsigned int> sorted; sorted.resize(weights.size()); for(size_t i=0;i<weights.size(); i++){ sorted[i]=weights[i]; } for(size_t s=0;s<swaps.size();s++) { unsigned int h = sorted[swaps[s].p1]; sum+= h+sorted[swaps[s].p2]; sorted[swaps[s].p1]=sorted[swaps[s].p2]; sorted[swaps[s].p2]=h; } if(calculatedSum!=sum) { std::cout<<"Error: sum="<<sum<<" calculated="<<calculatedSum<<"\n"; return false; } for(size_t t=0;t<sorted.size()-1;t++){ std::cout<<sorted[t]<<" "<<sorted[t+1]<<" "; if(sorted[t]>sorted[t+1]) { std::cout<<"Error: pos ("<<t<<"/"<<t+1<<")\n"; return false; } } return true; } };Einfach jedes Packetpaar, dass getauscht wird mit add(...) hinzufügen und am Schluss isOK mit der zu sortierenden Liste und dem berechnetem Ergebnis aufrufen.
-
Volkard ist und bleibt der Godfather of Coding
-
Glückwunsch.
-
Der angegebene Testcode läßt sich nicht gut einbauen, weil wir die Folgen nicht wirklich sortieren (ich zumindest nicht). Es werden nur die nötigen Kosten berechnet. Ich bin mir aber sehr sicher, daß die Implementierungen korrekt sind.
Für kleine Beispiele habe ich auch eine A*-Suche implementiert, die liefert die gleichen Ergebnisse. Allerdings ist sie zu Rechen- und Speicheraufwendig um richtige Beispiele damit durchzurechnen (ist auch etwas ungeschickt implementiert).
-
Es haben nur 3 Leute mitgemacht?
-
Bei der Experten-Aufgabe, ja. Bei der Linienaufgabe genauso.
Ursprünglich hatten sich noch mehr Leute daran versucht, aber nachdem wohl einige Algorithmen fehlerhaft waren haben sich manche entmutigen lassen. Schade eigentlich.
-
Hast du die Linien Aufgabe denn schon ausgewertet?
BR
-
Nur 3 Leute bei der Linienaufgabe? Hat thomas001 nicht abgegeben? Oder hat ness nicht abgegeben?
-
Ups, sind 4 Einsendungen.
Auswertung dazu kommt auch bald.
-
Hm, was mach ich nun mit der Streckenaufgabe?
Point origin(0,0); Point middle(1,1); Point end(2,2); Line line1(origin, middle); Line line2(middle, end); std::vector<Line> lines; lines.push_back(line1); lines.push_back(line2); cout << wpc_pro(lines) << endl;Da sind sich die Herren alle einig: 0 soll die Anzahl der Schnittpunkte sein.
Was nun?
-
Ist 0 das falsche Ergebnis?
-
Jester schrieb:
Hm, was mach ich nun mit der Streckenaufgabe?
Point origin(0,0); Point middle(1,1); Point end(2,2); Line line1(origin, middle); Line line2(middle, end); std::vector<Line> lines; lines.push_back(line1); lines.push_back(line2); cout << wpc_pro(lines) << endl;Da sind sich die Herren alle einig: 0 soll die Anzahl der Schnittpunkte sein.
Was nun?
Is'n Berührpunkt.
-
imho ist das ein Schnittpunkt.
Damit ich aber trotzdem was tun habe werde ich alle Punkte paarweise verschieden wählen. Dadurch kann dieser Fall nicht auftreten.
-
Lustig :p
Ich bin froh das wir alle das gleiche ergebniss haben *g*
-
Laut Wikipedia ist es ein Berührpunkt, wenn die erste Ableitung identisch ist (also eine Funktion die andere tangiert). { (1, 0), (1, 1) } { (2, 1), (1, 1) } dürften sich demzufolge beispielsweise schneiden. Wenn die teilnehmenden Programme so etwas sehen, musst du keine paarweise verschiedenen Punkte nehmen.
In jedem Fall würde es mich aber interessieren, ob die Einsendungen so einen Fall erkennen würden.
-
Das erkennen sie vermutlich.
Wobei mir nicht klar ist, von welchem Ableitungsbegriff Du sprichst. Wenn ich die Linien senkrecht nach oben mache kannste den normalen Ableitungsbegriff nicht benutzen.
Ist ein Berührpunkt nicht sowieso auch ein Schnittpunkt?
edit: Wikipedia sagt: ja
Wikipedia schrieb:
Ein Schnittpunkt ist in der Mathematik ein gemeinsamer Punkt zweier Kurven. Haben beide Kurven in ihrem gemeinsamen Punkt die gleiche Tangentensteigung, so spricht man von Berührungspunkt.
-
Wikipedia schrieb:
Ein Schnittpunkt ist in der Mathematik ein gemeinsamer Punkt zweier Kurven. Haben beide Kurven in ihrem gemeinsamen Punkt die gleiche Tangentensteigung, so spricht man von Berührungspunkt.
klingt logisch
-
http://de.wikipedia.org/wiki/Diskussion:Schnittpunkt
Wikipedia Diskussion schrieb:
Er bezeichnet einen Punkt, in dem sich zwei oder mehrere gerade oder gebogene Linien überkreuzen.
Eine tangentiale Berührung wird im Allgemeinen nicht als Schnittpunkt bezeichnet.
Die scheinen sich da aber auch nicht so sicher zu sein, so wie es aussieht ^^