WPC-Aufgabe (Programmierwettbewerb)

er bastelt sich mit den eingesandten Lösung seine eigene Über-Lösung zusammen und gewinnt bei einem völlig anderen Award den großen Geldpreis.

volkard

oder aber schrieb:

er bastelt sich mit den eingesandten Lösung seine eigene Über-Lösung zusammen und gewinnt bei einem völlig anderen Award den großen Geldpreis.

Nein. Jester ist moralisch integer.

interpreter

volkard schrieb:

oder aber schrieb:

er bastelt sich mit den eingesandten Lösung seine eigene Über-Lösung zusammen und gewinnt bei einem völlig anderen Award den großen Geldpreis.

Nein. Jester ist moralisch integer.

Also long hätte ich ihm schon zugetraut.

*push*

wollt ich auch machen

Jester

Sorry, daß das so lange dauert. Ich hatte diese Woche ne Prüfung und hatte damit einiges zu tun. Jetzt sitze ich grad an der Auswertung der Paket-Aufgabe. Ich wundere mich allerdings gerade etwas über die Werte, die ich erhalte.

edit: ich wundere mich nicht über die Ergebniswerte, die sind wohl bei allen korrekt. Eher über die Zeiten.

Jester

Haha, von wegen korrekt. Die Auswertung verzögert sich noch. Eigentlich dachte ich, daß wir alle den gleichen Algorithmus implementiert haben. Haben wir auch, aber irgendwas läuft trotzdem nicht ganz gleich.

Ponto und volkard sind sich eigentlich immer über das Ergebnis einig, weichen jedoch manchmal von dem von mir errechneten Ergebnis nach oben ab. MichaelE stimmt zumeist mit meinen Ergebnissen überein, unterbietet aber manchmal sogar noch.

Ich habe ein relativ kleines Beispiel (169 Zahlen) bei denen ponto und volkard von meinem Ergebnis abweichen. Ich habe aber noch nicht herausgefunden woran es liegt.

MfG Jester

Ponto

Könntest du uns mal das Beispiel geben? Und natürlich deine Vertauschungsfolge.

Jester

Folgende 18 Zahlen:

1561905584 99821026 794649123 128895837 511448469 85153817 320226944 1453410156 535386475 1670238832 1563150800 1480140378 1461781211 408247436 890359276 854389656 1035467383 955468239

Da sind sich die 3 Abgaben einig:
17963139964 kostet es

Nur meine Lösung sagt:
1574317377 soll es kosten

Vermutlich liegt der Fehler dann bei mir, aber ganz sicher bin ich auch nicht...
Mal sehen, wie die dazugehörige Vertauschung aussieht.

Jester wird gewinnen :p

Jester

Habe jetzt noch kürzere Beispiele:

Size: 5
1029501794 1498768723 1651719049 1077302955 736673887 

Disagreement: Jester, 8203988069, MichaelE, 6855716321
result too low

Ponto und volkard stimmen mir hier zu.

Size: 8
1029501794 1498768723 1651719049 1077302955 736673887 1233858148 1590004782 

1412505555 

Disagreement: Jester, 8028732250, ponto, 12323699546
result too high
Disagreement: Jester, 8028732250, volkard, 12323699546
result too high
Disagreement: Jester, 8028732250, MichaelE, 10975427798
result too high

Hier weichen wir irgendwie all ab, nur volkard und ponto sind sich stets einig.
Anzumerken ist vielleicht, daß, wie in diesem Thread schon bemerkt ponto eigentlich falsch rechnet. Er bat allerdings sozusagen außer Konkurrenz mitlaufen zu dürfen, daher habe ich den Typ der Variablen im Code geändert.

Jester

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.

Brutus

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.

Jester

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?

Jester

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.

evilissimo

Hast du die Linien Aufgabe denn schon ausgewertet?

BR