infoarena

Cineva cu inima buna  sa imi zica si mie cum ar fi trebuit sa fac problema 2 de la 11-12(Cezar) ca mi-ma batut capu 3 ore la Oji 2007 si nu am reusit sa o rezolv.
      http://olimpiada.info/oji2007/probleme/subiecte_oji_2007.zip
    PS Daka stiti  formula de la problema 1  sa imi scrieti cum ati ajuns la ea va rog.

nush sigur dak merge dar e o idee. Faci un DF si ptr fiecare nod retii cate noduri are subarborele care il are ca radacina. Apoi iei si bagi toti vecinii radacinii intr-o coada si iei maximu de acolo (sa zicem x), si pui strada r-x (r e radacina). Scoti elementu respectiv din coada si bagi vecinii lui si repeti algoritmu de k ori. (atentie cand bagi cate o muchie nu pui de fiecare data de la radacina la nod  muchie ci de la nod la tatal sau). Sper ca ai inteles ce am zis si sper sa fie bine :|
[later edit] de fapt asta merge doar dak ai radacina fixata dar akuma am observat ca tot tu sa o determini deci nu merge :(

Exact asa am facut si eu, numai am selctat pe rand fiecare nod ca si radacina a arborelui apoi
un df pentru determinare cate noduri are orice nod in subarbore, cu acelasi df calculezi cati senatori folosesc o anumita muchie (adica cu cat s-ar reduce costul daca ai selecta-o ca si gratuita), si tot in acelasi df calculezi costul total daca nici o muchie nu ar fi gratuita.
Apoi am pornit un bf dinn radacina cu rad initial bagata in coada.
Si pentru fiecare nod din coada costul muchiilor lui spre vecini (costul calculat de df-ul anterior (cati senatori folosesc muchia)) si selectezi pe cel mai mare. (mergea aici un heap da eram out of time)
Bagi noul nod spre care ai muchia cu care se reduce cel mai mult costul in coada, si repeti de K ori. \

Bineinteles.. e departe de optim algoritmul ce l-am aplicat.. dar still a mers de 25 pcte :)) lol poate ar fi mers mai mult, dar bc memory fucked up.
Next time s ama invazt minte sa imi rpet centroidul  ](*,)

Pastrezi pentru fiecare frunza o pondere ca fiind suma distantelor de la toate nodurile care sunt spre "exteriorul" grafului, scoti si bagi frunze pana cand ramai cu  K + 1 noduri, adica exact K muchii. Ai O(N log N) daca folosesti heapuri. Am luat 30 cu aceasta idee datorita balariei de Borland C++ si a pointerilor din el. :)

:aha: Ma gandeam io ca ii ceva cu numarul de noduri al subarborelor, da desteptu de mine nu m-am gandit la o coada  ](*,) .Pacat ca nu primim punctaje partiale pentru aflarea radacini ca aia era simpla. Parcurgeai cu BF dintr-un nod (1) si faceai media distantelor  de la nodul 1 la celelalte noduri si atunci radacina era situata la distanta medie fatza de 1 .

hm ideea mea la prob1 , fol permutari cu repetitie in felu urm

faceai un bk ca sa generezi toate cifrele a1 a2 a3 ... ak  , pt kre a1*a2*a3*...*ak = b
de ex pt a=1000,b = 210 aveai
2 3 5 7     
5 6 7  asta puneai in stiva
si mai luai un vec kre retinea de kte ori se repeta o cifra in fiecare prod
pt prod de mai sus aveai v[2]=v[3]=v[5]=v[7]=1 , in rest 0  , un bk recursiv optimizat mergea ffrpd

dupaia pt fiecare produs i gasit i=1..p adunai la solutie a! / (a - nr_cifre_din_produs_i)! v[2]!...v[9]!    (formula perm cu repetitie)  ,
de ex pt primu prod aveai 1000!/ (1000 - 4)! 1!0!0!1!....0! , bineinteles nu calc factorialu ci ramaneai cu 997*998*999*1000 si faceai toate operatiile mod 9973 , sau kt zic ei acolo , si adunai la suma

cred k era suficient sa iei un punctaj bun , chiar f bun la prob asta
sunt curios lumea ce sol a gasit la prob asta , in special cei kre au luat 100 :P

"O implementare posibilă utilizează metoda GREEDY, O(n*(n-k)) sau O((n-k)*log(n))

Se elimină succesiv, dintre frunzele existente la un moment dat, frunza de cost minim. Toate nodurile au costul iniţial 1. La eliminarea unei frunze, se incrementează cu 1 costul tatălui acesteia. Validitatea metodei rezultă din observaţia că, la eliminarea unei frunze oarecare, tatăl acesteia poate deveni frunză la rândul lui, dar cu un cost strict mai mare decât al frunzei eliminate.

Se poate reţine arborele cu ajutorul listelor de adiacenţă (liniare sau organizate ca arbori de căutare), iar frunzele se pot memora într-un minheap de costuri, structură care se actualizează în timp logaritmic." 
   Asta ii solutia oficiala la Cezar. Perfect logic asai??  :x Is curios cine so fi gandit sa o faca asa . Ca de obicei era o rezolvare prea simpla sa te gandesti la ea. Inca un 0 la lista ea de punctaje speciale la OJI. :D

Eu am luat 75 alegand nodul cu gradul maxim ca nod de pornire pt DF. Nu stiu sigur daca am luat WA sau TLE, dar probabil TLE pentru ca nu am folosit heap (a inceput borlandu sa faca fitze si am zis sa nu risc).

Cu toate ca alegerea nodului cu grad maxim nu garanteaza intotdeauna solutie optima, merge pe majoritatea.

Cum se putea lua 5 puncte la problema Cezar? Ca vad ca multi o luat punctaje cu 5 in capat. Poti sa iei numa jumate de test sau cum?

erau 20 de teste

Ioi da mahh .  ](*,) ups. :P

Cam asa am facut si eu, dar DFurile facute iterativ sa nu crape stiva si dupa ce am ales senatul, muchiile le-am ales cu un heap.. din pacate am uitat ca int este pe 16-biti (de fapt, am terminat in ultimul minut si nu am mai avut timp sa 'finisez' sursa)

si cate puncte lua solutia asta??