Diferente pentru autumn-warmup-2007/solutii/runda-1 intre reviziile #10 si #30

Diferente intre titluri:

autumn-warmup-2007/runda-1/solutii
Solutii Autumn Warmup, Runda 1

Diferente intre continut:

h2. 'Banuti':problema/banuti
Notam cu $min$ valoarea minima. Se observa ca pentru o suma oarecare $s$, daca toate sumele din intervalul $(s,s+min]$ pot fi obtinute, atunci toate sumele $> s$ pot fi obtinute la randul lor. (Pentru a va convinge, in caz ca aveti neclaritati, simulati un knapsack). Se construieste un graf cu $min$ noduri, nodul $x$ semnificand restul $x$ la impartirea cu $min$. Se defineste $cost[x]$, suma minima care poate fi obtinuta $(s)$, cu proprietatea ca $s%min=x$ (restul impartirii sumei la $min$ este $x$); @cost[0]=0@. Se observa ca daca putem obtine o suma $s$, atunci putem obtine toate sumele $s+k*min$ (care au acelasi rest), unde $k>0$. In acest graf fiecare bancnota (de valoare $v$), formeaza o muchie intre nodul $y$ si nodul $(y+v)%min$, cu costul $v$, unde $y$ apartine $[0,min)$. Daca acest graf nu este conex atunci nu avem solutie. Daca este conex, atunci solutia se afla in $max(cost[x])$, $x$ apartine $[0,min)$, care poate fi aflata cu Dijkstra. Mentionez faptul ca graful ar avea teoretic $N*min$ muchii. Pe cazul general, $N>min$, deci unele muchii sunt in plus (conform principiului cutiei). Graful pe care se face rezolvarea ar trebui sa aiba $~min^2^$ muchii. Complexitatea finala este $O(min^2^)$.
Notam cu $min$ valoarea minima. Se observa ca pentru o suma oarecare $s$, daca toate sumele din intervalul $(s,s+min]$ pot fi obtinute, atunci toate sumele $> s$ pot fi obtinute la randul lor. (Pentru a va convinge, in caz ca aveti neclaritati, simulati un knapsack). Se construieste un graf cu $min$ noduri, nodul $x$ semnificand restul $x$ la impartirea cu $min$. Se defineste $cost[x]$, suma minima care poate fi obtinuta $(s)$, cu proprietatea ca $s%min=x$ (restul impartirii sumei la $min$ este $x$); @cost[0]=0@. Se observa ca daca putem obtine o suma $s$, atunci putem obtine toate sumele $s+k*min$ (care au acelasi rest), unde $k>0$. In acest graf fiecare bancnota (de valoare $v$), formeaza o muchie intre nodul $y$ si nodul $(y+v)%min$, cu costul $v$, unde $y$ apartine $[0,min)$. Daca acest graf nu este conex atunci nu avem solutie. Daca este conex, atunci solutia se afla in $max(cost[x])-min$, $x$ apartine $[0,min)$, care poate fi aflata cu Dijkstra. Mentionez faptul ca graful ar avea teoretic $N*min$ muchii. Pe cazul general, $N>min$, deci unele muchii sunt in plus (conform principiului cutiei). Graful pe care se face rezolvarea ar trebui sa aiba $≈min^2^$ muchii. Complexitatea finala este $O(min^2^)$.
h2. 'Renovare':problema/renovare
Vom reduce problema la flux maxim de cost minim astfel: pentru fiecare muchie $a b c cst$ cu semnificatia din enunt vom adauga $2$ muchii in retea, una de capacitate $c$ si cost $0$ si inca una de capacitate infinit si cost $cst$. De asemenea vom conecta nodul $1$ la o sursa auxiliara printr-o muchie de capacitate $x$ si cost $0$. Apoi se ruleaza algoritmul de flux maxim de cost minim in reteaua noua.
 
