h1. Solutii Autumn WarmUp 2006
(Categoria _Competitii_, autor(i) _Echipa Infoarena_)
(Categoria _Competitii_, autor(i) _Echipa Info-arena_)
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:
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:
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.
