Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Paznici3  (Citit de 2549 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
savim
Nu mai tace
*****

Karma: 194
Deconectat Deconectat

Mesaje: 333



Vezi Profilul
« : Februarie 24, 2013, 01:28:50 »

Aici se pot pune întrebări legate de problema Paznici3 de la Runda 3 a concursului Algoritmiada 2013.

Timpul alocat întrebărilor este de 1 ora dupa inceperea concursului. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII.
Memorat
stardust
Strain
*

Karma: 13
Deconectat Deconectat

Mesaje: 39



Vezi Profilul
« Răspunde #1 : Februarie 24, 2013, 13:08:58 »

Cum se facea problema asta ?
Memorat
S7012MY
Nu mai tace
*****

Karma: 26
Deconectat Deconectat

Mesaje: 648



Vezi Profilul
« Răspunde #2 : Februarie 24, 2013, 19:35:31 »

bst[0/1][nod] costul de a acoperi subarborele lui nod fara/cu nodul nod .
Pentru fiecare nod o sa te intereseze paznicii care pazesc o pereche de noduri cu lca-ul in nod.
Memorat
razvan.popa
Strain


Karma: -3
Deconectat Deconectat

Mesaje: 12



Vezi Profilul
« Răspunde #3 : Februarie 25, 2013, 20:45:10 »

Daca vrei sa calculezei Bst[1][nod], nod fiind lca-ul unei perechi din cele M, nu trebuie sa separi nodurile de pe lant de celelalte?
Cum se face asta in timp logaritmic?
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 719



Vezi Profilul
« Răspunde #4 : Februarie 25, 2013, 20:51:41 »

bst[0/1][nod] costul de a acoperi subarborele lui nod fara/cu nodul nod .
Pentru fiecare nod o sa te intereseze paznicii care pazesc o pereche de noduri cu lca-ul in nod.

M-am gandit si eu la asta, dar nu stiu daca merge. In exemplu, daca esti in nodul 1 si iei (3, 7) de unde stii ca nodurile 4 si 6 nu sunt acoperite?

Edit: Sau ce a zis Razvan mai sus Smile
Memorat
visanr
Nu mai tace
*****

Karma: 168
Deconectat Deconectat

Mesaje: 213



Vezi Profilul
« Răspunde #5 : Februarie 28, 2013, 12:34:29 »

O solutie cu complexitate teoretica O(N * M) (parcurge lanturile in O(N)), dar care are fast kill, obtine 100 pct, timp maxim 770 ms.   Rolling Eyes
« Ultima modificare: Februarie 28, 2013, 13:17:31 de către Visan Radu » Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 719



Vezi Profilul
« Răspunde #6 : Februarie 28, 2013, 12:35:48 »

Se intampla ceva ciudat. Primesc "Wall time limit exceeded.". Cred ca timpii afisati de evaluator nu sunt corecti.

Edit: Ori e ceva dubios la sursa mea ori au ceva testele.
« Ultima modificare: Februarie 28, 2013, 13:19:18 de către George Marcus » Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines