Challenge24 Ec 2014

ekkor:

Ez is megvolt tegnap. Az idei csapatunk (a Quxers) szerintem kiváló volt, bár csak ketten voltunk három helyett. Nem találtunk senkit aki elég motivált és alkalmas lett volna harmadik embernek, főleg hogy még rá is kellett volna érnie.

Volt aki szerint gáz, hogy még mindig versenyeken indulunk, de én még nem érzem magam annyira öregnek. Legalább nem butulok el. Addig nincs vele gond, amíg nehéznek találjuk a feladatokat. Márpedig az idei feladatok is nehezek voltak, végül 51-edik helyen végeztünk, egy elég jó hajrával. Látszik hogy két ember kevés, ha lett volna egy jó harmadik, simán bent vagyunk a döntőben.

Négy feladattal tudtunk foglalkozni a tízből a rendelkezésre álló hat óra alatt. Ebből az egyik egy egészértékű programozós feladat volt (Spy Union), ezt gyorsan sikerült megoldanunk. Aztán volt egy olyan ami utazó ügynöknek nézett ki (Travelling) egy kis bonyolítással: az ügynök a Föld körül utazgat, viszont csak kelet felé mehet. Ez megbonyolítja a távolság számítást két pont között. Ráadásul csak kétszer volt szabad átlépni az antimeridánt. Mindez belefért az utazó ügynökbe, de végül kiderült, hogy nem így kellett volna nekiállni, mert van rá valami direktebb, dinamikus programozáson alapuló módszer. Viszont így a nagyágyút bevetve is megoldottunk hat bemenetet a tízből az utolsó órában.

Aztán jutott még idő egy valószínűség számítós feladatra (Wiretrapping), ahol mint kiokoskodtuk egy gráf összes feszítőfáját kellett meghatározni. Ez volt az összes esetek száma, a rossz eseteket meg úgy kaptuk, hogy a gráfból elhagytunk egy élet, és így is megszámoltuk a feszítő fákat. Erre sok idő ráment, mert a buta algoritmus nem futott le rá, végül tovább olvastuk a PDF-et amit találtunk a neten, és kiderült, hogy visszavezethető a probléma egy mátrix determinánsának kiszámolására.

Az utolsó 20 percben összeírtunk valami szögegyszerű algoritmust egy olyan problémára, ahol az egyes csapatok eredményei egymással versenyeztek (Image compression). Egy képet kellett közelíteni úgy, hogy referencia pontokat vettél fel (itt meg itt legyen ilyen meg ilyen szín). A közelített kép ezeknek a referencia pontoknak a színéből és távolságából esik ki valami átlagszámítással. Mivel a többi csapat se nagyon foglalkozott ezzel, így egész sok pontot kaptunk erre is.

Az idei hangfeldolgozás, ha jól értem egy Doppler effektuson alapuló távolságmérés volt (Forensics). Ezzel eljátszottam egy ideig, de nem tudtam értelmes egyenleteket felírni rá, úgyhogy menet közben átnyergeltem egy másik problémára. Két feladatot meg el sem olvastunk, mert már a leírás is túl hosszúnak tűnt. (Mondom, kevés volt az ember, nagyon kellett sietni.)

Jól kitöltöttük az időt, és jól együtt tudtunk dolgozni. Sajnos csak ennyire futotta, pedig tényleg úgy érzem, hogy ott lenne a helyünk a legjobb 30 között. Ha lesz jövőre is energiánk, talán akkor sikerül, bár most azért szerencsénk is volt, mert az utazó ügynökös algoritmust pont két nappal előtte kódoltam le, úgyhogy az megvolt, csak adaptálni kellett.

6 gondolat erről “Challenge24 Ec 2014

  1. “Ebből az egyik egy egészértékű programozós feladat volt (Spy Union), ezt gyorsan sikerült megoldanunk”
    És ezt hogyan?

  2. Minden emberre felveszel egy valtozot ami nulla vagy egy lehet. Mondjuk egy ha nem rugjak ki.

    Aztan a reszfakban levo emberek valtozoinak osszege nagyobb egyenlo kell legyen a departmentben szukseges emberek szamaval. Ez minden reszfara egy-egy constraintet jelent. Megcsinalod mindket fara.

    Utana mar csak minimalizalni kell a valtozok osszeget hogy minel kevesebb embert tartsunk meg.

  3. Igen eddig jutottam el én is, de ezt nem tudtam hogyan kell..Szimplex módszer jutott eszembe, hogy imlementáljam, de nem is tünik az túl könnyűnek + numerikus hibáktól is féltem volna..

  4. En mar bekeszitettem egy lib-et ami tud sima linearis programozast meg egeszertekut is, mert szokott lenni ilyen feladat.

    Mivel mi c#-ot hasznalunk en a Google Or Toolst talaltam, de van tobb ilyen (glpk mondjuk)

Hozzászólás letiltva