1433 Album

[•a_h1926]

Aici puteti discuta despre problema Album.

[•gabrielinelus]

Eu am facut un algoritm greedy : am sortat fiecare sir crescator apoi le-am considerat numere mari si am sortat liniile matricei cum ar veni ... Apoi am fixat prima linie ca fiind cea mai mica si iterez prin restul liniilor sa vad care o pot pune dupa prima si sa se si vada in poza. Apoi repet treaba asta cu noi linii pana cand le pun pe toate , si de cate ori repet, atatea poze fac. Iau 0 puncte ... imi spune si mie cineva va rog cum s-ar rezolva problema asta ?  Multumesc anticipat !

[•freak93]

Uite aici ai articoul cu solutii http://www.infoarena.ro/concurs-mihai-patrascu-2013/solutii desi ai nevoie de cunostii mai avansate ca sa intelegi de ce aceea e solutia. De la pasul 2 la pasul 3 problema se transforma in a acoperi un graf aciclic tranzitivizat cu un numar minim de lanturi, asta se rezolva prin acel cuplaj.