Solutii

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 multumesc intregii echipe infoarena pentru suportul tehnic acordat si ii rog sa ma ierte daca i-am stresat (prea tare).

Mult noroc in continuare,
Bogdan A. Stoica

Chiftea

problema usoara, clasele 9-10

Vom nota cu Pk, perimetrul minim al figurii ce contine k patratele de latura unitate. In mod evident, acesta depinde numai de patratelele ce formeaza marginea figurii.
Vom trata intai cazul in care N este patrat perfect pornind de la N = 1, cu P1 = 4. Pentru N = 4, construind toate figurile posibile se observa ca cea de perimetru minim are forma unui patrat cu latura 2, deci P4 = 4*2 = 8. Continuand procedeul, se demonstreaza cu ajutorul principiului inducitei matematice ca Pt = 4*[radical(t)] (cu [x] s-a notat partea intreaga a lui x), oricare ar fi t patrat perfect.
Pentru al doilea caz, cel in care N nu este patrat perfect, figura noastra porneste tot de la un patrat de latura [radical(N)]. Este evident faptul ca pentru ca PN sa fie minim, trebuie sa avem cat mai putine patratele (pe margine) carora li se aduna mai mult de o latura la perimetru (cu alte cuvinte trebuie sa avem cat mai putine patratele care sa formeze colturi). Va trebui, deci, sa adaugam pe marginile patratului format N-[radical(N)]*[radical(N)] patratele. Astfel solutia devine 4*[radical(N)] pentru N patrat perfect, 4*[radical(N)]+2 pentru cazul in care acoperim maxim o latura cu patratele sau 4*[radical(N)]+4 pentru cazul in care acoperim maxim 2 laturi cu patratele.
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]+Castig[l, k]) (0 < l < i, 0 ≤ k ≤ j), unde Castig[i, j] = castigul pe care-l obtine Varu de la firma i daca acesteia ii repratizaza exact j ingrijitori.
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]+Castig[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.

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 calculam 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 dintre:

  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 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.

Fear

problema usoara, clasele 11-12

In ciuda proprietatii un pic nenaturale care priveste valoarea fricii dintr-o intersectie, problema se reduce la aflarea fluxului maxim avand orasul 1 ca sursa si orasul N ca destinatie. Pentru realizarea acestui 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.

Aceasta metoda poarta denumirea de "Flux maxim prin scalare". O alta abordare care ar fi mers la fel de bine este cea folosind algoritmul de flux maxim Ford Fulkerson.

Doipe

problema grea, clasele 11-12

Prima solutie corecta este de complexitate O(N*2N). Se calculeaza o matrice P[i, R] = numarul de permutari cu i elemente, care respecta sirul de relatii R (R este un numar binar de i - 1 biti, care codifica un sir de relatii). Putem calcula aceste valori pe baza valorilor calculate pentru P[i - 1, R'], variind pozitia in care este asezat in cadrul permutarii cel de-al i-lea element. Aceasta solutie nu se incadreaza, insa, nici in limita de timp, nici in cea de memorie.
Ideea solutiei de punctaj maxim este urmatoarea: 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).