sobota 11. apríla 2009

PR0GR4M470R5K4 UL0H4

V poslednom čase sa v reálnom živote, ale aj na internete rozpútala zúrivá reklamná kampaň, ktorá má okrem iného osloviť aj programátorov. Nemohol som si ju nevšimnúť, pretože každý deň chodím okolo veľkého reklamného nápisu:

BUĎTE LEPŠÍ AKO VŠETCI HACKERI SVETA.

Všimol som si, že táto reklama obsahuje aj malú programátorskú úlohu. A keďže každý programátor bez výnimky si myslí, že je najlepší na svete, tak ani ja som nemohol odolať a musel som ju kvôli spokojnému spánku vyriešiť.

Znenie úlohy je možné nájsť tu http://www.3537.sk/programator.html, citujem:

Máte zoznam súborov, v ktorom je každý súbor identifikovaný menom a podpisom. Meno je ľubovoľný reťazec v úvodzovkách a podpis je postupnosť nezáporných 32-bitových čísiel v šestnástkovej sústave ako môžete vidieť na obr. 01.

"test_name" 3a 45ffa2 236da0 34cc 21
"/usr/stdio.h" 456fa 34dd 28ab9 457e
".other.txt" 5623d ff3a21 783d 22456

Obr. 01: formát zoznamu súborov

Vašou úlohou je nájsť počet jedinečných súborov v zozname. Súbor je považovaný za jedinečný, ak jeho podpis nie je riadnym prefixom podpisu akéhokoľvek iného súboru v zozname. Podpis s1 je považovaný za riadny prefix podpisu s2 vtedy (a len vtedy), keď s2 začína s s1 a podpisy majú rôzne dĺžky. V prípade, že viaceré súbory majú rovnaký podpis, započítajte ich všetky.
Úlohu som rozdelil na dve časti:
  1. načítanie celého súboru do pamäte a rozparsovanie obsahu do vhodnej dátovej štruktúry
  2. algoritmus, ktorý počíta požadované hodnoty nad touto dátovou štruktúrou
Ďalej sa bodom 1 nebudem zaoberať, pretože ho nepovažujem za dôležitý. Predpokladajme, že máme už celý obsah súboru uložený v List<FileDescription>, kde FileDescription vyzerá takto:
public class FileDescription {
    private String name;
    private List<Long> signature = new ArrayList<Long>();

    public String getName() { return name; }
    public void setName(String name) { this.name = name; }
    public int getSignatureSize() { return signature.size(); }
    public Long getSignature(int index) { return signature.get(index); }
    public void addSignature(long signature) { this.signature.add(signature); }
}
Je to obyčajný value object, ktorý obsahuje meno súboru, a podpis, ktorý je List Long-ov, pretože do Java int-u sa 32-bitové číslo nezmestí. (kvôli znamienku)

Riešenie 1 (Java):

