Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2006-11-18 14:40:43.
Revizia anterioară   Revizia următoare  

Solutii - Summer Challenge Doi

(Creat de DITzoneCAdrian Diaconu DITzoneC la data de 2006-08-11 categoria Competitii, autor(i) Adrian Diaconu si Cosmin Negruseri)

Sah

Prima observatie ar fi ca pentru a ne asigura ca intr-o regiune numarul de casute albe este egal cu numarul de celule negre este suficient ca aria regiunii sa fie para.

Plecand de la aceasta observatie si de la faptul ca N este mereu par propunem urmatoarea impartirea tablei si voi demonstra apoi ca indeplineste conditiile din enunt. Impartim tabla in benzi de latime 2 (pentru a asigura paritatea ariilor). Apoi prima banda o lasam intreaga, iar pentru urmatoarele banda i se va inmparti in i-1 si N-i+1. Astfel se vor creea N-1 regiuni. Se observa ca toate dreptunghiurile difera intre ele prin lungime deoarece se folosesc toate numerele de la 1 la N mai putin N/2.

Pentru a demonstra ca N-1 este numarul maxim de regiuni care se poate creea vom presupune ca se poate imparti tabla in N regiuni. Vom considera ca se folosesc cele mai mici arii posibile, dar acestea trebuie sa fie toate pare. Suma ariilor va fi 2+4+6+..+2*N= 2*(N*(N+1)/2)=N*N+N ceea ce ar depasi tabla noastra.

Plimbare

Evident ca o conditie necesara ca un graf turneu (asa se numesc grafurile ca cel mentionat in enunt in care exista exact un arc intre oricare doua noduri) sa aiba un circuit hamiltonean ar fi ca graful sa fie tare conex, daca nu ar fi tare conex atunci evident nu poate exista un circuit intre doua noduri aflate in doua componente tari conexe diferite. Aceasta conditie este si suficienta asa cum va reiesi din algoritmul pe care il vom explica mai jos.

Astfel pentru graful nostru vom determina componentele tari conexe, si vom cauta un circuit hamiltonean in cea mai mare dintre acestea. De acum ne vom concentra doar asupra nodurilor acestei componente. Evident ca aceasta componenta conexa contine cel putin un circuit, pentru a determina unul facem o cautare in adancime, si trebuie sa gasim la un moment dat o muchie de intoarcere (pentru ca altfel componenta nu ar fi tare conexa). Vom imparti nodurile din aceasta componenta in patru multimi: A multimea nodurilor din circuit, B multimea nodurilor din afara circuitului pentru care exista si arce orientate de la noduri din circuit la ele, si arce orientate de la ele la noduri din circuit, C multimea nodurilor din afara circuitului pentru care exista numai arce ce pornesc din circuit inspre noduri, si D multimea nodurilor pentru care toate arcele intre ele si noduri din circuit sunt orientate de la ele inspre circuit. Puteti observa ca nodurile din multimea B pot fi inserate tot timpul in circuit undeva inlocuind un arc intre doua noduri ale circuitului cu doua arce de la un nod al circuitului la nodul multimii B si apoi la alt nod din circuit. Inserarea unui astfel de nod dureaza maxim O(n) pasi, alti O(n) pasi ar fi necesari pentru modificarea multimilor B, C, D pentru ca circuitul s-a schimbat. Dupa ce nu ne mai ramane nici un nod in B. Ramanem doar cu noduri de tip C sau D. Orice nod din multimea C va avea cel putin un arc orientat spre alt nod din multimea D pentru ca altfel nu am fi intr-o componenta tare conexa. Acum aceste doua noduri legate printr-o muchie dinspre C inspre D pot fi inserate in circuit. Astfel am aratat o cale practica de a mari lungimea circuitului pana cand epuizam toate nodurile.

Daca folosim metoda de determinare a componentelor tari conexe folosind un algoritm eficient de complexitate O(N + M), atunci algoritmul are complexitatea O(N2) pentru ca la fiecare inserare facem O(n) pasi. Un algoritm mai eficient nu putem obtine deoarece M = N(N-1)/2, deci si citirea datelor e O(N2). N a fost fixat la 100 pentru ca am vrut sa punem accent asupra ideii de gasire a circuitului si nu asupra algoritmului de determinare eficienta a componentelor tari conexe.

TreiD

Aceasta problema e similara cu problema Bmatrix din arhiva si a fost propusa pentru a favoriza utilizatorii inraiti :).
Trei dreptunghiuri pot avea ca amplasare relativa doar 6 pozitii diferite:
+------+    +------+    +------+
|      |    |      |    |  |   |
+------+    +--+---+    +  +   +
|      |    |  |   |    |  |   |
+------+    +  +   +    +------+
|      |    |  |   |    |      |
+------+    +------+    +------+
si rotatiile cu 90 de grade ale acestora.

Pentru a determina pentru fiecare configuratie solutia optima putem incerca orice impartire posibila cu doua linii in trei zone a dreptunghiului initial. Apoi ne trebuie pentru fiecare dreptunghi de tipul [1..i]x[1..j], [1..i][j..m], [i..n]x[1..j], [i..n]x[j..m], [i..j]x[1..m] si [1..n]x[i..j].
Ca sa determinam suma numerelor din un dreptunghi [r1..r2]x[c1..c2] folosim o matrice B[i][j] care e suma elementelor din [1..i]x[1..j], avand aceasta matrice calculata putem determina ca suma elementelor din dreptunghiul [r1..r2]x[c1..c2] este B[r2][c2] - B[r1 - 1][c2] - B[r2][c2 - 1] + B[r1 - 1][c1 - 1]. Pentru a calcula B[i][j] eficient parcurgem elementele matricii initiale A in ordine si avem ca B[i][j] = A[i][j] + B[i][j - 1] + B[i- 1][j] - B[i-1][j-1].

Vom explica cum determinam submatricea optima pentru dreptunghiul [i..j]x[1..m] in O(n), celelalte dreptunghiuri putand fi determinate intr-un mod asemanator. Avem trei cazuri posibile: linia de sus a dreptunghiului optim nu coincide cu linia i, si astfel putem lua informatia despre el din rezultatul calculului pentru dreptunghiul [i+1..j]x[1..m], al doilea caz e cand linia de jos nu coincide cu linia j, acum luam rezultatul optim pentru dreptunghiul [i..j-1]x[1..m]. Al treilea caz cand dreptunghiul optim se sprijina pe liniile i si j il putem rezolva in O(n) asemanator problemei de determinare a unei subsecvente de suma maxima pe un vector C. C[k] va fi egal cu suma elementelor din dreptunghiul [i..j] x [k..k] (deci suma elementelor din banda [i..j] ce sunt pe coloana k).

Pentru a determina subsecventa de suma maxima a sirului C, vom folosi vectorul sum[k] = C[k] + C[k-1] + ... + C[1]. Astfel suma elementelor C[k..l] este egala cu sum[l] - sum[k - 1]. Pentru a determina subsecventa de suma maxima ce se termina in l trebuie sa gasim cea mai mica sum[k - 1] pentru a maximiza expresia sum[l] - sum[k - 1]. Astfel obtinem urmatorul cod:
int min_sum = 0;
int best = - infinit;
for (int k = 0; k < m; k++) {
    if (best < sum[l] - min_sum)
        best = sum[l] - min_sum;
    if (sum[l] < min_sum) min_sum = sum[l];
}
return best;

Acest algoritm are complexitatea O(n).

Astfel algoritmul calculeaza in O(n) valoarea optima pentru O(n2) zone, deci in total avem un algoritm ce consuma O(n2) memorie si are complexitatea O(n3) ca timp.