WPC-Aufgabe (Programmierwettbewerb)

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.

Gunnar

Kann ich davon ausgehen, das kein Geschenk 0 wiegt?

Wie viele Geschenke sind typisch fuer die Bewertungstestlaeufe? Millionen?

TomasRiker

Ich komme auch auf 290 (auf dem Papier).

Aufgabe kann gelöst werden.

Michael E.

Ich komm auch auf 290 Dann kann ich ja mal anfangen, die Implementierung zu verbessern.

Bin auf 180

Michael E.

#include <algorithm>

#pragma warning(push) 
#pragma warning(disable:4035) 
u64 rdtsc() 
{ 
	__asm rdtsc; 
} 
#pragma warning(pop)

int main()
{
	u64 sum = 0;
	u64 time;

	std::vector<unsigned int> origin;
	for(unsigned int i = 0; i < 10000000; ++i)
        origin.push_back(i);

    std::random_shuffle(origin.begin(), origin.end());

    std::cout << "initialized" << std::endl;

    for(int i = 0; i < 10000; ++i)
    {
    	std::vector<unsigned int> weights(origin.begin() + i*1000, origin.begin() + (i+1)*1000);

		time = rdtsc();

        wpc_expert(weights);

        sum += rdtsc() - time;
    }

    std::cout << (sum / 10000) << std::endl;

    sum = 0;

    for(int i = 0; i < 100; ++i)
    {
    	std::vector<unsigned int> weights(origin.begin() + i*100000, origin.begin() + (i+1)*100000);

    	time = rdtsc();

    	wpc_expert(weights);

    	sum += rdtsc() - time;
    }

    std::cout << (sum / 100) << std::endl;
}

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

5 174 824
722 308 723

Wie siehts bei euch aus?

Michael E. was soll der Mist? Deine Lösung soll geheim bleiben.

Michael E.

Troll.

TomasRiker

Darf man eigentlich hash_map etc. verwenden oder muss man alles selbst programmieren?

ERROR

hi

zur sortieraufgabe:

das mit den 290 kann ich irgend wie nicht richtig glauben

keine kiste ist am richtigen platz, also muss jede mindestens einmal bewegt werden, macht 286 ... dann bleiben also nurnoch 4 übrig, d.h. entweder wird die 4 ein zweites mal verrückt oder ihr verrückt die 1 und die 3 je zweimal oder ihr verrückt fünf mal die 1 ... anders gehts ja nicht ... nur wie sieht das bei euch aus?

welche variante entsteht bei euch?

danke und schönen zweiten weihnachtstag noch
:xmas2: andy :xmas1:

Doch, 290 geht. Das hab ich natürlich auch von Anfang an gehabt, 304 war nur, um euch zu foppen.

ERROR

jupp ok habs auch: 5 mal die 1

cu

Jester

Klar, Standard-Lib ist erlaubt! Ja, die getter/setter müssen natürlich const sein.
Ich änder's gleich noch in der Aufgabenstellung.

Die Geschenke haben natürlich alle ein Gewicht echt größer 0.

MfG Jester

Michael E.

Jester schrieb:

Klar, Standard-Lib ist erlaubt!

hash_map ist doch aber nur ne standard extension, oder etwa nicht?