Najjednoduchšie riešenie spočíva v tom, že najprv zoradíme FileDescription prvky v Liste podľa veľkosti podpisu od najväčšieho po najmenší a potom prejdeme každý prvok v Liste od začiatku a skontrolujeme, či má nejaké duplikáty. Ak na nejaký duplikát narazíme, proste ho z Listu vymažeme. Na konci metódy nám v Liste ostanú iba unikátne (jedinečné) súbory.
    private static class FileDescriptionComparatorLargestFirst implements Comparator<FileDescription>, Serializable {
        public int compare(FileDescription fileDescription1, FileDescription fileDescription2) {
            if (fileDescription1.getSignatureSize() < fileDescription2.getSignatureSize()) return 1;
            if (fileDescription1.getSignatureSize() > fileDescription2.getSignatureSize()) return -1;
            return 0;
        }
    }

    public int calculateNumberOfUnique1P(List<FileDescription> fileDescriptions) {
        Collections.sort(fileDescriptions, new FileDescriptionComparatorLargestFirst());
        for (int i = 0; i < fileDescriptions.size(); i++) {
            FileDescription outerFileDescription = fileDescriptions.get(i);
            for (int j = i + 1; j < fileDescriptions.size(); j++) {
                FileDescription innerFileDescription = fileDescriptions.get(j);
                if (outerFileDescription.getSignatureSize() > innerFileDescription.getSignatureSize()) {
                    boolean equal = true;
                    for (int k = 0; k < innerFileDescription.getSignatureSize(); k++) {
                        if (!innerFileDescription.getSignature(k).equals(outerFileDescription.getSignature(k))) {
                            equal = false;
                            break;
                        }
                    }
                    if (equal) {
                        fileDescriptions.remove(innerFileDescription);
                        j--;
                    }
                }
            }
        }
        return fileDescriptions.size();
    }
  • algoritmus využíva 3 vnorené for cykly, čo na prvý pohľad naznačuje, že nebude príliš výkonný, ale malý test súbor set_small.dat spracuje bez problémov v zlomku sekundy
  • taktiež výsledok zahŕňa List s unikátnymi súbormi a nielen ich počet (aj keď metóda vracia iba číslo)
  • vyskúšal som metódu aj na veľkom súbore set_large.dat, ale aby sa súbor vôbec načítal do pamäte je potrebné pridať pamäť pre JVM oproti štandardnému nastaveniu, napríklad takto -Xms128m -Xmx1024m
  • kým sa algoritmus dopracoval k výsledku prešlo viac než 20 minút, takže "Tudy cesta nevede." :)

Riešenie 2 (Java):

Druhý algoritmus rozdelí súbory z Listu do Mapy Listov podľa ich podpisu, najprv podľa prvého čísla v podpise a potom odstráni na tej úrovni všetky duplikáty a unikátne súbory z Listu a opakuje tú istú procedúru pre všetky Listy v Mape rekurzívne. Týmto spôsobom sa dá dosiahnuť minimalizácia porovnávania podpisov jednotlivých súborov.
    public int calculateNumberOfUnique2P(List<FileDescription> fileDescriptions) {
        List<FileDescription> uniques = new ArrayList<FileDescription>();
        List<FileDescription> duplicates = new ArrayList<FileDescription>();

        recurseFileDescriptionListP(fileDescriptions, 0, uniques, duplicates);

        return uniques.size();
    }

    private void recurseFileDescriptionListP(List<FileDescription> fileDescriptions, Integer level, List<FileDescription> uniques, List<FileDescription> duplicates) {
        if (level > 0) {
            if (fileDescriptions.size() == 1) {
                uniques.add(fileDescriptions.get(0));
                return;
            }
            if (fileDescriptions.size() > 0) {
                List<FileDescription> cleanCandidates = new ArrayList<FileDescription>();
                Integer largestSizeInList = 0;
                for (FileDescription fileDescription : fileDescriptions) {
                    if (fileDescription.getSignatureSize() == level) {
                        cleanCandidates.add(fileDescription);
                    }
                    if (fileDescription.getSignatureSize() > largestSizeInList) {
                        largestSizeInList = fileDescription.getSignatureSize();
                    }
                }
                if (cleanCandidates.size() > 0) {
                    if (largestSizeInList.equals(level)) {
                        uniques.addAll(cleanCandidates);
                        return;
                    }
                     if (largestSizeInList > level) {
                        duplicates.addAll(cleanCandidates);
                        fileDescriptions.removeAll(cleanCandidates);
                    }
                }
            }
        }

        Map<Long, List<FileDescription>> longFileDescriptionMap = new HashMap<Long, List<FileDescription>>();

        for (FileDescription fileDescription : fileDescriptions) {
            Long key = fileDescription.getSignature(level);
            List<FileDescription> fileDescriptionList = longFileDescriptionMap.get(key);
            if (fileDescriptionList == null) {
                fileDescriptionList = new ArrayList<FileDescription>();
                longFileDescriptionMap.put(key, fileDescriptionList);
            }
            fileDescriptionList.add(fileDescription);
        }

        for (List<FileDescription> fileDescriptionList : longFileDescriptionMap.values()) {
            recurseFileDescriptionList(fileDescriptionList, level + 1, uniques, duplicates);
        }
    }
  • aby sme zabránili pretečeniu zásobníka pri tejto metóde je potrebné upraviť parametre JVM, napríklad takto -Xms128m -Xmx1024m -Xss64m
  • výsledkom algoritmu sú 2 nové Listy, jeden obsahuje unikátne súbory a druhý duplicitné
  • beh programu pre veľký testovací súbor set_large.dat trvá menej ako jednu sekundu
  • pomerne ľahko by sa dal prepísať aby bežal vo viacerých threadoch

