h1. Solutii Autumn WarmUp 2006
(Creat de '_filipb_':user/filipb la data de _2006-09-07_ categoria _Competitii_, autor(i) _Echipa Info-arena_)
*Continut scurt:*
==Include(page="template/raw")==
Articolul contine ideile de rezolvare a celor 5 probleme propuse spre rezolvare in concursul Autumn WarmUp 2006, concurs organizat in intregime de 5 dintre utilizatorii info-arena.
*Continut lung:*
==Include(page="template/raw")==
Aici puteti gasi solutiile oficiale la cele 5 probleme propuse in concurs. De precizat si ca aceasta initiativa info-arena a fost un succes, adunand un numar respectabil de participanti. Punctajele au fost mai mici decat cele asteptate, fapt ce a confirmat ca setul de probleme a fost unul capabil sa puna in dificultate nume cunoscute la olimpiadele de informatica. Iata si solutiile:
(Categoria _Competitii_, autor(i) _Echipa Infoarena_)
Aici puteti gasi solutiile oficiale la cele 5 probleme propuse in concurs. De precizat si ca aceasta initiativa infoarena a fost un succes, adunand un numar respectabil de participanti. Punctajele au fost mai mici decat cele asteptate, fapt ce a confirmat ca setul de probleme a fost unul capabil sa puna in dificultate nume cunoscute la olimpiadele de informatica. Iata si solutiile:
h2. poly
Problema este una de programare dinamica si are complexitatea $O(N)$, de constanta $2^7^ = 128$. Sa notam cu $M{~i,j~}$ lungimea celui mai lung subsir utilizand primele $i$ numere din vector astfel incat ultimul element din subsirul optim sa aiba ca divizori numerele din multimea data corespunzatoare bitilor de $1$ din $j$. Mai intai $M{~i,j~}$ = $M{~i-1,j~}$ ( nu folosim numarul al $i$-lea ). Daca dorim sa folosim si numarul al $i$-lea, atunci $M{~i,config~} = maxim(M{~i,config~}$, M{~i-1,k~} + 1)$, cu $k and config = 0$, unde config are bitii de $1$ corespunzatori numerelor din multimea data cu care se divide acest al $i$-lea numar din sirul initial. Conditia $k and config$ ne asigura ca penultimul si ultimul numar din subsir nu au amandoua vreun divizor comun din multimea data (operatia $and$ in acest context este o operatie pe biti). Rezultatul va fi $max($M{~n,0~}$, $M{~n,1~}$... $M{~n,127~}$)$. Memoria folosita poate fi $O(1)$, retinand doar ultimele doua linii ale matricei.
Problema este una de programare dinamica si are complexitatea $O(N)$, de constanta $2^7^ = 128$. Sa notam cu $M{~i,j~}$ lungimea celui mai lung subsir utilizand primele $i$ numere din vector astfel incat ultimul element din subsirul optim sa aiba ca divizori numerele din multimea data corespunzatoare bitilor de $1$ din $j$. Mai intai $M{~i,j~}$ = $M{~i-1,j~}$ ( nu folosim numarul al $i$-lea ). Daca dorim sa folosim si numarul al $i$-lea, atunci $M{~i,config~} = maxim(M{~i,config~}$, $M{~i-1,k~} + 1)$, cu $k and config = 0$, unde $config$ are bitii de $1$ corespunzatori numerelor din multimea data cu care se divide acest al $i$-lea numar din sirul initial. Conditia $k and config$ ne asigura ca penultimul si ultimul numar din subsir nu au amandoua vreun divizor comun din multimea data (operatia $and$ in acest context este o operatie pe biti). Rezultatul va fi $max(M{~n,0~}$, $M{~n,1~}$... $M{~n,127~})$. Memoria folosita poate fi $O(1)$, retinand doar ultimele doua linii ale matricei.
Un algoritm de complexitate patratica in $N$ folosind tot programarea dinamica ar fi obtinut $30-40$ de puncte.
h2. bridge
Un algoritm de complexitate $O(M + N * K)$ folosind programarea dinamica nu este foarte greu de gasit. Daca notam cu $M{~i,j~}$ numarul de moduri (modulo $666013$) de a ajunge in $i$ pasi pe scandura $j$ din pozitia initiala, atunci mai trebuie avut grija doar la relatiile de recurenta. In cazul de fata vom utiliza metoda inainte si vom trata cazurile: daca scandura $j$ este lipsa atunci $M{~i,j~} = 0$, daca scandura $j$ este teleportoare incrementam $M{~i+1,unde[j]~}$ cu $M{~i,j~}$ daca si numai daca $unde[j]$ nu este lipsa sau subreda ($unde[j]$ este destinatia teleportarii de pe scandura $j$),daca $j$ este scandura buna, incrementam $M{~i+1,j+1~}$ cu $M{~i,j~}$ si $M{~i+1,j+2~}$ cu $M{~i,j~}$ doar daca $j+2$ nu e lipsa sau subreda, etc.
Un algoritm de complexitate $O(M + N * K)$ folosind programarea dinamica nu este foarte greu de gasit. Daca notam cu $M{~i,j~}$ numarul de moduri (modulo $666013$) de a ajunge in $i$ pasi pe scandura $j$ din pozitia initiala, atunci mai trebuie avut grija doar la relatiile de recurenta. In cazul de fata vom utiliza metoda inainte si vom trata cazurile: daca scandura $j$ este lipsa atunci $M{~i,j~} = 0$, daca scandura $j$ este teleportoare incrementam $M{~i+1,unde{~j~}~}$ cu $M{~i,j~}$ daca si numai daca {$unde{~j~}$} nu este lipsa sau subreda ({$unde{~j~}$} este destinatia teleportarii de pe scandura $j$),daca $j$ este scandura buna, incrementam $M{~i+1,j+1~}$ cu $M{~i,j~}$ si $M{~i+1,j+2~}$ cu $M{~i,j~}$ doar daca $j+2$ nu e lipsa sau subreda, etc.
Avand construita matricea $M$, pentru fiecare query putem raspunde acum in $O(1)$. Exista diferite optimizari care pot fi facute si care sporesc substantial timpul de executie.
h2. secv4
Deoarece logaritmul unui produs de numere este egal cu suma logaritmilor fiecarui numar din produs, si in ipoteza ca toate numerele din sir sunt pozitive, logaritmam fiecare numar si notam cu $S{~i~}$ suma primilor $i$ logaritmi. Astfel, pentru a afla secventa de produs maxim care se termina pe pozitia $i$, este suficient sa determinam, pentru $k$ intre $i-y$ si $i-x$ care este $S{~k~}$ minim (astfel, $S{~i~} - S{~k~}$ va fi maxim, deci si produsul maxim, iar secventa va incepe pe pozitia $k+1$). Putem folosi un arbore de intervale si obtinem un algoritm $O(NlogN)$, sau o coada prin care scoatem elementele prin ambele parti (structura de date numita deque - double ended queue), obtinand complexitatea $O(N)$. Daca exista si numere negative, in momentul logaritmarii numerelor negative logaritmam opusul lor. Aplicand procedeul descris mai sus, stim sigur la final ca produsul obtinut are modulul maxim. Pentru a fi cu adevarat maxim (deci pozitiv), notam cu $semn{~i~}$ semnul produsului primelor $i$ numere. Ca secventa $<j+1, i>$ sa aiba produs maxim trebuie in plus $semn{~i~} = semn{~j~}$. Vom retine doua deque-uri, unul pentru $+$ si unul pt $-$, conform vectorului semn. Astfel, in final, suntem siguri ca produsul are semnul $+$ si, cum are si modulul maxim, are valoarea maxima ceruta.
Deoarece logaritmul unui produs de numere este egal cu suma logaritmilor fiecarui numar din produs, si in ipoteza ca toate numerele din sir sunt pozitive, logaritmam fiecare numar si notam cu $S{~i~}$ suma primilor $i$ logaritmi. Astfel, pentru a afla secventa de produs maxim care se termina pe pozitia $i$, este suficient sa determinam, pentru $k$ intre $i-y$ si $i-x$ care este $S{~k~}$ minim (astfel, $S{~i~} - S{~k~}$ va fi maxim, deci si produsul maxim, iar secventa va incepe pe pozitia $k+1$). Putem folosi un arbore de intervale si obtinem un algoritm $O(NlogN)$, sau o coada prin care scoatem elementele prin ambele parti (structura de date numita deque - double ended queue), obtinand complexitatea $O(N)$. Daca exista si numere negative, in momentul logaritmarii numerelor negative logaritmam opusul lor. Aplicand procedeul descris mai sus, stim sigur la final ca produsul obtinut are modulul maxim. Pentru a fi cu adevarat maxim (deci pozitiv), notam cu $semn{~i~}$ semnul produsului primelor $i$ numere. Ca secventa {@<j+1, i>@} sa aiba produs maxim trebuie in plus $semn{~i~} = semn{~j~}$. Vom retine doua deque-uri, unul pentru {$+$} si unul pt {@-@}, conform vectorului semn. Astfel, in final, suntem siguri ca produsul are semnul {$+$} si, cum are si modulul maxim, are valoarea maxima ceruta.
h2. parcare
Problema este exponentiala in dimensiunea matricii, dar polinomiala in numarul total de posibilitati de pozitionare al masinilor. Astfel, vom folosi un algoritm de tip BFS care garanteaza ca se ajunge la solutie intr-un numar minim de miscari. Plecam de la matricea initiala, si expandam pe rand toate starile posibile, miscand din starea curenta cate o masina pana cand nu mai exista nici o varianta noua de pozitionare a masinilor sau pana cand am scos masina A din parcare. Starile problemei le putem codifica intr-un intreg de 64 de biti. Singurele variabile sunt pozitiile masinilor. Dupa ce eliminam zidurile inconjuratoare, coordonatele nu sunt mai mari decat 7 ( 3 biti ), deci pentru pozitia unei masini vom folosi 6 biti. Concatenam pozitiile masinilor si, cum sunt maxim 10 masini, codificarea nu va avea mai mult de 60 de biti.
Problema este exponentiala in dimensiunea matricii, dar polinomiala in numarul total de posibilitati de pozitionare al masinilor. Astfel, vom folosi un algoritm de tip BFS care garanteaza ca se ajunge la solutie intr-un numar minim de miscari. Plecam de la matricea initiala, si expandam pe rand toate starile posibile, miscand din starea curenta cate o masina pana cand nu mai exista nici o varianta noua de pozitionare a masinilor sau pana cand am scos masina A din parcare. Starile problemei le putem codifica intr-un intreg de $64$ de biti. Singurele variabile sunt pozitiile masinilor. Dupa ce eliminam zidurile inconjuratoare, coordonatele nu sunt mai mari decat $7$ ( $3$ biti ), deci pentru pozitia unei masini vom folosi $6$ biti. Concatenam pozitiile masinilor si, cum sunt maxim $10$ masini, codificarea nu va avea mai mult de $60$ de biti.
Pentru a memora starile explorate vom folosi o tabela de hash. De precizat si ca numarul total de posibilitati pornind de la starea initiala este destul de redus, deci problema va rula aproape instantaneu.
h2. easy query
Un algoritm simplu de complexitate $O(N*M)$ obtine $30-50$ de puncte. Algoritmul de $100$ de puncte are complexitatea $O(MlogN)$ si foloseste arbori de intervale. Considerand o secventa $x{~i~} x{~i+1~}... x{~j~}$ este evident ca pentru ca elementele sirurilor $y$ si $z$ sa fie maxime, respectiv minime, ele trebuiesc construite astfel:
easy query
Un algoritm simplu de complexitate O(N*M) obtine 30-50 de puncte. Algoritmul de 100 de puncte are complexitatea O(MlogN) si foloseste arbori de intervale. Considerand o secventa x[i] x[i+1]... x[j] este evident ca pentru ca elementele sirurilor y si z sa fie maxime, respectiv minime, ele trebuiesc construite astfel:
y[t] = x[t] - min(x[k]) + max(x[p]), i <= t <= j, t <= k, p <= j
z[t] = x[t] - max(x[k]) + min(x[p]), i <= t <= j, t <= k, p <= j.
Pentru a calcula in timp optim valoarea P = max(y) + min(z) ne vom folosi de un arbore de intervale in urmatorul mod: fiecare nod al acestuia va constitui o secventa x[st], x[st+1]... x[dr] ( unde st si dr sunt marginile intervalului din nodul arborelui ) pe care o vom rezolva prin metoda brute force de la inceput, avand grija sa precalculam si alte valori necesare mai tarziu, cum ar fi :
min = minim(x[st], x[st+1]... x[dr])
max = maxim(x[st], x[st+1]... x[dr])
x_max_max = maxim(x[t] + maxim(x[p]) ),
st <= t <= dr si t <= p <= dr
x_max_min = minim(x[t] - maxim(x[p]) ),
st <= t <= dr si t <= p <= dr
x_min_max = maxim(x[t] - minim(x[p]) ),
st <= t <= dr si t <= p <= dr
x_min_min = minim(x[t] + minim(x[p]) ),
st <= t <= dr si t <= p <= dr
y_max = maximul din sirul y corespunzator secventei x[st], x[st+1]... x[dr]
* $y{~t~} = x{~t~}- min(x{~k~}) + max(x{~p~}), i ≤ t ≤ j, t ≤ k, p ≤ j$
* $z{~t~} = x{~t~} - max(x{~k~}) + min(x{~p~}), i ≤ t ≤ j, t ≤ k, p ≤ j$
z_min = minimul din sirul z corespunzator secventei x[st], x[st+1]... x[dr]
Pentru a calcula in timp optim valoarea $P = max(y) + min(z)$ ne vom folosi de un arbore de intervale in urmatorul mod: fiecare nod al acestuia va constitui o secventa $x{~st~}, x{~st+1~}... x{~dr~}$ ( unde $st$ si $dr$ sunt marginile intervalului din nodul arborelui ) pe care o vom rezolva prin metoda brute force de la inceput, avand grija sa precalculam si alte valori necesare mai tarziu, cum ar fi :
Avand precalculate valorile de mai sus pentru fiecare nod al arborelui in parte vom putea raspunde in timp O(logN) pentru fiecare din cele M intrebari. Fiecare subsecventa data x[i], x[i+1]... x[j] va putea fi compusa din reuniunea mai multor noduri din arborele de intervale. Acum parcurgem nodurile ce compun subsecventa data de la dreapta la stanga si vom gasi rapid valorile maxim(y) si minim(z). Presupunand ca am ajuns la nodul Q valoarea maxim(y) pana aici se calculeaza astfel:
* $min = minim(x{~st~}, x{~st+1~}... x{~dr~})$
* $max = maxim(x{~st~}, x{~st+1~}... x{~dr~})$
* $x_max_max = maxim(x{~t~} + maxim(x{~p~}) ),st ≤ t ≤ dr si t ≤ p ≤ dr$
* $x_max_min = minim(x{~t~} - maxim(x{~p~}) ),st ≤ t ≤ dr si t ≤ p ≤ dr$
* $x_min_max = maxim(x{~t~} - minim(x{~p~}) ),st ≤ t ≤ dr si t ≤ p ≤ dr$
* $x_min_min = minim(x{~t~} + minim(x{~p~}) ),st ≤ t ≤ dr si t ≤ p ≤ dr$
* $y_max = maximul din sirul y corespunzator secventei x{~st~}, x{~st+1~}... x{~dr~}$
* $z_min = minimul din sirul z corespunzator secventei x{~st~}, x{~st+1~}... x{~dr~}$
MAX(Y) = y_max(Q) = y_max_max(Q) - min(W) = x_min_max(Q)+max(W) = max(Q)+max(W)-min(W).
Avand precalculate valorile de mai sus pentru fiecare nod al arborelui in parte vom putea raspunde in timp $O(logN)$ pentru fiecare din cele $M$ intrebari. Fiecare subsecventa data $x{~i~}, x{~i+1~}... x{~j~}$ va putea fi compusa din reuniunea mai multor noduri din arborele de intervale. Acum parcurgem nodurile ce compun subsecventa data de la dreapta la stanga si vom gasi rapid valorile $maxim(y)$ si $minim(z)$. Presupunand ca am ajuns la nodul $Q$ valoarea $maxim(y)$ pana aici se calculeaza astfel:
Analog se calculeaza si minim(z).
* @MAX(Y) = maxim (y_max(Q) ; y_max_max(Q) - min(W) ; x_min_max(Q)+max(W) ; max(Q)+max(W)-min(W))@
Analog se calculeaza si $minim(z)$.
