Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Album  (Citit de 6126 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
a_h1926
Echipa infoarena
Nu mai tace
*****

Karma: 317
Deconectat Deconectat

Mesaje: 385



Vezi Profilul
« : August 17, 2013, 08:43:53 »

Aici se pot pune întrebări legate de problema Album de la Concursul Mihai Patrascu 2013.

Timpul alocat întrebărilor este de 2 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
Dddarius95
Client obisnuit
**

Karma: 30
Deconectat Deconectat

Mesaje: 66



Vezi Profilul
« Răspunde #1 : August 17, 2013, 08:48:18 »

2 ore sau 1 ora?Very Happy ... sa stim care e greseala:D
Memorat
a_h1926
Echipa infoarena
Nu mai tace
*****

Karma: 317
Deconectat Deconectat

Mesaje: 385



Vezi Profilul
« Răspunde #2 : August 17, 2013, 08:49:46 »

Timpul alocat pentru intrebari va fi de 2 ore Smile.
Memorat
Dddarius95
Client obisnuit
**

Karma: 30
Deconectat Deconectat

Mesaje: 66



Vezi Profilul
« Răspunde #3 : August 17, 2013, 08:50:10 »

ok.ms
Memorat
Dddarius95
Client obisnuit
**

Karma: 30
Deconectat Deconectat

Mesaje: 66



Vezi Profilul
« Răspunde #4 : August 17, 2013, 08:58:37 »

Bafta tuturor !  Very Happy
Memorat
lupvasile
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 13



Vezi Profilul
« Răspunde #5 : August 17, 2013, 09:09:34 »

De cate ori putem trimite sursa la o problema?
Memorat
a_h1926
Echipa infoarena
Nu mai tace
*****

Karma: 317
Deconectat Deconectat

Mesaje: 385



Vezi Profilul
« Răspunde #6 : August 17, 2013, 09:10:21 »

De cate ori doriti.
Memorat
Cristy94
De-al casei
***

Karma: 37
Deconectat Deconectat

Mesaje: 128



Vezi Profilul
« Răspunde #7 : August 17, 2013, 10:56:54 »

Hmm, iau incorect pe testele de feedback, insa nu am gasit niciun test sa dea gresit.

Pentru


10 10
1 2 3 4 5 1 2 3 4 5
10 9 8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2 1 1
4 4 4 4 4 5 5 5 5 5
1 2 3 1 2 3 1 2 3 1
7 8 9 7 8 9 7 8 9 7
1 2 3 4 5 1 2 3 4 5
10 10 10 10 10 10 10 10 10 10
6 6 6 6 6 6 6 6 6 6
2 3 4 6 7 2 3 4 6 7


Raspunsul este 6, nu? Sau am inteles eu gresit problema  Cry
Memorat
a_h1926
Echipa infoarena
Nu mai tace
*****

Karma: 317
Deconectat Deconectat

Mesaje: 385



Vezi Profilul
« Răspunde #8 : August 17, 2013, 10:58:32 »

Raspunsul este 5.
Memorat
lupvasile
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 13



Vezi Profilul
« Răspunde #9 : August 17, 2013, 11:01:20 »

Nu este obligatoriu ca in toate pozele sa apara toate clasele?
Memorat
a_h1926
Echipa infoarena
Nu mai tace
*****

Karma: 317
Deconectat Deconectat

Mesaje: 385



Vezi Profilul
« Răspunde #10 : August 17, 2013, 11:03:43 »

Toate clasele trebuie sa faca parte din fiecare poza.
Memorat
geniucos
Vorbaret
****

Karma: 21
Deconectat Deconectat

Mesaje: 199



Vezi Profilul
« Răspunde #11 : August 17, 2013, 14:03:31 »

Cum se facea problema asta?M-am chinuit foarte mult si nu am gasit nici o solutie. d'oh!
Memorat
a_h1926
Echipa infoarena
Nu mai tace
*****

Karma: 317
Deconectat Deconectat

Mesaje: 385



Vezi Profilul
« Răspunde #12 : August 17, 2013, 14:06:33 »

Poti construi un graf acilic pe care trebuie sa il acoperi cu un numar minim de lanturi. Acest lucru il poti face cu cuplaj.
Memorat
Dddarius95
Client obisnuit
**

Karma: 30
Deconectat Deconectat

Mesaje: 66



Vezi Profilul
« Răspunde #13 : August 17, 2013, 14:07:21 »

mai detaliat?Very Happy
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #14 : August 17, 2013, 14:09:25 »

Poti construi un graf orientat in care exista muchie (u,v) daca si numai daca clasa u ar fi vizibila daca ar sta in spatele clasei v. Se poate demonstra usor ca graful este aciclic. Problema s-a redus la una clasica: minimum path cover in directed acyclic graph, ceea ce se poate rezolva in timp polinomial.  Ok
Memorat
geniucos
Vorbaret
****

Karma: 21
Deconectat Deconectat

Mesaje: 199



Vezi Profilul
« Răspunde #15 : August 17, 2013, 14:10:21 »

Cum faci asta cu cuplaj?M-am prins cum sa construiesc graful dar nu inteleg la ce te-ar ajuta cuplajul.
Memorat
a_h1926
Echipa infoarena
Nu mai tace
*****

Karma: 317
Deconectat Deconectat

Mesaje: 385



Vezi Profilul
« Răspunde #16 : August 17, 2013, 14:12:46 »

Vei construi un graf bipartit in care in ambele multimi ai nodurile de la 1 la N. In acest graf duci muchie de la nodul x din stanga la nodul y din dreapta daca in graful initial exista muchia orientata x->y. Un cuplaj maxim in graful bipartit va determina acoperirea minima cu lanturi.
Memorat
geniucos
Vorbaret
****

Karma: 21
Deconectat Deconectat

Mesaje: 199



Vezi Profilul
« Răspunde #17 : August 17, 2013, 14:18:37 »

Multumesc!Am inteles.Imi poti explica cum se facea si rectangles? Smile
Memorat
Cristy94
De-al casei
***

Karma: 37
Deconectat Deconectat

Mesaje: 128



Vezi Profilul
« Răspunde #18 : August 17, 2013, 14:22:49 »

Vei construi un graf bipartit in care in ambele multimi ai nodurile de la 1 la N. In acest graf duci muchie de la nodul x din stanga la nodul y din dreapta daca in graful initial exista muchia orientata x->y. Un cuplaj maxim in graful bipartit va determina acoperirea minima cu lanturi.

Am stat 3 ore la problema asta, si cu sortari, si cu flux si nimic Smile) tot incorect Sad.