Riešenie 3 (C++):

Toto riešenie je prepisom riešenia 2 do iteratívnej podoby, teda ten istý algoritmus, ale bez rekurzie a pretože je napísaný v C++, tak opakujem aj triedu FileDescription.
class FileDescription {
private:
    string name;
    vector<unsigned int> signature;
public:
    string getName() const { return name; }
    void setName(string name) { this->name = name; }
    unsigned int getSignature(unsigned int level) const { return signature[level]; }
    void addSignature(unsigned int signature) { this->signature.push_back(signature); }
    unsigned int getSignatureSize() const { return this->signature.size(); }
};
unsigned int cleanFileDescriptions3P(list<FileDescription*>& fileDescriptions, unsigned int level, unsigned int& uniques, unsigned int& duplicates) {
    if (fileDescriptions.size() == 1) {
        uniques++;
        return 0;
    }
    if (fileDescriptions.size() > 1) {
        list<FileDescription*> toRemove;
        unsigned int largestSizeInList = 0;

        for (list<FileDescription*>::iterator iter = fileDescriptions.begin(); iter != fileDescriptions.end(); ++iter) {
            unsigned int signatureSize = (*iter)->getSignatureSize();
            if (signatureSize == level+1) {
                toRemove.push_back((*iter));
            }
            if (signatureSize > largestSizeInList) {
                largestSizeInList = signatureSize;
            }
        }
        if (toRemove.size() > 0) {
            if (largestSizeInList == level+1) {
                uniques += toRemove.size();
                return 0;
            }
            if (largestSizeInList > level+1) {
                duplicates += toRemove.size();

                for (list<FileDescription*>::const_iterator iter = toRemove.begin(); iter != toRemove.end(); ++iter) {
                    fileDescriptions.remove(*iter);
                }
            }
        }
    }
    return fileDescriptions.size();
}

void calculateNumberOfUnique3P(list<FileDescription*>& fileDescriptions, unsigned int& uniques, unsigned int& duplicates) {
    unsigned int level = 0;
    map<unsigned int, list<FileDescription*> > fileDescriptionMap;
    list<list<FileDescription*> > fileDescriptionsListOfLists;

    fileDescriptionsListOfLists.push_back(fileDescriptions);

    while (!fileDescriptionsListOfLists.empty()) {
        for (list<list<FileDescription*> >::const_iterator outerListIter = fileDescriptionsListOfLists.begin(); outerListIter != fileDescriptionsListOfLists.end(); ++outerListIter) {

            for (list<FileDescription*>::const_iterator innerListIter = (*outerListIter).begin(); innerListIter != (*outerListIter).end(); ++innerListIter) {
                unsigned int key = (*innerListIter)->getSignature(level);
                fileDescriptionMap[key].push_back((*innerListIter));
            }
        }
        fileDescriptionsListOfLists.clear();

        for (map<unsigned int, list<FileDescription*> >::const_iterator mapIter = fileDescriptionMap.begin(); mapIter != fileDescriptionMap.end(); ++mapIter) {
            list<FileDescription*> fileDescriptionsPart = mapIter->second;

            unsigned int unresolvedListFlag = cleanFileDescriptions3P(fileDescriptionsPart, level, uniques, duplicates);
            if (unresolvedListFlag>0) {
                fileDescriptionsListOfLists.push_back(fileDescriptionsPart);
            }
        }
        fileDescriptionMap.clear();
        level++;
    }
}
  • výsledkom sú dve čísla a to počet duplicitných a počet unikátnych súborov
  • výkon je porovnateľný s riešením číslo 2
