vymysleni algoritmu

[KralLam]

Ahoj,
nejak jsem se zasekl na domacim ukolu a tak bych moc uvital, kdyby tu nekdo nemel co jineho na praci nez mi poradit

Pracujete s databazi, ktera obsahuje informace o studentech a studijnich oborech. Kazdy student studuje prave jeden studijni obor. Kazdy studijni obor muze studovat vice studentu. Rekneme, ze dva studenti jsou spoluzaci, prave kdyz studuji stejny studujni obor.
Vasim ukolem je zjistit, zda v souboru N studentu existuje skupina alespon N/2 spoluzaku, tj. studentu studujicich stejny studijni obor. Problem je, ze jediny databazovy dotaz, ktery k tomu muzete vyuzit, je dotaz na dva studenty; jako odpoved obdrzite pouze informaci zda jsou anebo nejsou spoluzaci.
Navrhnete algoritmus, ktery nalezne pozadovanou odpoved a pritom pocet provedenych dotazu bude O(N log N). Pri navrhu algoritmu pouzijte techniku rozdel a panuj.

Pocmaral jsem asi deset A4, ale worst case mam vzdy kvadraticky.
Tak predem dekuju, pokud nekdo poradite.

[Houp]

já ti poradím jen málo, možná vůbec(že ti řeknu, co už ti dávno došlo). Šel bych na to od konce, tedy ne stylem navrhnout algoritmus, a pak se kouknout na jeho složitost, ale začít tou požadovanou složitostí.

Jelikož se po tobě chce n . log n, tak řešení bude pravděpodobně vypadat stylem nejdřív se zeptej na všechny dvojice. Pak z výsledku nějak zavolat totéž na dvojice dvojic, pak na dvojice čtveřic atd. Teď stačí vymyslet "jen", co to bude dělat.

Vím, asi jsem ti nepomohl.
_________________

[KralLam]

no to myslim, uz napovida docela zadani - rozdel a panuj

[mike.pr]

No jestli ti to vraci jen jestli je spoluzak nebo ne tak je to dost jednoduchy.

Protoze jakmile zjistis, ze Petr je spoluzak Pavla, tak te pak zajimaji jen spoluzaci Pavla, protoze jsou to to i spoluzaci Petra atd atd. Samozrejme v kazdem kroku predavas spoluzakovi mensi a mensi mnozinu k prohledavani.



Krasny D&C

Chybu na krase to bude mit, kdyz bude relace skupin N:M. To pak fakt jinak nez se slozitosti N^2 nepujde.

[OndraSej]

mike.pr> Zkus to trochu rozepsat, nejak v tom navod k reseni v NlogN nevidim (a pokud bys v kazdem kroce ubral jen jednoho spoluzaka, tak nejhorsi pripad bude O(n^2)).

Reseni v N*logN pomoci rozdel a panuj me zrovna nenapada, takze aspon reseni v O(n) (dvema pruchody seznamem spoluzaku):

Prvni pruchod:
Projdi seznam studentu a udrzuj si citac N a aktualni studijni program (reprezentovany jednim jeho clenem C).
Na zacatku N <- 1, C <- prvni student v seznamu
Pro kazdeho dalsiho studenta S proved jedno z nasledujicich:
1) pokud N > 0 a S a C jsou spoluzaci, pak N <- N + 1 a pokracuj dalsim.
2) pokud N > 0 a S a C nejsou spoluzaci, pak N <- N - 1 a pokracuj dalsim.
3) pokud N = 0, pak C <- S a N <- 1

Lemma: Da se rozmyslet, ze pokud na nejakem studijnim programu je ostre vic nez N/2 studentu, pak po projdeni seznamu vsech studentu bude N > 0 a v C bude reprezentant tohoto studijniho programu (resp., coz je dulezitejsi, studijni programy, ktere C nestuduje, nemuzou mit vic nez N/2 studentu).

Druhy pruchod:
Projdi seznam studentu znovu a spocitej, kolik ma C, co vysel na konci predchoziho kroku, spoluzaku.

Pozor, pokud N je sude a studentu v nejvetsim studijnim programu je presne N/2, tak Lemma neplati a je potreba to osetrit. To jde udelat snadno tretim pruchodem, ale na to urcite prijdes, at z toho ukolu neco mas
_________________
http://trionteam.net

[OndraSej]

Tak chvile ve vane a uz me napadlo i to reseni pomoci rozdel a panuj v N*logN. Ono to vlastne je celkem jednoduche
_________________
http://trionteam.net

[KralLam]

Tak se podel

[OndraSej]

Reseni v linearnim case nestaci?
_________________
http://trionteam.net

[KralLam]

No rozhodne za nej dekuji, je pekne a elegantni, ale ja stravil nekolik osklivych hodin nad tim jak to udelat pomoci rozdel a panuj v N log N...jsem zvedavy

[OndraSej]

No, vsechno je to zalozene na celkem jednoduche uvaze, ze pokud nadpolovicni vetsina studentu z mnoziny S patri do studijniho programu A a S libovolne rozdelis na dve stejne velke podmnoziny, tak alespon v jedne z nich nadpolovicni vetsina studentu patri do A. Dal to urcite zvladnes
Teda ono to plati, at uz S rozdelis na dve podskupiny jakkoliv...
_________________
http://trionteam.net

[Quiark]

Hm, tohle jsem taky řešil do školy. Vymyslel jsem brutálně obrovský a složitý algoritmus s asi 10 speciálními případy na principu co říkal ondrasej
_________________
Mám strach

[adragon]

[KralLam]

[OndraSej]

No, pocitat budes asi smerem "zdola nahoru", takze slucovat mensi mnoziny. Co si pri tomhle slucovani budes zachovavat, uz jsem naznacoval vys: s kazdou mnozinou by sis mel predavat, jestli v ni alespon polovina studentu studuje stejny program. A pokud ano, tak bys mel zaroven predat studenta, ktery ten program reprezentuje.

No a ted si predstav, ze mas dve takove mnoziny (a nejvyse dva reprezentanty) a potrebujes je nejak sloucit do jedne (s nejvyse jednim reprezentantem). Otazka je jak. (ale to uz bys mel fakt zvladnout i kdyz jsi beznadejny pripad) Jeste drobna napoveda - abys pocital v NlogN, tak slucovani dvou mnozin studentu o celkove velikosti K ti staci provest v O(K) krocich.

A pak je tu jeste ten problem, kdy studenti v urcite mnozine studuji dva programy a obe skupiny jsou stejne velke (tj. jedna pulka studuje program A, druha program B). Pozor na to - ten postup co jsem popsal je potreba mirne (ale fakt jen mirne) poopravit, aby fungoval i v tomto pripade. Ale na to bys taky uz mel prijit.
_________________
http://trionteam.net