Frumoase problemele oricum Very Happy
Memorat
Kira96
Client obisnuit
**

Karma: 36
Deconectat Deconectat

Mesaje: 69



Vezi Profilul
« Răspunde #19 : August 17, 2013, 15:01:48 »

Smechera solutia  Applause
Memorat
geniucos
Vorbaret
****

Karma: 21
Deconectat Deconectat

Mesaje: 199



Vezi Profilul
« Răspunde #20 : August 17, 2013, 16:02:05 »

Cand vor fi bagate problemele in arhiva?
Memorat
a_h1926
Echipa infoarena
Nu mai tace
*****

Karma: 317
Deconectat Deconectat

Mesaje: 385



Vezi Profilul
« Răspunde #21 : August 17, 2013, 16:13:07 »

Ne vom stradui sa le adaugam cat mai repede, dar din motive intemeiate, nu putem acum.
Memorat
Mihai22e
Client obisnuit
**

Karma: 20
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #22 : August 17, 2013, 16:17:47 »

Vreau si eu o parere despre solutia mea:
M-am gandit sa aplic o strategie greedy; la fiecare pas (adica la fiecare poza facuta), incerc sa fac in asa fel incat sa se vada cat mai multe clase (care n-au aparut si in alte poze), in felul urmator: la inceput sortez elevii din fiecare clasa dupa inaltimea lor si apoi incerc sa sortez clasele in asa fel incat daca clasa i poate fi asezata inaintea clasei j la poza astfel incat sa se vada toti elevii din ambele clase, clasa i va fi pe o pozitie inaintea clasei j in sirul sortat al claselor. Acum incerc sa iau un numar maxim de clase astfel incat sa fie vizibile toate la poza; pentru asta voi face un subsir crescator maximal in K dimensiuni. Dupa ce am gasit valoarea Max = lungimea maxima a unui subsir crescator, marchez toate clasele care au format acest subsir ca si folosite: used[clasa] = true si apoi trec la pasul urmator (urmatoarea poza), unde voi forma din nou un subsir maximal crescator, avand grija sa nu folosesc decat clasele unde used[clasa] = false. Algoritmul se repeta pana cand used[j] = true, pentu orice 1 <= j <= N. Complexitatea totala e Nr_pasi*N*logN = N^2*logN.
Eu am gresit implenetarea in timpul concursului, dar nu gasesc niciun contraexemplu.
Memorat
classius
Strain


