Programátorská úloha od Esetu

HackForum

Programátorská úloha od Esetu#
[link]

Nezkoušel náhodou někdo vyřešit tento problém (zadání vytáhněte třeba z google cache [link])? 24.4. mají uzávěrku, takže pravděpodobně nebude vadit, když se tu objeví nějaké zajímavé myšlenky.

Když jsem se s tím problémem potýkal, nejvíc času jsem samozřejmě strávil nad strukturou, do které bych nacpal prefixy. Jako nejefektivnější mi vylezlo něco mezi trií [link] a binárním vyhledávacím stromem [link] .
Časová složitost celého "počítacího" algoritmu mi vychází na O(n logn k), kde n je počet řádků, k je jejich délka. (kvůli alokaci paměti pro uložení prefixu je přenější O(n*log(n)*k*log(k)), ale logk je vzhledem k zbytku tak zanedbatelná hodnota, že na ni není třeba brát ohled).
Celé to funguje na Dual-Core 1.8GhZ okolo 5 sekund (ten větší soubor set_large.dat), přičemž spousta času by se asi ušetřila, kdybych prefixy ukládal jako pole znaků, nikoli jako integery (konverze sscanf()-em z "písmen na čísla" je ve výsledném čase citelně znát). Spotřeba paměti by ale narostla téměř dvojnásobně.
(odpovědět)
mr.Crow. | 212.96.172.*23.4.2009 19:15
re: Programátorská úloha od Esetu#
Ahoj,
ja som praveze ani nebral do uvahy nazvy tych suborov, ved v podstate ani nie su pre tuto ulohu dolezite. Dolezite su predovsetkym prve cisla z podpisu.
Este to naprogramovane nemam, ale myslel som na trojicu dat. struktur: hash table, a dva binarne stromy.
Mozes sa s nami podelit, ako si to realizoval pomocou toho trie?
(odpovědět)
spacer | 195.91.79.*25.4.2009 11:28
re: Programátorská úloha od Esetu#
vymyslel jsem strom, jehož velice zjednoduššený princip je tento:

- každý uzel má dva potomky.
- prefix vkládáme na pozici, ke které se dostaneme tímto postupem:
a) pokud procházíme uzel s dvěma potomky, pokračujeme v prohledávání na potomkovi, který má s právě vkládaným prefixem více společných nejnižších bitů
b) pokud má uzel jednoho potomka, pokračujeme v prohledávání na tomto potomkovi jen pokud má s právě vkládaným prefixem více stejných nejnižších bitů, než právě procházený uzel. V opačném případě vložíme prefix na volné místo, tzn. právě procházený uzel od této chvíle má oba potomky
c) pokud nemá uzel ani jednoho potomka, právě vkládaný prefix mu jako potomka přiřadíme

--tento postup (ověřoval jsem si to) zaručuje, že při vkládání prefixu projdu právě ty uzly, ve kterých může být uložen prefix takový, že bychom právě vkládaný prefix nebo právě procházený museli odstranit (právě vkládaný prefix odstranuji, pokud je prefix už uložený ve stromě, nemažu ho, nastavuju mu spec. příznak). Duplicitní prefixy neukládám vícekrát, jen jednou - počet duplicit si každý uzel pamatuje.
--takový strom má tu výhodu, že se prefixy do jednotlivých větví dostávají celkem rovnoměrně, tzn. průměrný počet uzlů, které při N uzlech stromu musíme projít se odlišuje od lg(N) "celkem málo".

---možná je tato struktura nedobře pochopitelná. Vymyslel jsem pravděpodobně obludu, která se hodí (možná nehodí, nevím) jen pro tento případ :-)
(odpovědět)
mr.Crow. | 213.211.34.*26.4.2009 19:39
re: Programátorská úloha od Esetu#
Máte na tuto ulohu taktéž i programátorský kód?

(odpovědět)
HR ClamWin | 217.12.62.*12.11.2010 15:36

Zpět
 
 
 

 
BBCode