WPC-Aufgabe (Programmierwettbewerb)

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.

volkard

Ponto schrieb:

Ich bin mir aber bei Sortieren + O(n) ziemlich sicher. Zum Beweis fehlt noch was Zeit zum nachdenken.

na, hoffen wir mal, daß du nicht recht hast. was machen wir, wenn du recht hast? wie soll man das noch messen? vielleicht hängen wir alle noch nen bäckerwitz in die kommentierung und im zweifelsfall gewinnt der beste bäckerwitz?

Jester

Dann bin ich auch gespannt!

In #cpp ist grad einer, der die Streckenaufgabe macht. Hoffe, daß es noch ein paar mehr versteckte Teilnehmer gibt.

volkard schrieb:

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?

192. Geht es wirklich billiger? Mach mir keine Angst, ich hasse das.

TomasRiker

Ja, leider geht es billiger.

Kosten
 1 32 33 34 31
31 32 33 34  1        32
31 32 33  1 34      + 35
31 32  1 33 34      + 34
31  1 32 33 34      + 33
 1 31 32 33 34      + 32
                    ----
                     166

Gute Nacht.

TomasRiker

Ebenfalls...
Da hatte ich grade meinen alten Algorithmus schön optimiert und dann sowas.
Vielleicht mache ich doch die Aufgabe mit den Linien

volkard gewinnt eh.

TomasRiker

Einmal hab ich ihn geschlagen *g*
wenn auch nur knapp!

Brutus

volkard schrieb:

wer macht eigentlich die streckenschneideaufgabe?

ich

Ach ja, ihr Sortieraufgabenlöser, gebt euch doch nicht alle gleich immer auf, ist volkard nicht eine "Motivation" für euch? Denkt halt nochmal scharf nach, irgendwie wird er auch auf seinen Algo. gekommen sein ;-). Wie ich das verstanden habe, besteht das Risiko, wenn er seine schnelle Lösung abgibt, dass die nicht unbedingt korrekt ist. Braucht ihr noch mehr Motivation?

evilissimo

volkard schrieb:

wer macht eigentlich die streckenschneideaufgabe?

Ich versuchs *duck*

Ponto

volkard schrieb:

Ponto schrieb:

Ich bin mir aber bei Sortieren + O(n) ziemlich sicher. Zum Beweis fehlt noch was Zeit zum nachdenken.

na, hoffen wir mal, daß du nicht recht hast. was machen wir, wenn du recht hast? wie soll man das noch messen? vielleicht hängen wir alle noch nen bäckerwitz in die kommentierung und im zweifelsfall gewinnt der beste bäckerwitz?

Wenn das mit O(n) stimmt, ist da nicht viel zu machen. Und die Sortierung schaue ich mir auf keinen Fall an.

Brutus schrieb:

Wie ich das verstanden habe, besteht das Risiko, wenn er seine schnelle Lösung abgibt, dass die nicht unbedingt korrekt ist. Braucht ihr noch mehr Motivation?

Ja. Ich sehe noch immer keine andere Möglichkeit, als alles durchzuprobieren und das mache ich nicht schneller als volkard.

volkard schrieb:

irgendwer schrieb:

Kann das jemand bestätigen
16628551

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

Danke, ich hab jetzt auch 16628462.

Noch ein bischen Bestätigung bitte.
Mit evilissimo's WeightListGenerator
SEED=10 ELEMS=100 : 1509278
SEED=10 ELEMS=300 : 5041260

SEED=12 ELEMS=200 : 3132883

SEED=31 ELEMS=200 : 3200808

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

volkard

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

Ponto

Hab da ganz andere Werte raus. Kann aber am Generator liegen. Benutze den der glibc? Was habt ihr genommen?

Ich hab mal einen PRNG vorgeschaltet:

class Prng
{
public:
   Prng(unsigned int seed);

   void init (unsigned int seed);
   unsigned int getuint();
private:
   unsigned int a[55];
   int index;
};

Prng::Prng(unsigned int seed)
{
   init(seed);
}

void Prng::init(unsigned int seed)
{
   a[0] = seed;
   for (index = 1; index != 55; ++index) {
      a[index] = a[index-1]*31 + 1;
   }
}

unsigned int Prng::getuint() {
   index = (index + 1) % 55;
   a[index] = a[(index + 23) % 55] + a[(index + 54) % 55];
   return a[index];
}

class WeightListGenerator 
 { 
   std::vector<unsigned> weight_list;   
   Prng prng;

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

Mit den folgenden Ergebnissen:

E: 100 S: 10   228544409808
E: 300 S: 10   682663452603
E: 200 S: 12   426704698914
E: 200 S: 31   436103580650
E: 100 S: 1000 193533809787
E: 300 S: 1000 615707704331

Geht dein Algo auch mit gleichen Gewichten?
Ich hab den Code so geändert

class WeightListGenerator 
{ 
typedef std::map<unsigned int, int,std::less<unsigned int> > WMAP;
  std::vector<unsigned> weight_list;   
  WMAP wmap;
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()); 
	 //}
	 while(elems>0) {
		 unsigned int value = unsigned(rand()); 
		 if(wmap.find(value) == wmap.end()) {
			 weight_list[elems] = value;
			 wmap.insert(WMAP::value_type(value,0));
			 elems--;
		 } else {
			 std::cout<<"\nEQUAL\n";
		 }
	 }

  }   
  std::vector<unsigned> const & GetList() const { return weight_list; } 
};

Und er gibt mir bei SEED=1000 ELEMS=300 zweimal EQUAL aus, bleibt auch nicht mehr hängen.

Haben wir nicht immer die gleichen Zahlen?