ECN Sapientia si selectie ACM - faza pe centre - Cluj -

[•MciprianM]

Astazi a avut loc concursul din titlu(intre orele 11-16 aprox.). Problemele le gasiti aici: http://www.mitis.ro/ecn/pages/ECN-2010-problems.pdf
Daca doriti, m-ar bucura daca s-ar discuta niste solutii in acest subiect. Eu cel mai tare sunt curios cum se face problema J . Nu stiu de ce, dar am impresia ca se gaseste si pe infoarena; sau doar mi se pare?

[•blasterz]

Pai din cate am inteles eu (la problema J) nu iei in considerare ultimul element si faci permutari de n - 1 element si pt fiecare permutare inserezi ultimul element . Nu pare prea grea.

[•MciprianM]

Cred ca nu vorbim de aceeasi pb. Problema J e cea numita "Squares" in care trebuie sa acoperi o matrice cu patrate

[•blasterz]

ah scuze.... ma uitam la F )

Nu merge o dinamica de genul:

dp[ i ] [ j ] = numarul minim de a acoperi un dreptunghi i x j

si zici

dp[ i ][ j ] = min (dp[ i ][ j ] , 1 + min (dp [i - k] [ j  ] + dp [ k][ j - k ] , dp [ i - k][ j - (j - k) ] + dp [ i][ j - k], dp [ i - k][ k ] + dp[ k ][j - k] + dp [i - k][ j - k]));

practic pui un patrat de k x k intr-un colt
nu garantez ca e buna

[•MciprianM]

  ai putea sa explici putin?
L.E: ai mai modif relatia intre timp
                  

[•blasterz]

daca ai un dreptunghi i x j si pui intr-un colt un patrat de k x k
tu obtii fie 3 dreptunghiuri
fie in 2 modalitati 2 dreptunghiuri

[•MciprianM]

Acuma am inteles relatia data de tine. Am incercat sa-i gasesc hibe, dar n-am reusit
Dar nu reusesc nici o demonstratie.
L.E. E posibil sa fi gasit ceva. Formula ta presupune ca patratul dintr-un colt sa aiba acelasi nivel fie pe orizontala fie pe verticala(fie amandoua) cu restul impartirii. Mie mi se pare ca nu permite ca unele cazuri sa fie luate in considerare... nu stiu; poate reusesti o demonstratie

[•Marius]

Cod:

bst[i][j] = 1, dacă i = j
bst[i][j] = min { min{bst[i][k] + bst[i][j - k]}, min{bst[k][j] + bst[i - k][j]}}

adică, un dreptunghi de laturi (i, j) îl descompui în alte două dreptunghiuri pe orizontală ori pe verticală. Mie mi-a mers aşa.

[•MciprianM]

  Ati vazut testele postate pe site-ul ecn? http://www.mitis.ro/ecn/pages/p_problem.php?lang=ENG&UserAction=-1&

Acum nu ma mai mira nimic.

[•blasterz]

=)))  misto inputu la J )

[•Marius]

Caterincă concursul ăsta.

[•MciprianM]

Sa nu fim rai, totusi Poate ca acele cazuri au fost alese special astfel incat sa mearga doar o solutie corecta.
Stiti cum se zice... Esentele tari se tin in sticlute mici
L.E.: