3. WPC-Aufgabe (Programmierwettbewerb)

WPC-Aufgabe (Programmierwettbewerb)

  • P

    borg schrieb:

    womit bewiesen wäre das es nicht schneller als O(n^2) geht 🤡

    Deshalb unterteilt man die Laufzeit solcher Algorithmen gerne:

    O(nlogn + Ergebnis) ist dann besser als O(n^2 + Ergebnis) obwohl beide zu O(n^2) werden, wenn das Ergebnis wie hier gezeigt O(n^2) ist.

    0
  • N

    Um Gottes willen! Ihr macht hier komplexitätsanalysen und riesige tests und ich hab mir mal eben in nen paar stunden was gebastelt???
    Naja, hab glaub ich O(n^2), bin mir aber nicht sicher (manchmal kann ich schneller ausschließen, dass sich 2 Strecken net schneiden (parallel), dafür berechne ich aber auf kosten der übersichtlichkeit was doppelt)...

    0
  • B

    Was will er uns nur sagen? 😕

    0
  • V

    Brutus schrieb:

    Was will er uns nur sagen? 😕

    er will, daß alle denken, er würde was voll lahmes abgeben, damit sie noch schnell zur streckenaufgabe wechseln, und er dann alle plattmacht.

    0
  • J

    Zumindest hat er die erste Abgabe überhaupt gemacht gemacht. 🙂

    Achja, er hatte die feine Idee, die Point- und Line- Klasse in wpc_pro.h zu verpacken. Vielleicht können sich da alle dran halten. Wäre praktisch, ist aber natürlich, da ich's so spät erst sage, kein Teilnahmekriterium.

    MfG Jester

    0
  • M

    volkard schrieb:

    SEED=10 ELEMS=100 : 1509278
    ich hab 1509218

    SEED=10 ELEMS=300 : 5041260
    ich hab 5041108

    SEED=12 ELEMS=200 : 3132883
    ich hab auch 3132883

    SEED=31 ELEMS=200 : 3200808
    ich hab auch 3200808

    SEED=1000 ELEMS=100 : 1628503
    ich hab 1624809

    SEED=1000 ELEMS=300 : bleibt hängen (ich hoffe mal auf gleiche Gewichte)
    ich hab 4776964

    Hast du das mit dem schnellen Algo oder mit dem sicheren Algo gemacht?

    0
  • V

    Michael E. schrieb:

    Hast du das mit dem schnellen Algo oder mit dem sicheren Algo gemacht?

    ich habe nur einen implementiert. einen recht schnellen. aber hab nicht irgendwie bewiesen, daß er korrekt ist. hab auch keine programmiertechnischen optimierungem. hab nur so runtergeschrieben, wie ich per hand festtstellen würde, wieviel der weihnachstmann heben muss.

    0
  • M

    Ich glaub, dann brauch ich gar nicht erst mit Optimieren anzufangen. Naja, hab auch noch anderes zu tun.

    0
  • ?

    Wer hat abgegeben?

    0
  • P

    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

    0
  • V

    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.

    0
  • E

    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

    0
  • M

    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;
}
    0
  • P

    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.

    0
  • P

    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, ...?

    0
  • B

    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

    0
  • J

    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

    0
  • M

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

    0
  • E

    Und wie stehts mit der Auswertung?

    🙂

    BR

    evilissimo

    0
  • J

    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

    0
Anmelden zum Antworten