Prije nekoliko mjeseci u postu Znanost i algoritmi pisao sam o nekim znanstvenim radovima u kojima glavnu ulogu igraju algoritmi ne toliko različiti od onih na natjecanjima. U međuvremenu sam se sjetio još dvaju dobrih primjera u kojima glavnu ulogu igraju naši algoritmaši. Za početak spomenimo članak u kojem su naši bivši uspješni natjecatelji (Goran Žužić i Filip Pavetić) objavili efikasan algoritam računanja sličnosti stringova. A o drugom primjeru treba napisati nešto više, pa krenimo.

Na 1. kolu HONI-ja 2012. postavio sam zadatak Mars. U njemu je riječ o potpunom binarnom stablu u kojemu možemo proizvoljno zamijeniti lijevo i desno podstablo bilo kojeg vrha – ili, ekvivalentno, odabrati permutaciju listova u kojoj svako podstablo i dalje pokriva uzastopan podniz – tako da zbroj “odbojnosti” susjednih listova (koja je definirana za sve parove u ulaznim podatcima) bude što manji.

Zanimljivo je da sam poslije naišao na znanstvene radove koji rješavaju isti problem. Ovaj članak rješava isti problem za PQ-stablo i primjenjuje ga na poznati problem trgovačkog putnika (Travelling Salesman Problem ili TSP). U ovom članku problem se rješava za K-arna stabla (u binarnom stablu je K = 2) i primjenjuje u bioinformatici za sortiranje gena. Algoritmi i jednog i drugog članka svode se na za binarno stablo, što je i složenost mog rješenja u zadatku Mars.

Ali to nije najbolja moguća složenost! Kao što pokazuje ovaj članak Urlika Brandesa, problem za binarna stabla moguće je riješiti u . Zanimljivo je da je jedan natjecatelj na samom natjecanju pronašao takvo, brže rješenje (o kojem je, dakle, netko prethodno napisao znanstveni rad) – to je bio Luka Kalinovčić na COCI natjecanju. Nakon što sam proučio njegovo rješenje, opisao sam ga (uz vlastito) u službenim rješenjima, tada još ne znajući za cijelu ovu priču. Svaka čast Luki!

Spomenimo i da navedeni Brandesov članak navodi još neke primjene ovog problema kao što je sortiranje piksela u svrhu sažimanja slika, te je predloženi algoritam zbog memorijske složenosti od bolji od algoritma iz članka koji se izvorno bavi tim praktičnim problemom.