Album

[•a_h1926]

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.

[•Dddarius95]

2 ore sau 1 ora? ... sa stim care e greseala:D

[•a_h1926]

Timpul alocat pentru intrebari va fi de 2 ore .

[•Dddarius95]

ok.ms

[•Dddarius95]

Bafta tuturor ! 

[•lupvasile]

De cate ori putem trimite sursa la o problema?

[•a_h1926]

De cate ori doriti.

[•Cristy94]

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  

[•a_h1926]

Raspunsul este 5.

[•lupvasile]

Nu este obligatoriu ca in toate pozele sa apara toate clasele?

[•a_h1926]

Toate clasele trebuie sa faca parte din fiecare poza.

[•geniucos]

Cum se facea problema asta?M-am chinuit foarte mult si nu am gasit nici o solutie.

[•a_h1926]

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

[•Dddarius95]

mai detaliat?

[•SebiSebi]

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. 

[•geniucos]

Cum faci asta cu cuplaj?M-am prins cum sa construiesc graful dar nu inteleg la ce te-ar ajuta cuplajul.

[•a_h1926]

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.

[•geniucos]

Multumesc!Am inteles.Imi poti explica cum se facea si rectangles?

[•Cristy94]

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 ) tot incorect .

Frumoase problemele oricum

[•Kira96]

Smechera solutia 

[•geniucos]

Cand vor fi bagate problemele in arhiva?

[•a_h1926]

Ne vom stradui sa le adaugam cat mai repede, dar din motive intemeiate, nu putem acum.

[•Mihai22e]

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.

[•classius]

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:

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.

[•Mihai22e]

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