Programmiercontest...

CarstenJ

Ich weiss, dass es dazu schonmal einen Thread gab....ich wollte nur mal wissen, ob da noch jemand mitmacht:
http://www.geocities.com/acmesofties/wpcq.htm

operator void

Der Contest war im Channel #cpp sehr beliebt, als ich das letzte Mal da war. Mir sind die Aufgaben aber irgendwie zu sehr aus der Luft gegriffen. Was bringt mir eine kurze handgecodete Lösung, wenn jemand mit der STL und boost das ganze in zwei Zeilen schafft? Da finde ich diese 48-Stunden-Spieleprogrammierwettbewerbe viel lustiger...

CarstenJ

Naja, stimmt schon, aber mich interessieren die Dinge, die dahinter stecken. Ich habe z.B. megagroße Probleme, Duplikate aus einem Array zu entfernen. An diesem Problem sitze ich schon Wochen. Solche Aufgaben sind da schon hilfreich, da man einiges lernen kann. Allerdings muss ich echt feststellen, dass mir Algorithmen gerade mal so gar nicht liegen :(.

In C++ würde man da eben nen SET nehmen, und Problem gelöst. Das kann sogar ich, aber wies wirklich funktioniert wüsste ich dann immer noch nicht....

Walli

Jo, ich mach da schonmal mit wenn ich Langeweile habe. Manchmal ist die Auswertung der Ergebnisse allerdings nicht ganz nachvollziehbar.

HumeSikkins

Hallo,
das Bewertungskriterium dieser Aufgabenstellung findet ich persönlich mal wieder äußerst dämlich. Was genau bringt einem denn "code brevity"?

Die Aufgabe an sich finde ich aber interessant.
Was würdet ihr für einen Algorithmus verwenden?
Ich habe bisher über drei Ansätze nachgedacht:
1. Triviale Lösung -> Zwei Schleifen: n^2
2. Arrays sortieren + 1 Schleife zum Vergleichen: 2 * (nlogn) + n
3. Bit-Vektor der Größe size = (max(a,b) / + 1: 2n + 2size

Wie würdet ihr vorgehen?

Shade Of Mine

MaSTaH schrieb:

Jo, ich mach da schonmal mit wenn ich Langeweile habe. Manchmal ist die Auswertung der Ergebnisse allerdings nicht ganz nachvollziehbar.

jo, vorallem dass die Testdaten nicht bekanntgegeben werden ist doof. Vorallem wenn es um speed geht.

Soll ich den Algo dann für <1000 Elemente optimieren, oder lieber für größere Elemente? etc...

IMHO sind die Daten einfach zu wenig...

Bashar

HumeSikkins schrieb:

Was genau bringt einem denn "code brevity"?

Spaß z.B.

CarstenJ

Sagt ihr mir mal bitte, ob es im Prinzip einfach ist, ein Array auf doppelte Einträge zu überprüfen? Ich schaffe es nicht, und wäre für Hilfe dankbar....irgendnen Ansatz, irgendnen Tipp, irgendwas, das mich weiterbringt.

HumeSikkins

Sagt ihr mir mal bitte, ob es im Prinzip einfach ist, ein Array auf doppelte Einträge zu überprüfen?

Was genau meinst du mit überprüfen? Nur eine Ja/Nein-Frage oder brauchst du alle Doppelten?

Zwei spontane Möglichkeiten für Ja/Nein:
1. Array sortieren, dann paarweise Vergleichen.
2. Zwei for-Schleifen. Die äußere geht von i = [0..n), die innere von j = [i+1..n).
Falls array[i] == array[j] -> Duplikat.

Bashar

3. Array-Elemente in eine Menge (Hashtable oder Baum (std::set)) eintragen, dabei prüfen ob schon vorhanden.

HumeSikkins

Hallo,
ich hätte da auch gerade mal ein Problem.
Gegeben:
sortiertes Array mit N Elementen (a1..aN mit ai <= ai+1)

Gesucht:
Array a1,..,ak,ak+1,..an mit ai < ai+1 für i <= k und ai <= ai+1 für i > k.

Dabei soll sowohl das Array transformiert werden, als auch der Index von (oder ein Zeiger auf) ak+1 geliefert werden.

Sprich: Alle Duplikate sollen nach hinten verschoben werden. Ihre Reihenfolge soll zusätzlich sortiert sein.

Beispiel:
Eingabe: a[] = {1, 2};
Ausgabe: a = {1,2} und k + 1 = 2

Eingabe: a[] = {1, 1, 2, 2};
Ausgabe: a = {1,2, 1, 2} und k + 1 = 2

Eingabe: a[] = {1,1,2,2,2,3,3,4};
Ausgabe: a = 1, 2, 3, 4, 1, 2, 2, 3 und k + 1 = 4

Meine Frage:
Lässt sich das nur durch Tauschen der Elemente implementieren. Sprich ohne temoporäres Array und ohne das man am Ende einfach die Duplikate sortiert?

Meine Lösung benötigt z.B. eine explizite Sortierung:

template <class FwdIter>
FwdIter uniqueImpl(FwdIter begin, FwdIter end)
{
	if (begin == end) return begin;
	FwdIter next = begin;
	FwdIter put = next;
	while (next != end)
	{
		while (next != end && *next == *put)
			++next;
		++put;
		if (next == end)
			return put;
		swap(*put, *next);
		++next;
	}
	return ++put;
}

template <class FwdIter>
FwdIter uniqueWithSort(FwdIter begin, FwdIter end)
{
	FwdIter newEnd = uniqueImpl(begin, end);
	sort(newEnd, end);
	return newEnd;
}

hmm
naja angenommen man macht die sache von hinten her..
dann wuerde man fuer 1,1,2,2,2,2,3,3,4
=> 1,2,2,3,1,2,3,4
erhalten!
jetz drehen wir das ding bei put (zeigt auf 1) und voilá

1,2,3,4,1,2,2,3

sry das war falsch
1,3,2,2,2,1,2,3,4 kommt natürlich raus..
hmm..