WPC-Aufgabe (Programmierwettbewerb)

roger that. Würd mich auch freuen, wenn eine dritte Instanz das noch bestätigen könnte. Ich weiß nicht warum, aber ich hab ne panische Angst, dass ich es nicht richtig mache. Ich find meinen Algorithmus zwar logisch, aber für nen Korrektheitsbeweis bin ich zu blöd.

EDIT: was ist bis jetzt der geilste Frickel-Kommentar in eurem Code? Meiner:

// vielleicht passt des

Bashar

Ich kann alle drei Werte bestätigen. Mich wundert, wieso das die optimalen Werte sein sollen, ich hab eigentlich erstmal die einfachste Form meines Algorithmus' aufgeschrieben, die Verbesserung sollte noch kommen ... das scheint aus irgendeinem Grunde so schon optimal zu sein. Oder eure Ergebnisse sind es nicht

Muss nur noch -- definitiv -- an der Laufzeit feilen

Ich kann alle drei Werte bestätigen.

Dann kann's kaum noch falsch sein.

Bashar schrieb:

Muss nur noch -- definitiv -- an der Laufzeit feilen

Hast noch nichts mit O(log(log(log n))) gefunden?

Woah, kann das sein, dass std::vector::clear() ends teuer ist? Das STL-Zeugs taugt irgendwie nicht.

Bashar

Nein, erstmal die doof-Version, O(n^2). 10000 Pakete dauern ein paar Sekunden.

evilissimo

class WeightListGenerator
{
  std::vector<unsigned> weight_list;  
public:
  WeightListGenerator( size_t elems , unsigned seed = unsigned(time(0)))
  : weight_list(std::vector<unsigned int>(elems,0))
  {
     std::srand(seed);                         
     while(elems--)
       weight_list[elems] = unsigned(rand());
  }  
  std::vector<unsigned> const & GetList() const { return weight_list; }
};

Anstatt ständig alles tippen zu müssen könnt ihr die obige klasse verwenden um eure vectoren zu basteln. Mit dem selben startwert ( seed ) könnt ihr dann eure werte untereinander vergleichen. ( macht eure posts etwas kürzer )

size_t anzahl_pakete = 10;
unsigned seed = 234;
WeightListGenerator gen( anzahl_pakete , seed );
u64 result = wpc_expert(gen.GetList());

BR
evilissimo

volkard

irgendwer schrieb:

Kann das jemand bestätigen
16628551

leider nicht.
ich hab 16628462.
ich hab aber auch 16628551 in meinem ersten versuch gehabt.

c.rackwitz

volkard schrieb:

leider nicht.
ich hab 16628462.
ich hab aber auch 16628551 in meinem ersten versuch gehabt.

postest du im neuen jahr die zwischenschritte fuer dieses ergebnis? ich waer interessiert.

Michael E.

Ich auch, kireg nämlich auch 16628551 raus. Dabei war ich mir doch sicher, dass mein Algorithmus richtig ist

BTW: Ich wär mal froh, wenn ich die Komplexität von meinem Algo rauskriegen würd Müsst aber einklich O(n) sein.

Bashar

volkard schrieb:

ich hab 16628462.

Gut.

Ponto

Michael E. schrieb:

Ich auch, kireg nämlich auch 16628551 raus. Dabei war ich mir doch sicher, dass mein Algorithmus richtig ist

BTW: Ich wär mal froh, wenn ich die Komplexität von meinem Algo rauskriegen würd Müsst aber einklich O(n) sein.

O(n)? Da muss ich noch rauskriegen, wie man es ohne Sortieren macht.

TomasRiker

volkard, Bashar:
Ihr wollt uns doch nur Angst machen!
... oder?

Bashar

Michael E. schrieb:

Kompiliert mit VC++ 2003 Toolkit auf Speed optimiert komm ich auf folgende Ausgabe:

5 174 824
722 308 723

gcc -O

562 092
163 260 531

volkard

c.rackwitz schrieb:

volkard schrieb:

leider nicht.
ich hab 16628462.
ich hab aber auch 16628551 in meinem ersten versuch gehabt.

postest du im neuen jahr die zwischenschritte fuer dieses ergebnis? ich waer interessiert.

viel einfacher. auch wenn es mich und bashar den sieg kostet, ich verrate das problem meines ersten algos algos an einem beispiel:
1 32 33 34 31
was sagt dein programm dazu?

volkard

Ponto schrieb:

O(n)? Da muss ich noch rauskriegen, wie man es ohne Sortieren macht.

ich glaube nicht, daß es ohne sortieren geht. und daß es mit sortieren plus O(n) geht, ist noch nicht bewiesen. sicher ist für mich bisher nur, alle möglichleiten durchzuprobieren (sagen wir mal mit höchstens 2*n vertauschungen), und die leichteste zu nehmen. klingt nach O(n!). sollte ich eine schnelle lösung abgeben, wo ich nicht weiß, ob sie stimmt, oder eine langsame?

Bashar

volkard schrieb:

viel einfacher. auch wenn es mich und bashar den sieg kostet, ich verrate das problem meines ersten algos algos an einem beispiel:

Das "gut" ist wohl falsch rübergekommen. Ich meinte nicht, das ich das gleiche Ergebnis bekomme, sondern hab mich gefreut, dass es noch Optimierungspotential gibt.

Ponto

volkard schrieb:

Ponto schrieb:

O(n)? Da muss ich noch rauskriegen, wie man es ohne Sortieren macht.

ich glaube nicht, daß es ohne sortieren geht. und daß es mit sortieren plus O(n) geht, ist noch nicht bewiesen. sicher ist für mich bisher nur, alle möglichleiten durchzuprobieren (sagen wir mal mit höchstens 2*n vertauschungen), und die leichteste zu nehmen. klingt nach O(n!). sollte ich eine schnelle lösung abgeben, wo ich nicht weiß, ob sie stimmt, oder eine langsame?

Da du ja jetzt den Witz an der Aufgabe verraten hast, kann man mal darüber nachdenken. Die Zeit in die Laufzeitoptimierung zu stecken halte ich für sinnlos. Da sind andere immer besser und ohne die Testplattform kann man auch nicht viel machen. Ich bin mir aber bei Sortieren + O(n) ziemlich sicher. Zum Beweis fehlt noch was Zeit zum nachdenken.

Ponto

Im übrigen denke ich, dass die Aufgabe spannender wäre, wenn Pakete auch identisches Gewicht haben könnten. Aber dafür ist es zu spät.

Jester

Ja, die Aufgabe wäre dann definitiv schwieriger. Allerdings muß ich ehrlich gestehen, daß mir dann meine Lösungsansatze nahezu alle kaputt gehen und mir nur noch eine Idee übrig bleibt.

Um mehr Spielraum zu lassen habe ich mich daher entschieden, die Aufgabe so zu stellen.

MfG Jester

volkard

wer macht eigentlich die streckenschneideaufgabe?

volkard

Jester schrieb:

Ja, die Aufgabe wäre dann definitiv schwieriger. Allerdings muß ich ehrlich gestehen, daß mir dann meine Lösungsansatze nahezu alle kaputt gehen und mir nur noch eine Idee übrig bleibt.

da bin ich ja mal gespannt. ich hab nur einen lösungsansatz, un dem ist egal, ob doppels vorkommen.