WPC-Aufgabe (Programmierwettbewerb)

Jester

Ganz einfach, ich finde die minimalen Kosten, mit denen es möglich ist zu sortieren. Die vergleiche ich dann mit der Ausgabe von euren Lösungen. Wie ihr auf die Zahl gekommen seid ist mir eigentlich recht egal. Vielleicht gibt's ja ne Lösung, sogar ohne sortieren und so auskommt, keine Ahnung, ehrlich. Ich laß mich überraschen.

Jester

abstrakt schrieb:

Mach mal das ganze Bla-Bla aus der Aufgabenstellung raus.

Wenn Du's nicht schaffst das zu überlesen wirst Du es vermutlich auch nicht schaffen die Aufgabe zu lösen. :p

TomasRiker

Ist es erlaubt, für die Linien z.B. SSE oder 3DNow! zu verwenden?
Womit wird kompiliert?
Auf was für einem Rechner wird kompiliert?

Michael E.

Jester: Hast du schon eine Referenzimplementierung zur ersten Aufgabe? Wenn ja: Kannst du sie bitte zur Verfügung stellen?

groovemaster

Super Sache Jester, dem WPC neues Futter zu geben. Die Aufgabe klingt jedenfalls interessant.
:xmas1: :xmas2:

Jester

Ich werde die Einsendungen wohl mit dem vc8 kompilieren und testen. Die Einsendungen sollten standard-konform sein. Wir können natürlich wenn ihr wollt noch ne Sonderkategorie mit allen möglichen Tricks und Hacks aufmachen. Die Hauptauswertung möchte ich aber lieber auf standard-konformem Code machen.

MfG Jester

Jester

Michael E. schrieb:

Jester: Hast du schon eine Referenzimplementierung zur ersten Aufgabe? Wenn ja: Kannst du sie bitte zur Verfügung stellen?

Ich hab sie noch nicht implementiert. Aber ich werde sie auch auf keinen Fall zur Verfügung stellen. Die Aufgabe ist so gedacht, daß man was dran zu rätseln hat.

Wer weniger rätseln, sondern sich nur auf's implementieren beschränken will, ist möglicherweise bei der zweiten Aufgabe besser aufgehoben.

Sind alle Pakete unterschiedlich schwer oder gibt es gleich schwere?

Könnte man nicht

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

statt

u64 wpc_expert(std::vector<unsigned int> const& gewichte);

schreiben.
Damit es nicht so denglisch ist.

Jester

In dem Code-Fetzen ist kein einziges deutsches Wort. Durch ändern des Variablennamens machst Du's also erst denglisch. Da aber der Name der Variablen nicht maßgeblich für die Signatur der Funktion ist kannst Du sie meinetwegen auch umbenennen.

edit:

sorry, hab's genau falsch rum verstanden. Hab die Aufgabenstellung entsprechend abgeändert.

Jester

Rund um die Programmierun schrieb:

Sind alle Pakete unterschiedlich schwer oder gibt es gleich schwere?

Hm, wenn alle unterschiedlich schwer sind, dann isses leichter, gell? Also gut, weil Weihnachten ist und weil die Aufgabe auch so noch einiges zu tun bietet würde ich sagen: Die Pakete sind alle unterschiedlich schwer.

Jester schrieb:

Bewertungskriterium ist bei beiden Programmieraugaben neben der Korrektheit vor allem die Geschwindigkeit auf Eingaben mittlerer Größe

Was genau bedeutet dieser Satz? Es ist doch schon so, dass Programme, die das falsche Ergebnis liefern, disqualifiziert werden oder zumindest eine erhebliche Strafe erhalten, oder?

Jester schrieb:

...Nochmal technisch:

Schreibe eine Funktion

[cpp]
typedef unsigned long long u64;
u64 wpc_expert(std::vector<unsigned int> const& gewichte);
[/cpp]
...

Jester schrieb:

In dem Code-Fetzen ist kein einziges deutsches Wort. Durch ändern des Variablennamens machst Du's also erst denglisch. Da aber der Name der Variablen nicht maßgeblich für die Signatur der Funktion ist kannst Du sie meinetwegen auch umbenennen.

Sicher???

Michael E.

Jester schrieb:

Michael E. schrieb:

Jester: Hast du schon eine Referenzimplementierung zur ersten Aufgabe? Wenn ja: Kannst du sie bitte zur Verfügung stellen?

Ich hab sie noch nicht implementiert. Aber ich werde sie auch auf keinen Fall zur Verfügung stellen. Die Aufgabe ist so gedacht, daß man was dran zu rätseln hat.

Ich mein ja auch nicht, dass du den Quellcode veröffentlichen sollst, sondern nur eine Möglichkeit geben solltest, zu überprüfen, ob man keine Kombinationen übersehen hat. Was nützen mir meine großartigsten Algorithmen, wenn ich simple Sachen übersehen habe?

@Michael E.:
Lass uns einfach Kosten-Werte austauschen, dann haben wir schon mal ne ziemliche Sicherheit.

- hat sich erledigt -

---

So, hab mal ein Beispiel: 44, 22, 7, 4, 1, 11, 71, 91, 32, 3
Gesamtkosten: 304

Kann das jemand unterbieten?

virtuell Realisticer

Nabend,

also ich hab zwar kein Programm geschrieben, aber mich mal mit Papier und Stifft hingesetzt. Ob es die
minimale Loesung ist, weiss ich nicht, aber zumindest, wenn ich mich nicht vertan hab, komme ich auf
Gesamtkosten von 294 mit deinem Beispiel.

Ich geh das nochmal durch

mfg
v R

evilissimo

Hi Jester,

es wäre gut wenn du Line etwas abgeändert nehmen würdest:

struct Point
{
  Point(double xc, double yc) : x(xc), y(yc) {}
  double x, y;
};

class Line
{
public:
  Line(Point const& startPoint, Point const& endPoint) : start(startPoint), end(endPoint)
  {}
  Point const& getStart() const { return start; }
  Point const& getEnd()   const { return end;   }

private:
  Point start, end;
};

size_t wpc_pro(std::vector<Line> const& lines);

Sonst wird es compile probleme geben. Wenn getStart() und getEnd() nicht const sind kann man die ja net verwenden weil du einen vector<Line> const & übergibst

BR

evilissimo.

c.rackwitz

ich kann 290 fuer die obigen testdaten bieten, aber der algorithmus ist natuerlich kein O(n log n) und auch nur in python implementiert.