HUP-osok a Veszprémi 24 órás programozóversenyen - III. hely

A versenyre idén is csapatunk jutott be a legtöbb ponttal, az elődöntőben a bejutás határának kétszeresénél is több pontot értünk el. Maga a döntő egy kis crackerkedéssel kezdődött, valahogy be kellett jutni arra a weboldalra, amely magát a feladatot tartalmazta. Ez sajnos a "hivatalos" úton nem ment, de a weboldalt kiszolgáló szerveren rejtetlenül maradt class fájl visszafejtésével meglett a jelszó, és a második leggyorsabb csapatként kezdhettük megoldani a fő feladatot.
Ez pedig nem más volt, mint - itt a gazdasági világválságban - egy szállítási feladat valamiféle megoldása olyan módon, hogy a kötelezően elvitelre kerülő csomagokon felül opcionális, licitálható csomagokat is elvihetőek voltak. Ha rálicitáltál másra, és el tudtad szállítani a csomagot, sok pénzt kaptál, viszont ha nem, sok mínuszt. 5 percig lehetett licitálni, majd további 7 percig megoldani a feladatot.
Nos, a mi stratégiánk annyi volt, hogy a 12 percet egyben tekintve egy Branch-and-bound algoritmussal kiszámolunk egy minél jobb utat, majd feltöltjük így ahogy van. Valószínűsítettük, hogy licitálni nem nagyon fog a többi csapat, mert túl rizikós.
A verseny végén 5 tesztnap volt, 5 szállítási feladattal. Az első három után még nyerő pozícióban voltunk, a negyedik napon -200.000 Ft-ot csúsztunk amiatt, hogy rossz binárist futtattunk, az ötödik napon egy algoritmikus (azóta sem ismert) bug miatt túlterheltük az autót, és újabb 200.000 Ft-ot buktunk, emiatt a negyedik helyre csúsztunk vissza.

Kicsit bántó dolog, hogy míg néhány csapat - köztük mi is, és a második helyezett is - algoritmust írt, addig néhányan egyszerűen annyit tettek, hogy a rendelkezésre álló 12 perc alatt valamilyen módon találtak egy egész jó megoldást, majd azt ránézésre, emberi beavatkozással, próbálkozva oldották meg, a végeredményeket pedig SQL inserttel írták vissza a táblába.

Összességében a feladat maga nem tetszett csapatunk tagjainak, az meg főleg nem derült ki, hogy melyik csapat tudott végülis jó algoritmust adni a problémára. Sajnos egyéb része nem volt ennek a jól nem felosztható problémának, szóval a fentebb látható GUI-nk sem lett értékelve.

Míg valaki itt meg van lepődve A programot teljes egészében C++-ban, Qt 4.5-tel írtuk. greenvirag javaslatára minden tárolót Qt-sre cseréltük ki, kihasználva pl.: a QVector implicit sharingen alapuló megvalósítából adódó gyors, és memóriahatékony működést. Qt-vel kezeltük az SQL-t, és a GUI-t is ezzel készítettük, felhasználva a webkit motort és egy kis Google Mapset. A program egyébként jól működött, 9 perc elteltével visszaadott egy jó túraútvonalat, és a GUI-n kirajzolta a három jármű útvonalát, különböző színekkel, a listában megjelnő címek pontos bejelülésével.

Tavaly lecsúsztunk az első helyről, idén még közelebb voltunk hozzá, mégis múlasztottunk. Emelt fővel, örömmel fogadtuk a harmadik helyezést, és ezúton gratulálunk másik HUP-os haverunknak, persicsb-nek, aki a második helyezett csapatban volt, és mivel egymással szemben ültünk, végig baromkodtunk. :)