AGM 2015

[•eudanip]

Prima editie a concursului AGM va avea loc sambata 30 mai 2015.

[•SebiSebi]

Cum sa scapă la problema Autobuze3 de condiția de 25 de mutări pentru un șofer? Ideea inițiala a fost ca răspunsul este costul unui MST. Dar cum se construiește răspunsul astfel încât sa nu existe mai mult de 25 de mutări?

[•PlayLikeNeverB4]

Muti soferii din autobuzul cu numar mai mic de soferi in autobuzul cu numar mai mare de soferi. Fiecare sofer va fi mutat de cel mult logN ori.

[•SebiSebi]

Cum se poate demonstra ca este cel mult log(N)? Eu am mutat șoferii din toate autobuzele în autobuzul care avea un șofer cu număr maxim de mutări (asta pentru fiecare nod din arbore) si pica. Adica facem o parcurgere in adancime si pentru fiecare nod, dupa ce rezolvam subarborele sau vedeam cate autobuze ajung in el. Unul dintre acestea trebuie sa treacă mai departe către rădăcina. Si acesta era cel care avea un sofer cu numar maxim de mutari.

[•PlayLikeNeverB4]

Pai gandeste-te la cum se muta un sofer s. Fie x numarul de soferi din autobuzul in care e s. Daca se muta soferul s in alt autobuz atunci x va deveni cel putin 2x. Evident, nu se poate intampla asta decat de cel mult logN ori.

[•SebiSebi]

Sa zicem ca intr-un nod ajung 3 autobuze: unul cu 2 soferi, altul cu 3 și altul cu 5. Atunci nu trebuie sa ii mut pe cei 2 din primul si pe cei 3 din al doilea, in al treilea autobuz? Ultimul va fi cel care va "avansa" catre radacina impreuna cu 10 soferi.

[•PlayLikeNeverB4]

Da, e corect.