h1. Solutii Autumn WarmUp 2006

(Creat la data de _2006-09-07_ categoria _Competitii_, autor(i) _Echipa Info-arena_)

(Categoria _Competitii_, autor(i) _Echipa Infoarena_)

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:

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. 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({~p~}), i ≤ t ≤ j, t ≤ k, p ≤ j$
$z{~t~} = x{~t~} - max(x{~k~}) + min({~p~}), i ≤ t ≤ j, t ≤ k, p ≤ j$

 
* $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~}$
$z_min = minimul din sirul z corespunzator secventei x{~st~}, x{~st+1~}... x{~dr~}$

 
* $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~}$
 

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:

@MAX(Y) = 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).

 
* @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)$.