h2. 'Plan':problema/plan
h2. 'Numar de Divizori':problema/ndiv
Construim graful componentelor tare conexe si in continuare ne vom referi numai la acest graf. Plasam in multimea $X$ nodurile cu grad de intrare 0, iar in multimea $Y$ nodurile cu grad de iesire 0. Vom gasi in continuare un mod de a construi $max(cardX, cardY)$ sosele si este clar ca acest numar e minim deoarece din fiecare nod din $X$ trebuie sa intre macar o muchie, iar din fiecare nod din $Y$ trebuie sa iasa macar o muchie. In continuare ne vom construi un set maximal (atentie, maximal != maxim) de perechi $(x{~1~}, y{~1~}), (x{~2~}, y{~2~}) ... (x{~k~}, y{~k~})$ astfel incat $x{~1~}, x{~2~} .. x{~k~}$ apartin lui $X$ iar $y{~1~}, y{~2~}.. y{~k~}$ apartin lui $Y$. Mai mult exista drum in graf de la $x{~i~}$ la $y{~i~}$. Acest set se poate construi simplu efectuand cate o parcurgere din fiecare nod a lui $X$. Adaugam muchie de la $y{~1~}$ la $x{~2~}$, $y{~2~}$ la $x{~3~}$ ... $y{~k~}$ la $x{~1~}$. In continuare adaugam muchii de la fiecare nod ramas din $Y$ la un nod ramas din $X$ pana cand vom avea noduri doar in $X$ sau doar in $Y$. Pentru acele noduri adaugam o muchie de la ele la $x{~1~}$ sa zicem, sau de la $x{~1~}$ la ele in functie daca sunt din $X$ sau din $Y$. Am adaugat cate muchii ne-am propus, acum sa vedem daca respecta proprietatea ca avem un drum de la orice nod la orice nod. Dupa ce am construit acel set maximal si practic am construit un ciclu adaugand muchiile, nodurile care au mai ramas din multimea $X$ au drum de la ele la un nod din ciclu, iar cele din multimea $Y$ ramase au drum de la un nod din ciclu la ele. Deci cand consideram doua noduri $A$ si $B$, cu $A$ din $X$ si $B$ din $Y$ si dintre cele care au ramas dupa alegerea nodurilor din setul maximal, si tragem muchie de la $B$ la $A$ vom avea drum de la nodurile din ciclu la $A$, la $B$ si de la ele la nodurile din ciclu. Acelasi lucru se intampla si in momentul cand raman noduri doar din $X$ sau doar din $Y$, vom avea drum de la un nod din ciclu la ele si invers. Deci daca consideram un nod oarecare $P$, acest nod fie este pe ciclu, fie exista drum de la el la ciclu si invers, adica exista drum de la el spre toate nodurile si de la toate nodurile spre el. Pentru nodurile care nu sunt din $X$ sau din $Y$ avem macar un drum de la ele la un nod din $Y$ si de la un nod din $X$ la ele, deci respecta proprietatea.
 
h2. 'Numar de Divizori':problema/ndiv
 
Se afla solutia pentru intervalul $[1, A-1]$ si $[1, B]$ si se face diferenta. Pentru un interval $[1, N]$ si un numar $X$, se afla numarul de numere din interval care se divid la $X$ prin aflarea catului $N / X$. O simpla solutie ar fi pentru fiecare $X = 1 2 ... N$ se face suma lui $N/X$. Evident nu intra in timp. Daca se scrie sirul $N/X$ cu $X$ de la $1$ la $N$ se observa ca termenii sirului sunt in ordine descrescatoare. De exemplu sa vedem pentru $N = 12$, vom avea sirul $N/X$ : $12/1$, $12/2$, $12/3$ ... $12/12$ care este $12, 6, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1$. Solutia se bazeaza pe faptul ca aceste numere se repeta pe anumite intervale. Astfel se iau toate numerele $i$ de la $1$ la $sqrt(N)$ si se vor tine intr-un vector sortate valorile: $i$ si $N/i$. Acum pentru doua pozitii consecutive in acest vector vom avea doua valori: $X1$ si $X2$ si $N/X1$ = $N/X2$. Si orice numar din intervalul $[X1, X2]$, sa zicem $Y$ va avea $N/Y$ = $N/X1$. Acum se iau toate pozitiile consecutive in vectorul format si se aduna la solutie $(N/X1)*(X2-X1+1)$ (lungimea intervalului). Corectitudinea acestei solutii se bazeaza pe faptul ca daca ar fi sa imparti numarul $N$ la toate numerele de la $1$ la $N$, se obtin $2*sqrt(N)$ diferite caturi. De exemplu nu poti sa imparti $12$ la ceva mai mic egal cu $12$ si sa obtii catul $11$. Complexitatea va fi $O(sqrt(N))$.

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.