WPC-Aufgabe (Programmierwettbewerb)

Wer hat abgegeben?

Ponto

Hier ist meine Abgabe für die Sortieraufgabe. Bin mir aber über die Korrektheit nicht klar geworden, kann also falsch sein.

http://www.pontohonk.de/wpc/wpc-sorting.C

volkard

hier meine:

#include <vector>
#include <algorithm>
//#include <iostream>
using namespace std;

struct Geschenk{
	unsigned int gewicht;
	size_t platz;
	friend bool operator<(Geschenk const& a,Geschenk const& b){
		return a.gewicht<b.gewicht;
	}
};

typedef unsigned long long u64; 
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;
}

wir haben das gleiche verfahren.

habe mich übrigens gegen

for (SizeType i = 0; i != size; ++i) pos[i] = i;
   std::sort(pos.begin(), pos.end(), Sorter(weights));

entschieden, weil da die zugriffe während des sortierens zu durcheinander sind. ich befürchte, das macht der cache nicht mit.

total_weight += weights[i];

in der innersten schleife wollte ich das ergebnis nicht anfassen, da es bestimmt nicht gut in ein register gesteckt werden kann. hab deswegen den zyklus noch auf ne lokale variable sum aufsummiert. eigentlich unangebracht und dein code ist hübscher.

u64 s1 = (amount - 2) * min;
      u64 s2 = (amount + 1) * M + min;

das ist bitter. bei nem großen zyklus kriegste einen überlauf, weil amount und min nur 32-bitter sind.

std::swap(cur, pos[cur]);

lol. ich hab

size_t neuEnde=geschenk[ende].platz;
				geschenk[ende].platz=ende;
				ende=neuEnde;

geschrieben und nicht bemerkt, daß die folge von zuweisungen einfach nur die beiden vertauscht.

evilissimo

Meine WPC Pro ( die Linien ) Lösung ist folgende ( falls es überhaupt jemanden interessiert *g* )

http://www.evilissimo-softdev.de/wpc/wpc_pro.html

BR

evilissimo

Michael E.

volkard: Ich hab denselben Ansatz:

#include <algorithm>

struct Packet
{
public:
    Packet(bool unhandled, std::size_t index, unsigned int weight)
        : unhandled_(unhandled), index_(index), weight_(weight)
    {
    }

    bool unhandled_;
    std::size_t index_;
    unsigned int weight_;
};

bool operator< (const Packet &lhs, const Packet &rhs)
{
	return lhs.weight_ < rhs.weight_;
}

class UnhandledPacketFind
{
public:
    bool operator() (const Packet &elem)
    {
    	return elem.unhandled_;
    }
};

typedef std::vector<Packet> PacketList;

u64 wpc_expert(std::vector<unsigned int> const& weights)
{
	PacketList packets;

	for(std::size_t i = weights.size(); i > 0; --i)
        packets.push_back(Packet(true, i-1, weights[i-1]));

    std::sort(packets.begin(), packets.end());

    u64 weight = 0;

    PacketList::iterator iter;
    int counter;
    PacketList::difference_type startPos;
    unsigned int minWeight;
    unsigned int totallyMin = (std::min_element(packets.begin(), packets.end()))->weight_;

    while(true)
    {
    	iter = std::find_if(packets.begin(), packets.end(), UnhandledPacketFind());

    	if(iter == packets.end())
            break;

    	counter = 0;
    	startPos = iter - packets.begin();
    	minWeight = iter->weight_;

        do
        {    
            iter->unhandled_ = false;
            ++counter;
            weight += iter->weight_;
            minWeight = std::min(minWeight, iter->weight_);

            iter = packets.begin() + iter->index_;
        }
        while(iter - packets.begin() != startPos);

        if(counter != 1)
            weight += (counter - 2) * minWeight;
        else
            weight -= minWeight;

        if(counter > 3 && (counter + 1) * totallyMin < (counter - 3) * minWeight)
            weight -= (counter - 3) * minWeight - (counter + 1) * totallyMin;
    }

    return weight;
}

Ponto

volkard schrieb:

hier meine:
u64 s1 = (amount - 2) * min;
      u64 s2 = (amount + 1) * M + min;
das ist bitter. bei nem großen zyklus kriegste einen überlauf, weil amount und min nur 32-bitter sind.

Jetzt wo du es so sagst. Irgendwie hab ich immer so einen Klotz drin.

Ansonsten kann ich nur sagen:

1. Ich hab mich für die Sortierung der Indizes entschieden, um den Overhead auf n*sizeof(SizeType) + Konstante zu bringen.
2. Ich hatte auch ursprünglich eine lokale Summe in der Schleife. Da der Code so aber kürzer ist, hab ich die Summe rausgeschmissen. Hat auf meiner Testplatform nichts an Laufzeit gekostet.
3. Den Swap hab ich auch erst bemerkt, als ich versuchte den Code sinnvoll klein zu kriegen.

Ponto

Michael E. schrieb:

iter = std::find_if(packets.begin(), packets.end(), UnhandledPacketFind());

Macht das das ganze nicht quadratisch? Wenn du n/2 benachbarte Zweierzykel hast, machst du dann nicht n/2 Suchen der Längen 1, 3, 5, ...?

Brutus

Meine ist evilissimos Lösung sehr ähnlich, nur ist seine schneller

Wen's interessiert, meine Lösung + 2 andere Ansätze, einer von Sedgewick: http://rafb.net/paste/results/ksWPX366.html

Jester

Stimmt,

iter = std::find_if(iter, packets.end(), UnhandledPacketFind());

wäre linear gewesen. Böse STL, man schreibt eine Zeile mit nem falschen Parameter und fängt sich ne teure Schleife ein.

MfG Jester

Michael E.

*heul* Darf doch net wahr sein, in meinen Vorüberlegungen hab ich sogar noch dran gedacht

evilissimo

Und wie stehts mit der Auswertung?

BR

evilissimo

Jester

Bitte entschuldigt, die Wartezeit. Ich bin leider noch nicht dazu gekommen und habe im Moment wenig Zeit. Ich hoffe, daß es mir morgen reicht.

Ich hab euch nicht vergessen und die Auswertung mache ich so bald wie möglich.

MfG Jester

Und wie stehts mit der Auswertung?

Und wie stehts mit der Auswertung?

evilissimo

*push*

Jester wird das mit Sicherheit nicht vergessen.

Vielleicht hat er die Preise alleine eingestrichen...

er hat selber noch keine Lösung für das Packet Problem :p

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.