|
Titlul: Paznici3 Scris de: Serban Andrei Stan din 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. Titlul: Răspuns: Paznici3 Scris de: stardust din Februarie 24, 2013, 13:08:58 Cum se facea problema asta ?
Titlul: Răspuns: Paznici3 Scris de: Petru Trimbitas din 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. Titlul: Răspuns: Paznici3 Scris de: Popa Razvan din 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? Titlul: Răspuns: Paznici3 Scris de: George Marcus din 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 :) Titlul: Răspuns: Paznici3 Scris de: Visan Radu din 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. :roll:
Titlul: Răspuns: Paznici3 Scris de: George Marcus din 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. |