WPC-Aufgabe (Programmierwettbewerb)

evilissimo

Meine WPC Pro ( die Linien ) Lösung ist folgende ( falls es überhaupt jemanden interessiert *g* )

http://www.evilissimo-softdev.de/wpc/wpc_pro.html

BR

evilissimo

Michael E.

volkard: Ich hab denselben Ansatz:

#include <algorithm>

struct Packet
{
public:
    Packet(bool unhandled, std::size_t index, unsigned int weight)
        : unhandled_(unhandled), index_(index), weight_(weight)
    {
    }

    bool unhandled_;
    std::size_t index_;
    unsigned int weight_;
};

bool operator< (const Packet &lhs, const Packet &rhs)
{
	return lhs.weight_ < rhs.weight_;
}

class UnhandledPacketFind
{
public:
    bool operator() (const Packet &elem)
    {
    	return elem.unhandled_;
    }
};

typedef std::vector<Packet> PacketList;

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

	for(std::size_t i = weights.size(); i > 0; --i)
        packets.push_back(Packet(true, i-1, weights[i-1]));

    std::sort(packets.begin(), packets.end());

    u64 weight = 0;

    PacketList::iterator iter;
    int counter;
    PacketList::difference_type startPos;
    unsigned int minWeight;
    unsigned int totallyMin = (std::min_element(packets.begin(), packets.end()))->weight_;

    while(true)
    {
    	iter = std::find_if(packets.begin(), packets.end(), UnhandledPacketFind());

    	if(iter == packets.end())
            break;

    	counter = 0;
    	startPos = iter - packets.begin();
    	minWeight = iter->weight_;

        do
        {    
            iter->unhandled_ = false;
            ++counter;
            weight += iter->weight_;
            minWeight = std::min(minWeight, iter->weight_);

            iter = packets.begin() + iter->index_;
        }
        while(iter - packets.begin() != startPos);

        if(counter != 1)
            weight += (counter - 2) * minWeight;
        else
            weight -= minWeight;

        if(counter > 3 && (counter + 1) * totallyMin < (counter - 3) * minWeight)
            weight -= (counter - 3) * minWeight - (counter + 1) * totallyMin;
    }

    return weight;
}

Ponto

volkard schrieb:

hier meine:
u64 s1 = (amount - 2) * min;
      u64 s2 = (amount + 1) * M + min;
das ist bitter. bei nem großen zyklus kriegste einen überlauf, weil amount und min nur 32-bitter sind.

Jetzt wo du es so sagst. Irgendwie hab ich immer so einen Klotz drin.

Ansonsten kann ich nur sagen:

1. Ich hab mich für die Sortierung der Indizes entschieden, um den Overhead auf n*sizeof(SizeType) + Konstante zu bringen.
2. Ich hatte auch ursprünglich eine lokale Summe in der Schleife. Da der Code so aber kürzer ist, hab ich die Summe rausgeschmissen. Hat auf meiner Testplatform nichts an Laufzeit gekostet.
3. Den Swap hab ich auch erst bemerkt, als ich versuchte den Code sinnvoll klein zu kriegen.

Ponto

Michael E. schrieb:

iter = std::find_if(packets.begin(), packets.end(), UnhandledPacketFind());

Macht das das ganze nicht quadratisch? Wenn du n/2 benachbarte Zweierzykel hast, machst du dann nicht n/2 Suchen der Längen 1, 3, 5, ...?

Brutus

Meine ist evilissimos Lösung sehr ähnlich, nur ist seine schneller

Wen's interessiert, meine Lösung + 2 andere Ansätze, einer von Sedgewick: http://rafb.net/paste/results/ksWPX366.html

Jester

Stimmt,

iter = std::find_if(iter, packets.end(), UnhandledPacketFind());

wäre linear gewesen. Böse STL, man schreibt eine Zeile mit nem falschen Parameter und fängt sich ne teure Schleife ein.

MfG Jester

Michael E.

*heul* Darf doch net wahr sein, in meinen Vorüberlegungen hab ich sogar noch dran gedacht

evilissimo

Und wie stehts mit der Auswertung?

BR

evilissimo

Jester

Bitte entschuldigt, die Wartezeit. Ich bin leider noch nicht dazu gekommen und habe im Moment wenig Zeit. Ich hoffe, daß es mir morgen reicht.

Ich hab euch nicht vergessen und die Auswertung mache ich so bald wie möglich.

MfG Jester

Und wie stehts mit der Auswertung?

Und wie stehts mit der Auswertung?

evilissimo

*push*

Jester wird das mit Sicherheit nicht vergessen.

Vielleicht hat er die Preise alleine eingestrichen...

er hat selber noch keine Lösung für das Packet Problem :p

er bastelt sich mit den eingesandten Lösung seine eigene Über-Lösung zusammen und gewinnt bei einem völlig anderen Award den großen Geldpreis.

volkard

oder aber schrieb:

er bastelt sich mit den eingesandten Lösung seine eigene Über-Lösung zusammen und gewinnt bei einem völlig anderen Award den großen Geldpreis.

Nein. Jester ist moralisch integer.

interpreter

volkard schrieb:

oder aber schrieb:

er bastelt sich mit den eingesandten Lösung seine eigene Über-Lösung zusammen und gewinnt bei einem völlig anderen Award den großen Geldpreis.

Nein. Jester ist moralisch integer.

Also long hätte ich ihm schon zugetraut.

*push*

wollt ich auch machen