Karma: -2
Deconectat Deconectat

Mesaje: 9



Vezi Profilul
« Răspunde #23 : August 17, 2013, 17:09:35 »

Vreau si eu o parere despre solutia mea:
M-am gandit sa aplic o strategie greedy; la fiecare pas (adica la fiecare poza facuta), incerc sa fac in asa fel incat sa se vada cat mai multe clase (care n-au aparut si in alte poze), in felul urmator: la inceput sortez elevii din fiecare clasa dupa inaltimea lor si apoi incerc sa sortez clasele in asa fel incat daca clasa i poate fi asezata inaintea clasei j la poza astfel incat sa se vada toti elevii din ambele clase, clasa i va fi pe o pozitie inaintea clasei j in sirul sortat al claselor. Acum incerc sa iau un numar maxim de clase astfel incat sa fie vizibile toate la poza; pentru asta voi face un subsir crescator maximal in K dimensiuni. Dupa ce am gasit valoarea Max = lungimea maxima a unui subsir crescator, marchez toate clasele care au format acest subsir ca si folosite: used[clasa] = true si apoi trec la pasul urmator (urmatoarea poza), unde voi forma din nou un subsir maximal crescator, avand grija sa nu folosesc decat clasele unde used[clasa] = false. Algoritmul se repeta pana cand used[j] = true, pentu orice 1 <= j <= N. Complexitatea totala e Nr_pasi*N*logN = N^2*logN.
Eu am gresit implenetarea in timpul concursului, dar nu gasesc niciun contraexemplu.

Criteriul dupa care sortezi clasele nu este complet, deoarece nu ai o metoda sigura de a le ordona in orice caz, dar sa zicem ca le ordonezi lexicografic iar pentru urmatorul test:

Citat
n=5,k=4
1 1 4 9
1 3 8 10
5 6 9 9
6 7 9 11
6 8 9 10

Sunt 3 subsiruri formate din:
1 si 5
2 si 4
3

In functie de cum faci dinamica tie iti pot iesi 4 subsiruri:
1 si 4
2
3
5

Acum, daca tot am comentat aici, as vrea o parere despre ideea mea:
Am sortat fiecare clasa dupa inaltime iar dupa aceea am sortat clasele lexicografic.
Am construit un graf orientat ,arcul de la x la y reprezentand faptul ca sirul y poate sta in spatele sirului x.
Pentru fiecare componenta slab conexa a grafului am facut o sortare topologica iar dupa fiecare sortare adunam la rezultat numarul de noduri de pe nivelul cu cele mai multe noduri a componentei slab conexe.
Memorat
Mihai22e
Client obisnuit
**

Karma: 20
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #24 : August 17, 2013, 17:26:45 »

Da, cred ca ai dreptate. Am omis faptul ca ordinea in care formezi subsirul conteaza. Aveam senzatia ca merge pentru ca in timpul concursului cand am implementat aflarea subsirului maximal in N^2 (deci complexitatea totala N^3) mi-a trecut toate testele pe care n-am luat TLE
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

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