Diametru

[•eudanip]

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

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.

[•GavrilaVlad]

You might want to check on this:

http://www.infoarena.ro/job_detail/1454660

Eroare in configurarea problemei: TLE in evaluator.

[•klamathix]

Aye, aye, rezolvăm, scuze. Carry on  .

[•fluture.godlike]

Daca la rezultate partiale evaluatorul da mesajul "Wrong answer", nu primim nici un punct pe problema?(sau doar nu e rezolvata de 100p?)

[•a_h1926]

Daca vi se afiseaza "Wrong answer", nu primiti niciun punct pe problema. Punctajele partiale sunt afisate la feedback.

[•veleandu]

Cum definiti faptul ca "niciunea din perechile (next, nod_curent) si (nod_curent, next) sa nu mai fi fost aleasa"
Sa nu te fi extins din nod_curent in next sau invers?
in cazul asta, sigur sigur evalul ia next-ul sa aiba indice minim?
Iau 50 de puncte si chiar nu inteleg de ce

[•Andrei1998]

Ce se intampla daca nu mai exista nici o pereche astfel incat niciunea din perechile (next, nod_curent) si (nod_curent, next) sa nu mai fi fost aleasa?

[•veleandu]

Acum ca ma gandesc mai bine, cred ca asta se intampla si la mine.
Cred ca el nu mai gaseste muchiile respective si crede ca s-a terminat.
DAR NU S-A TERMINAT >

asa ca presupun ca gaseste si prost diametrul

[•a_h1926]

@Velea
Atunci cand vrei sa te extinzi din nod_1 in nod_2, niciuna din perechile (nod_1, nod_2) sau (nod_2, nod_1) nu trebuie sa fi fost alese la un moment anterior. Cu alte cuvinte, nu tinem cont de ordinea nodurilor din pereche. Evaluatorul foloseste algoritmul descris in enunt.

@Constantinescu
NO COMMENT

[•Andrei1998]

"next <- nodul cel mai indepartat de nod_curent astfel incat niciunea din perechile (next, nod_curent) si (nod_curent, next) sa nu mai fi fost aleasa
          in caz de egalitate se alege next la distanta maxima de nod_curent"
Al doilea rand se refera la egalitate in cazul in care nu se gaseste o pereche cu conditia suplimentara de pe primul rand? (nu e deloc clar de ce ambele conditii spun ca se alege nodul la distanta maxima)

[•veleandu]

Cum adica no comment?
Pe langa ca in enunt NU SCRIE CAND SE OPRESTE ALGORITMU
scopul nostru e sa facem ca "pseudo codu" ala sa ia TLE sau sa ia TLE pana gaseste solutia buna?

[•veleandu]

In fine ..

[•Andrei1998]

Cred ca ar fi un moment bun sa dati o clarificare. 

[•freak93]

Algoritmul ala merge pentru K pasi fixati. Pentru fiecare graf exista un K minim, pentru care daca rulezi algoritmul ai sa obtii diametrul grafului, altfel spus ce se calculeaza pentru sursa voastra e la ce iteratie `raspuns` din pseudocod ajunge sa fie egal cu diametrul.

Daca se intampla cel putin la iteratia 10 atunci primti 30 de puncte, s.a.m.d.

Evaluatorul o sa crape daca nu se opreste niciodata, dar asta e imposibil.

Later Edit:
In exemplu la iteratia 3 se obtine diametrul (care este 2) si deci acel test ia 0 puncte.

[•dutzul]

solutia mea a fost evaluata dar primesc doar 50p pe pretest , asta inseamna ca mai e un pretest sau ca nu am indeplinit decat cerinta

450 - veti primi 50 de puncte

[•a_h1926]

Ai indeplinit doar cerinta partiala pentru 50 de puncte (450 de iteratii).

[•Andrei1998]

@freak93 Si daca nu se mai gasesc perechi care sa nu mai fi fost alese plecand dintr-un nod (eu de asta intrebam)?

[•a_h1926]

Daca algoritmul nu mai gaseste nicio pereche nevizitata anterior, se opreste (si implicit a gasit si diametrul). Exista intotdeauna un K pentru care gaseste diametrul.

[•Andrei1998]

Ma refeream la asta: " next <- nodul cel mai indepartat de nod_curent astfel incat niciunea din perechile (next, nod_curent) si (nod_curent, next) sa nu mai fi fost aleasa" Ce se intampla daca pe linia asta nu se gaseste nici un next cu aceasta proprietate?

[•a_h1926]

Algoritmul se opreste.

[•veleandu]

Daca nu mai ai perechi clar ai rezolvat tot.
Sa spunem ca ai varful 1, si ai luat perechile (1, 2) (1, 3) (1, 4) .. w/e
asta inseamna ca te-ai extins cu BF-ul din toate nodurile posibile, deci ai aflat raspunsul

Daca ai implementa TU problema, ai optimiza sa nu te extinzi daca next a fost vizitat, nu perechea (nod, next)

[•Impaler_009]

Deci feedback-ul la aceasta problema este complet ?

[•a_h1926]

DA

[•veleandu]

ez katka
ez 5 minute