Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-02-12 11:25:03.
Revizia anterioară   Revizia următoare  

//Articolul nu este complet ediat. O sa-l editez maine, acum ma duc sa ma culc pt ca sunt rupt :D Somn usor tuturor.

In numele echipei Winter Challenge 2007 felicit toti participantii si le urez succes in viitoare confruntari. Totodata tin sa multumesc lui Mugurel Ionut Andreica si lui Sorin Stancu-Mara pentru ca au acceptat sa propuna subiecte alaturi de mine. Nu in ultimul rand tin sa multumesc echipei infoarena pentru suportul tehnic acordat si sa-i rog sa ma ierte daca i-am stresat (prea tare).

Mult noroc in continuare,
Bogdan A. Stoica

Chiftea

problema usoara, clasele 9-10

Se observa ca figura se obtine dintr-un patrat de latura radical(n), la care se mai adauga niste patratele, solutia fiind 4*radical(n) (pentru n patrat perfect) sau 4*(radical(n)+1) (-2, dupa caz :p).
O solutie care calcula aceste valori in O(n) nu ar fi obtinut punctaj maxim.

Mall

problema medie, clasele 9-10

Calculam A[i, j] = castigul maxim pe care-l obtine Varu daca repartizeaza j ingrijitori primelor i firme, unde A[i, j] = maxim(A[l, j-k]) (0 < l < i, 0 ≤ k ≤ j).
O solutie care calcula in O(N4) aceasta recurenta ar fi obtinut 16 puncte.
O solutie care calcula in O(N3), folosind matricea V[i, j] = maxim(A[k, j]) (0 < k < i), obtinea 32 de puncte.
O solutie care calcula in O(N2), folosind un deque ce calcula in O(1) maximul (pentru linia i si coloana j) dintre V[i, 1], V[i, 2], ..., V[i, j-1], obtinea 100 de puncte.

Fear

problema usoara, clasele 11-12

In ciuda proprietatii un pic ciudate care priveste valoarea fricii dintr-o intersectie, problema se reduce la aflarea fluxul maxim avand orasul 1 ca sursa si orasul N ca destinatie. Pentru a realiza acest lucru vom logaritma (in baza 2, e sau 10) costurile muchiilor ce se dau in fisierul de intrare. Dintre toate aceste noi costuri o vom lua pe cea maxima (vmax). Algoritmul va fi urmatorul:

  1. vom trimite frica (din orasul 1) cu o valoare V (initial, V = vmax) pana cand frica nu va mai putea ajunge la destinatie.
  2. injumatatim pe V si reluam algoritmul de la pasul 1.

Smen

problema grea, clasele 9-10 - problema medie, clasele 11-12

Incepem prin a normaliza toate numerele din sir si pe A si B, adunand tuturor valoarea 200. Astfel vom lucra numai cu numere pozitive. Apoi problema se rezolva prin programare dinamica. Sortam in ordine crescatoare elementele si apoi clauculam A[i, j, k] = numarul minim de operatii ce se efectueaza asupra primelor i numere a.i. sa obtinem exact j elemente distincte iar ultimul element sa nu depaseasca valoarea k.
A[i, j, k] se poate obtine ca fiind maximul dinntre:

  1. A[i-1, j, k-1] + |Val_initiala[i]-k| (daca vrem ca valoarea initiala a celui de-al i-lea element sa fie k, dar sa nu-mi creeze un alt element distinct).
  2. A[i-1, j-1, k-1]+|Val_initiala[i]-k| (daca vrem ca valoarea initiala a celui de-al i-lea element sa fie k si sa-mi creez inca un element dinstinct)
  3. A[i-1, j, k-1] (nu cresc nici valoarea elementului i, nici numarul de elemente distincte)