Záver:

Moje výsledky:
  • set_small.dat: spolu súborov 942, z toho unikátnych 851
  • set_large.dat: spolu súborov 106020, z toho unikátnych 96312
Zadávatelia úlohy výsledky nezverejnili, takže nemám možnosť si skontrolovať či som zadanie pochopil správne. Každopádne pokiaľ problém niekto riešil, určite napíšte komentár ako Vám vyšiel, prípadne aj linku na Vaše riešenie.

Čo dodať ku koncu? Netrúfam si síce povedať, že som lepší ako najlepší hackeri sveta. Ale za predpokladu, že najlepší hackeri sveta sú z Číny, som lepší ako najlepší hackeri sveta v jedení lyžičkou. :)

A čo Vy? Ste lepší ako najlepší hackeri sveta?

35 komentárov:

  1. Nezkoušel jsem ten program vytvářet, ale jako jedno z nejoptimálnějších řešení mi připadá použití prefixových stromů. Stačilo by vytvořit strom a spočítat jeho listy.

    OdpovedaťOdstrániť
  2. Long nie je potrebny, kedze v externej reprezentacii moze byt cislo aj zaporne. Staci, ze jeho interna reprezentazia je hexovo/bitovo spravna. V zasade ide o porovnanie 'rovna sa' / 'nerovna sa' a je jedno, ci je to kladne alebo zaporne cislo. Tym sa usetri 1/2 pamate a rychlost tiez vzrastie.

    OdpovedaťOdstrániť
  3. Tak tak, prefixove stromy ako to je v blogu : http://hladajuci-muz.blogspot.com/2009/04/pr0gr4m470r5k4-ul0h4.html

    OdpovedaťOdstrániť
  4. Jako rychle reseni me napada prepsat metodu hashcode a equals a nahazet to do hashsetu - jeho size je pak vysledek.

    OdpovedaťOdstrániť
  5. RE: Long nie je potrebny...

    ...máš pravdu, len som bol lenivý a nechcelo sa mi ručne konvertovať ten hex String z testovacieho súboru na znamienko + hodnota, ktorá sa zmestí do Integeru

    ...musel by som to skonvertovať do dvojkovej sústavy odobrať jeden bit a použiť ho ako znamienko

    ...oproti C++, ktoré ma unsigned int dosť nevýhoda

    OdpovedaťOdstrániť
  6. RE: ...prefixove stromy...

    ...to je asi štandardné riešenie, ktoré ma vôbec nenapadlo, ak by sa ale zhoršilo počasie mohol by som si to naimplementovať a porovnať rýchlosť s mojím riešením :)

    ...hľadajúcemu mužovi vyšli výsledky rovnako, to ma potešilo :)


    RE: ...prepsat metodu hashcode a equals...

    ...nad tým som rozmýšlal, ale žiadna rozumná realizácia metódy hashcode ma nenapadla

    OdpovedaťOdstrániť
  7. RE: Long nie je potrebny...

    nepochopil som uplne, co si myslel pod konvertovanim do dvojkovej sustavy, odobratim bitu a pouzitim ako znamienko, ale:

    int number = 0;
    pre kazdy znak z hex cisla: number = (number << 4) | znak;

    vysledok je int reprezentacia hex cisla, len je znamienkova. Kedze v principe nie je potrebne porovnanie vacsi/mensi, je jedno ci je externa reprezentacia znamienkova alebo neznamienkova. Interne bitovo je to stale to iste.

    Co sa tyka vysledku v pocte unikatnych zaznamov, tak ten mas spravny.

    OdpovedaťOdstrániť
  8. no neviem, mne to pod javou zbehlo za 2 sekundy a vyuzil som na to 17mb ramky, pricom kamos to stiahol dokonca na 15mb

    OdpovedaťOdstrániť
  9. som rad, ze nie som jediny co sa namotal :-)
    moje riesenie je taketo:
    1. precitat subory do pola
    2. pole zotriedit podla signatury
    (pouzit lexikograficke porovnanie signatur)
    3. iterujeme cez pole.
    ak za prvkom nasleduju dalsie prvky
    ktore su jeho prefixom, preskocime ich.

    na mojom obstaroznom pocitaci to trvalo ~360ms

    OdpovedaťOdstrániť
  10. Hehe - niekto tam pastol moj blog :) musim sa popytat tych par ludi co to citaju kto to spravil.

    a teraz k veci :) aj ked som si nie isty ci to co vytvaram je prefixovy strom :)

    k prispevku predo mnou - v tych 360ms je aj nacitanie suboru? Mne spracovanie trva do 300ms ale nacitanie na 5400 otackovom disku cca 1s.

    A pri takom sposobe riesenia sa moze stat ze pri este vacsich suboroch nebude stacit pamat a zaroven sortovanie rastie n.log n...

    Hladajuci Muz :)

    OdpovedaťOdstrániť
  11. > k prispevku predo mnou - v tych 360ms je aj nacitanie suboru?

    nie. 360ms trvali body 2 a 3 (spracovanie nacitanych dat) na subore set_large.dat

    > A pri takom sposobe riesenia sa moze stat ze pri este vacsich suboroch nebude stacit pamat

    jojo. ak sa data nevmestia do pamate, algoritmy treba vzdy radikalne zmenit :-)
    pretoze set_large.dat nevyzadoval nastavenie velkosti pamati, tzn zmestil sa do 64MB, nezaoberal som sa takouto alternativou. ani v zadani sa takto poziadavka nevyskytla.

    > zaroven sortovanie rastie n.log n

    spravne, zlozitost algoritmu je dana krokom 2. ja povazujem n.log n za dobre. ak ma niekto lepsie, klobuk dolu

    OdpovedaťOdstrániť
  12. Hladajuci muz:

    podla mojho zbezneho nahladu ma tvoje riesenie worst case (kazdy prvok unikatny) zlozitost n^2.

    A co sa tyka nacitania, tak ta 1s nie je z disku, ale uz nacachovane z pamate :) z disku je to podstatne pomalsie (5-6s) ale to zaregistrujes len pri prvom nacitani, potom OS uz ten file podrzi v RAM-ke)

    Stano

    OdpovedaťOdstrániť
  13. ahoj stano.

    toto je postata mojej implementacie:

    private void test() {
    long start = System.nanoTime();

    Collections.sort(files); // order is defined by FileDescriptor.compareTo()
    int n = files.size();
    int unique = 0, duplicate = 0;
    for (int i=0; i<n; ++i) {
    FileDescriptor f = files.get(i);
    unique++;
    while ((i+1<n) && files.get(i+1).isPrefixOf(f)) {
    duplicate++;
    i++;
    }
    }

    long stop = System.nanoTime();
    System.out.println("unique=" + unique + ", duplicate=" + duplicate + ", in " + (stop-start)/1000000 + " ms");
    }

    // this is more tricky than it looks:
    // 1. use descending lexicographical order
    // 2. compare ints using substraction may result in overflow
    public int compareTo(FileDescriptor other) {
    int n = Math.min(signature.length, other.signature.length);
    for (int i=0; i<n; ++i) {
    int a = signature[i];
    int b = other.signature[i];
    if (a<b)
    return 1;
    if (a>b)
    return -1;
    }
    return other.signature.length - signature.length;
    }


    ked zbehne sort(), zvysok je linearna zalezitost (vid i++ vo vnutornom cykle).
    co sa tyka disku ... parsovanie mi trva >20sec, takze tieto efekty nepozorujem :-D.

    s pozdravom, martin

    OdpovedaťOdstrániť
  14. Stano :

    k n^2 - nie som si istý ako si na to došiel. Ale v Tvojom popisovanom prípade zaberie hash a je to ( n * log n) x k, pričom k je max dĺžka podpisu. Horšie je to keď sú rovnaké prvé prvky podpisu a nezaberie hash - ale na to je jednoduchá úprava - vytvárať hash pre prvky kde prekročíme určitý treshold. Potom si stále udržím danú rýchlosť.

    A inak sortovanie v najhoršom prípade je (n * k).log n. A to preto lebo sortovanie keď porovnanie trvá jeden krok je n.log n, lenže tu musíš porovnávať v najhoršom prípade k prvkov ak sa podpisy zhodujú. Takže ak sú všetky rovnaké tak nastáva problém. Riešením by bolo robiť niečo ako insert sort pričom už rovno rozpoznať prefix a nepridávať do zoznamu. potom sa dostaneš na n * k pri všetkých rovnakých prvkoch.

    OdpovedaťOdstrániť
  15. Este raz k Stanovy - preco by to malo byt 5-6s? To by uz fakt musel byt pomalý disk a cital iba 5-6MB/s.

    OdpovedaťOdstrániť
  16. "pretoze set_large.dat nevyzadoval nastavenie velkosti pamati, tzn zmestil sa do 64MB, nezaoberal som sa takouto alternativou. ani v zadani sa takto poziadavka nevyskytla."

    Hmm, a v zadani bolo, ze to ma fungovat pre set_large.dat :) ? Ani nie - to bol len jeden z testovacich suborov... Takyto pristup k problemu nie je velmi rozumny.

    OdpovedaťOdstrániť
  17. Snad posledny prispevok pre teraz :)

    Uz sa Vam niekomu ozval Eset?

    OdpovedaťOdstrániť
  18. ahoj vsetci

    ...stratil som mierne prehlad, ktore komentare sa tykaju ktorych algoritmov, mozno by bolo dobre to explicitne napisat v kazdom komente

    ...kazdopadne, neberte moj kod ako finalny vysledok, je to skor len taka studia uskutocnitelnosti a ide skor o ten princip ako o implementaciu

    ...vacsinou vsetko robim tak iterativne, cestou najmensieho odporu a najrychlejsieho vysledku a potom ked treba tak to optimalizujem, ale k tomu som sa v tomto pripade nedostal

    ...netusim kolko pamate prve dva algoritmy potrebuju, pretoze tak daleko aby som pustil profiler som neprisiel, tie nastavenia pamate pre jvm som urobil len tak zbrucha

    ...samozrejme keby som nepouzil ako nositel dat triedy, v ktorych je meno suboru, ktore vlastne ani nepotrebujem, ale pouzil by som len pole obsahujuce polia int-ov podla navodu v komente vyssie:

    http://antaran13.blogspot.com/2009/04/pr0gr4m470r5k4-ul0h4.html?showComment=1239783240000#c1546353362369214875

    ...tak by sa tie naroky na pamat velmi znizili a aj implementacia by bola asi nepomerne rychlejsia (okrem nacitania dat zo suboru a rozparsovania, to by trvalo dlhsie, ale to som ani nestopoval, pretoze keby bolo cielom testu to ako najrychlejsie rozparsovat ten subor, tak by bol subor navrhnuty asi uplne inak)

    ...taktiez ak niekto viete ako spristupnit zvyraznovanie syntaxe v komentoch bloggeru, tak napiste ako sa to robi

    RE: Uz sa Vam niekomu ozval Eset?

    ...ja som im napisal len jednoduchu otazku, ze ci mam dobre vysledky a dal som im link na tento blog, ale mi neodpovedali a myslim si, ze sa odpovede ani nedockam, ale vzhladom na to, ze ostatnym to vyslo tak isto, tak si myslim, ze je to dobre

    Riesili ste niekto aj tu druhu ulohu?
    http://www.3537.sk/virusovy-analytik.html

    OdpovedaťOdstrániť
  19. predosli koment je moj, len som sa zabudol prihlasit :(

    OdpovedaťOdstrániť
  20. Update: Opravujem, dostal som odpoved z ESET-u a vcelku ma potesila. Ak si najdem cas urcite sa pozriem aj na druhu ulohu.

    OdpovedaťOdstrániť
  21. Mozem sa spytat kedy si im to posielal?

    OdpovedaťOdstrániť
  22. Samozrejme, poslal som to presne: Mon, Apr 13, 2009 at 2:36 PM.

    OdpovedaťOdstrániť
  23. Neviete nahodou niekto kde by sa dal zohnat ten subor set_large.dat bo by som si to chcel aj ja skusit otestovat ale neviem kde ho najst

    OdpovedaťOdstrániť
  24. Ja ho mam :) ale nechcem ho zverejnovat na webe - neviem ako s autorskymi pravami - a zaroven nechcem nejak zverejnovat svoju email adresu :) uz mam spamu dost :) ale ak sa nebojis postni email adresu (aj do mojho blogu :) )

    OdpovedaťOdstrániť
  25. No, a ma menej ako 2MB?

    OdpovedaťOdstrániť
  26. Ma to az nieco cez 30MB ak si dobre pamatam...

    OdpovedaťOdstrániť
  27. Inak, neviem ci viete, ja som si to az teraz vsimol, ale akutalizovali stanku sutaze:
    http://www.3537.sk/programator.html

    Mimochodom, Eset, bolo by velmi zaujimave, keby ste zverejnili vsetky spravne riesenia, prosim..?

    OdpovedaťOdstrániť
  28. museli to dat v poslednych dvoch dnoch ...

    A gratulujem k priamej linke na tento blog :)

    OdpovedaťOdstrániť
  29. super, konecne som nasiel spravne vysledky a este lepsie ze mne to vyslo rovnako :)

    kedze som to zbuchal v Pythone a nechcelo sa mi optimalizovat kym neviem ci mam dobre vysledky,, ostal vykon na 2 sekundach a cca 50MB (set_large.dat)

    http://aprilboy.e404.sk/PH_3537_uloha.py.txt

    OdpovedaťOdstrániť
  30. re Rori:

    diq, pisanie blogov je celkom zabava, ak budem mat nieco co by mohlo zaujat inych, urcite napisem clanok

    re Vyhodnotenie vysledkov:

    prijemne ma prekvapilo kolko roznych programovacich jazykov bolo pouzitych, chcel by som vediet vsetky :)

    pobavilo ma, ze som sa dostal medzi renegatov, nebolo to mojim zamerom, trosku som cakal, ze medzi renegatmi budu riesenia vyuzivajuce kombinacie neuronovych sieti a genetickych algoritmov :)

    OdpovedaťOdstrániť
  31. uz je vonku aj analyticka uloha - http://3537.sk/virusovy-analytik.html

    OdpovedaťOdstrániť
  32. inak niekto z Vas ide pracovat pre eset?

    OdpovedaťOdstrániť
  33. ja nie, ale bol som tam na exkurzii a majú tam pekný výhľad...

    ...taktiež tam majú "Control Room" skoro ako v Houston-e, už iba odpaľovacie zariadenie na rakety a môžu posielať satelity na obežnú dráhu :)

    ...a ešte špeciálne antivírové rohožky, ktoré zrejme zabraňujú šíreniu vírusov medzi miestnosťami :)

    OdpovedaťOdstrániť
  34. Ja som to tiez riesil ale nestihol som to poslat :( navyse to malo jednu chybu - pascal stringy - iba 255 znakov takze setko orezava... ale inak fajne... uz sa tesim na dalsiu ulohu :) (snad nezmeskam)

    P.S. - admini mate nieco s open ID "Poverenia pre váš identifikátor OpenID sa nedali overiť." co to ma byt?

    OdpovedaťOdstrániť