Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Oji 2007 Probleme cls 11-12  (Citit de 4002 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
beliver_X
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« : Martie 10, 2007, 14:10:51 »

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.
« Ultima modificare: Martie 10, 2007, 14:12:30 de către soare sorin » Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #1 : Martie 10, 2007, 15:48:14 »

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 Neutral
[later edit] de fapt asta merge doar dak ai radacina fixata dar akuma am observat ca tot tu sa o determini deci nu merge Sad
« Ultima modificare: Martie 10, 2007, 15:54:34 de către Savin Tiberiu » Memorat
flo_demon
Strain
*

Karma: 20
Deconectat Deconectat

Mesaje: 46



Vezi Profilul
« Răspunde #2 : Martie 10, 2007, 16:09:00 »

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 Smile) lol poate ar fi mers mai mult, dar bc memory fucked up.
Next time s ama invazt minte sa imi rpet centroidul  Brick wall
Memorat

Marines don't die! They go to hell and regroup
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #3 : Martie 10, 2007, 18:27:25 »

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. Smile
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
beliver_X
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #4 : Martie 10, 2007, 19:56:55 »

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 Neutral
[later edit] de fapt asta merge doar dak ai radacina fixata dar akuma am observat ca tot tu sa o determini deci nu merge Sad
Aha Ma gandeam io ca ii ceva cu numarul de noduri al subarborelor, da desteptu de mine nu m-am gandit la o coada  Brick wall .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 .
Memorat
mika17
Strain
*

Karma: 8
Deconectat Deconectat

Mesaje: 33



Vezi Profilul
« Răspunde #5 : Martie 10, 2007, 20:27:28 »

Citat
    PS Daka stiti  formula de la problema 1  sa imi scrieti cum ati ajuns la ea va rog.

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 Tongue
« Ultima modificare: Martie 10, 2007, 20:35:10 de către Mihai Ionescu » Memorat
beliver_X
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #6 : Martie 10, 2007, 20:35:45 »

"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??  Mad 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. Very Happy

« Ultima modificare: Martie 11, 2007, 12:45:43 de către soare sorin » Memorat
StTwister
Client obisnuit
**

Karma: 11
Deconectat Deconectat

Mesaje: 86



Vezi Profilul
« Răspunde #7 : Martie 10, 2007, 23:10:08 »

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.
Memorat
beliver_X
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #8 : Martie 11, 2007, 12:48:52 »

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?
Memorat
svalentin
Nu mai tace
*****

Karma: 88
Deconectat Deconectat

Mesaje: 704



Vezi Profilul
« Răspunde #9 : Martie 11, 2007, 12:52:22 »

erau 20 de teste
Memorat
beliver_X
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #10 : Martie 11, 2007, 12:54:43 »

Ioi da mahh .  Brick wall ups. Tongue
Memorat
svalentin
Nu mai tace
*****

Karma: 88
Deconectat Deconectat

Mesaje: 704



Vezi Profilul
« Răspunde #11 : Martie 11, 2007, 13:06:03 »

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.

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)
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #12 : Martie 11, 2007, 13:29:12 »

si cate puncte lua solutia asta??
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

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