Pentru reconstituire vom lucra cu o matrice B[i, j, k] care ia valori din multimea {0, 1, 2}, semnificand conditia din care a provenit starea (i, j, k). Se observa ca aceasta solutie ar fi obtinut foloseste foarte multa memorie (O(N*K*(B-A)) si ar fi obtinut doar 40% din punctaj.

Solutia 100 de puncte incepe prin a observa ca, la un pas, nu sunt folosite decat "linia" curenta si "linia" anterioara din matricea A. Pentru reconstituire se poate folosi urmatorul smen: retinem din 14 in 14 "linii" informatiile din matricea A (cea de la prima solutie), adica R[1, j, k] = $A[1, j, k]$ ($1 ≤ j ≤ K$ si A+200 ≤ k ≤ B+200), R[2, j, k] = A[15, j, k] ($1 ≤ j ≤ K$ si A+200 ≤ k ≤ B+200), R[3, j, k] = A[29, j, k] ($1 ≤ j ≤ K$ si A+200 ≤ k ≤ B+200), etc. Dupa ce am completat matricea R, reluam dinamica de la coada la cap si ne vom folosi doar de matricea R. Astfel la pasul i vom reconstitui doar liniile care se afla intre liniile R[i, j, k] si R[i-1, j, k] ($1 ≤ j ≤ K$ si A+200 ≤ k ≤ B+200), adica intre ($i-1$)$*14+1$ si i*14+1 in matricea de la prima solutie. Astfel o sa avem o memorie de O(14*K*(B}-{A)).

O alta solutie care obtinea punctaj maxim este transformarea problemei intr-una de cuplaj de cost minim. Cele doua multimi de noduri se construiau in felul urmator: prima multime era reprezentata de sirul initial, iar cea de-a doua era reprezentata de valorile intregi cuprinse in intervalul [A, B]. Se introduc N*($B-A$) muchii de capacitate 1, o muchie de la un nod ce leaga elementul X din prima multime si elementul Y din a doua multime avand costul |X-Y|. Prima multime se leaga de o sursa fictiva prin muchii de cost 0 si capacitate 1, iar cea de-a doua multime de o destinatie fictive prin muchii de cost 0 si capacitate 1. Tinandu-se cont ca in destinatie trebuie sa se obtina fluxul minim K, se aplica acest algoritm avand grija sa minimizam costul.

Doipe

problema grea, clasele 11-12

Vom calcula P[i, j] = numarul de permutari ale multimii {1,$2$,..,$i$} care respecta primele i-1 relatii ale sirului de relatii si in care ultimul numar al permutarii este numarul j. In mod evident, rezultatul dorit va fi dat de suma P[N, 1] + P[N, 2] + .. + P[N, N].
Pentru calculul lui P[i, j] vom observa ca, eliminand numarul j din permutare, obtinem i-1 numere distincte care pot fi renumerotate pentru a forma o permutare a multimii {1,$2$,..,$i-1$}. Mai exact, orice numar x mai mare decat j este renumerotat cu valoarea x-1. In conditiile acestei renumerotari, avem urmatoarele 2 cazuri:

  • daca relatia i-1 este "<", atunci P[i, j] = P[i-1, 1] + P[i-1, 2] + .. + P[i-1, j-1]
  • daca relatia i-1 este ">", atunci P[i, j] = P[i-1, j] + P[i-1, j+1] + .. + P[i-1, i-1]

Cazul "de baza" este P[1, 1] = 1. Relatiile date sunt corecte, deoarece pentru orice permutare ce corespunde lui P[i-1, x] se poate aplica operatia de renumerotare inversa (relativ la j), obtinand un sir de i-1 numere distincte din multimea {1,$2$,..,$i$}\j care respecta primele i-2 relatii. La sfarsitul acestui sir se poate adauga numarul j, obtinand o permutare cu i elemente care respecta primele i-1 relatii.
Implementarea imediata a relatiilor de recurenta mentionate se poate realiza foarte usor in complexitate O(N3). Memorand sumele partiale SP[x] = P[i-1, 1] + P[i-1, 2] + .. + P[i-1, x] putem calcula P[i, j] in timp O($1$), reducand complexitatea la O($N2$).