h2. 'Curcubeu':problema/curcubeu

Vom considera colorarile incepand cu ultima. Parcurgem intervalul asociat ei si de fiecare data cand gasim o casuta necolorata ii asociem valoarea $C$<sub>$i$</sub>. Aceasta solutie are complexitatea $O(N^2^)$ si ar fi obtinut 20 de puncte. Pentru punctaj maxim este nevoie de un rafinament. Analizand solutia anterioara, observam ca vom parcuge de foarte multe ori casute deja colorate, lucru inutil si consumator de timp. Pentru fiecare pozitie $i$ vom mentine o valoare $Next[i]$, semnficand faptul ca intervalul $[i, Next[i]-1]$ contine doar casute colorate (initial $Next[i] = i$). Astfel, la colorarile urmatoare, vom putea "sari" peste secvente intregi de pozitii anterior colorate. Pentru a implementa eficient aceasta solutie, putem folosi una din cele doua euristici ale structurilor pentru multumi disjuncte, cea a comprimarii drumului. Puteti citi mai multe despre structuri pentru multimi disjuncte in "Cormen":http://zhuzeyuan.hp.infoseek.co.jp/ita/chap22.htm sau "aici":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure. Complexitatea finala este $O(N log* N)$. De mentionat faptul ca se pot obtine 50 de puncte implementand solutii de complexitate $O(N log N)$ folosind arbori de intervale sau un maxheap.

Vom considera colorarile incepand cu ultima. Parcurgem intervalul asociat ei si de fiecare data cand gasim o casuta necolorata ii asociem valoarea $C{~i~}$. Aceasta solutie are complexitatea $O(N^2^)$ si ar fi obtinut 20 de puncte. Pentru punctaj maxim este nevoie de un rafinament. Analizand solutia anterioara, observam ca vom parcuge de foarte multe ori casute deja colorate, lucru inutil si consumator de timp. Pentru fiecare pozitie $i$ vom mentine o valoare $Next[i]$, semnficand faptul ca intervalul $[i, Next[i]-1]$ contine doar casute colorate (initial $Next[i] = i$). Astfel, la colorarile urmatoare, vom putea "sari" peste secvente intregi de pozitii anterior colorate. Pentru a implementa eficient aceasta solutie, putem folosi una din cele doua euristici ale structurilor pentru multumi disjuncte, cea a comprimarii drumului. Puteti citi mai multe despre structuri pentru multimi disjuncte in "Cormen":http://zhuzeyuan.hp.infoseek.co.jp/ita/chap22.htm sau "aici":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure. Complexitatea finala este $O(N log* N)$. De mentionat faptul ca se pot obtine 50 de puncte implementand solutii de complexitate $O(N log N)$ folosind arbori de intervale sau un maxheap.

h2. 'Trompeta':problema/trompeta

* $csum[i] =$ suma cantitatilor de combusitibil din benzinariile $[1..i]$ ; $csum[i] = csum[i-1]+c[i]$
* $cright[i] =$ suma costurilor de a transporta cantitatile necesare de combustibil de la benzinaria $N$ la fiecare din benzinariile $[i..N]$ ; $cright[i] = cright[i+1] + c[i] * (d[N] - d[i])$

* $cleft[i] =$ suma costurilor de a transporta cantitatea dorita de combustibil de la benzinaria $N$ la benzinariile $[i..N]$ ; $cleft[i] = cleft[i-1] + c[i] * (d[i] - d[ 1 ])$

* $cleft[i] =$ suma costurilor de a transporta cantitatea dorita de combustibil de la benzinaria $N$ la benzinariile $[1..i]$ ; $cleft[i] = cleft[i-1] + c[i] * (d[i] - d[ 1 ])$

Cu acesti vectori, <tex> \displaystyle\sum_{p = j' + 1}^j c_{p} * (d_{j} - d_{p}) </tex> se scrie ca fiind egala cu $cright[j{~1~}+1] - cright[j+1] - (csum[j] - csum[j{~1~}]) * (d[N] - d[j])$. In mod similar, <tex> \displaystyle\sum_{p = j' + 1}^j c_{p} * (d_{p} - d_{j'}) </tex> se scrie ca fiind egala cu $cleft[j] - cleft[j{~1~}] - (csum[j] - csum[j{~1~}])*(d[j{~1~}] - d[ 1 ])$.