dtotal = 0
  cost_stocare = 0
  pentru j de la i la 1

    cost_stocare = cost_stocare + S[j]    dtotal

    cost_stocare = cost_stocare + S[j] * dtotal

    dtotal = dtotal + D[j]
    cost_productie = F[j] + C[j]    dtotal
    cost_total = cmin[j-1] + cost_productie + cost_stocare

Folosind observatia ca fiecare functie este minima pe cel mult un interval, putem folosi un arbore de intervale pentru a stoca in el semidrepte. Aceasta este o utilizare oarecum neobisnuita a unui arbore de intervale, dar vom vedea ca este foarte utila in cazul acestei probleme. Pseudocodul solutiei este urmatorul:
==code(c) |

; calculeaza vectorii SP si DP

// calculeaza vectorii SP si DP

SP[ 0 ] = 0
DP[ 0 ] = 0
pentru i de la 1 la N
  SP[i] = SP[i-1] + S[i]
  DP[i] = DP[i-1] + D[i]

; calculeaza vectorul cmin

// calculeaza vectorul cmin

cmin[ 0 ] = 0
pentru i de la 1 la N
  finit[i] = cmin[i-1] + F[i]
  P[i] = C[i] - SP[i-1]

  [li,ri] = find_interval(i) ; gaseste intervalul [li,ri] pe care functia fi este minima

  [li,ri] = find_interval(i) // gaseste intervalul [li,ri] pe care functia fi este minima

  daca intervalul [li, ri] nu este vid
    update(li, ri, i, radacina_arborelui_de_intervale)

  cmin[i] = get_min(i) ; determina valoarea minima in punctul i dintre toate functiile existente

  cmin[i] = get_min(i) // determina valoarea minima in punctul i dintre toate functiile existente

suma = 0
pentru i de la 1 la N
  suma = suma + SP[i-1] * D[i]

==code(c) |
find_interval(i)

left=i
right=N
li=N+1
cat timp left <= right
  mid = (left+right)/2
  fi_mid_1 = finit[i]+(DP[mid]-DP[i-1])  P[i] // valoarea in punctul DP[mid+1]
  fi_mid_2 = finit[i]+(DP[mid + 1]-DP[i-1])  P[i] // valoarea in punctul DP[mid]
  fmin1=get_min(mid+1) // valoarea minima in punctul DP[mid+1]
  fmin2=get_min(mid) // valoarea minima in punctul DP[mid]
  df1 = fi_mid_1 - fmin1;
  df2 = fi_mid_2 - fmin2;
  daca (df1 &lt; 0)
 li = mid;
 right = mid - 1;
  altfel
  daca (df1 - df2 &gt; 0)
 left = mid + 1;
  altfel
 right = mid - 1;
; la sfarsit, in li se afla capatul stanga al intervalului in care fi este minima (sau N+1 daca nu exista un astfel de interval)

  left=i
  right=N
  li=N+1
  cat timp left <= right
    mid = (left+right)/2
    fi_mid_1 = finit[i]+(DP[mid]-DP[i-1]) * P[i] // valoarea in punctul DP[mid+1]
    fi_mid_2 = finit[i]+(DP[mid + 1]-DP[i-1]) * P[i] // valoarea in punctul DP[mid]
    fmin1=get_min(mid+1) // valoarea minima in punctul DP[mid+1]
    fmin2=get_min(mid) // valoarea minima in punctul DP[mid]
    df1 = fi_mid_1 - fmin1
    df2 = fi_mid_2 - fmin2
    daca (df1 < 0)
      li = mid
      right = mid - 1
    altfel
    daca (df1 - df2 > 0)
      left = mid + 1
    altfel
      right = mid - 1
// la sfarsit, in li se afla capatul stanga al intervalului in care fi este minima (sau N+1 daca nu exista un astfel de interval)

==
Functiile $update$ si $get_min$ se aplica arborelui de intervale si au complexitate $O(logN)$. Complexitatea functiei $find_interval$ este $O(log^2^N)$.

Pseudocodul functiei $update$ este prezentat in continuare:

* $*update(li,ri,i,nod)*$
* $daca intervalul corespunzator nodului nod este chiar [li,ri], atunci$
** $index[nod]=i$
* $altfel$
** $fs = fiul stanga al nodului nod$
** $fd = fiul dreapta al nodului nod$
** $daca l[fd] > ri atunci$
*** $update(li,ri,i,fs)$
** $altfel$
** $daca r[fs] < li atunci$
*** $update(li,ri,i,fd)$
** $altfel$
*** $update(li,r[fs],i,fs)$
*** $update(l[fd],ri,i,fd)$

== code(c) |
update(li,ri,i,nod)
  daca intervalul corespunzator nodului nod este chiar [li,ri], atunci
    index[nod]=i
  altfel
    fs = fiul stanga al nodului nod
    fd = fiul dreapta al nodului nod
    daca l[fd] > ri atunci
     update(li,ri,i,fs)
   altfel
   daca r[fs] < li atunci
     update(li,ri,i,fd)
   altfel
     update(li,r[fs],i,fs)
     update(l[fd],ri,i,fd)
==

h4. Functia $get_min$
Fiecare nod din arbore are o referinta catre tatal sau $(tata[nod])$. Radacina arborelui are o referinta catre o valoare nedefinita $(NEDEFINIT)$. Pseudocodul functiei $get_min$ este urmatorul:

* $*get_min(i)*$
* $nod = nodul din arbore corespunzator intervalului [i,i]$
* $val_min=infinit$
* $cat timp nod <> NEDEFINIT$
** $k=index[nod]$
** $daca k este definit atunci$
*** $fki = finit[k] + (DP[i] - DP[k-1]) * P[k]$
*** $daca fki < val_min atunci$
**** $val_min=fki$
** $nod=tata[nod]$
* $intoarce val_min$

== code(c) |
get_min(i)
  nod = nodul din arbore corespunzator intervalului [i,i]
  val_min=infinit
  cat timp nod != NEDEFINIT
    k=index[nod]
    daca k este definit atunci
      fki = finit[k] + (DP[i] - DP[k-1]) * P[k]
      daca fki < val_min atunci
        val_min=fki
    nod=tata[nod]
  intoarce val_min
==

h3. Link-uri utile

Folosind aceste valori, vom determina bitii celui de-al $M$-lea sir, unul cate unul, pornind de la al $N$-lea bit. La fiecare pas, va trebui sa determinam cate siruri incep cu bitul $0$ si cate siruri incep cu bitul $1$. La inceput, vor exista $num[N-1,3]$ siruri care incep cu bitul $0$ si $num[N-1,2]$ siruri care incep cu bitul $1$. Este evident ca, la un anumit pas, toate sirurile care incep cu $0$ se vor afla inaintea tuturor sirurilor care incep cu $1$. De aceea, daca $M$ < numarul sirurilor care incep cu $0$, bitul respectiv va fi $0$; in caz contrar, bitul va fi $1$. Daca bitul este $1$, inainte de a trece la pasul urmator, va trebui sa actualizam valoarea lui $M$, in asa fel incat sa sarim peste toate sirurile care incep cu $0$ ({$M = M - numarul de siruri care incep cu 0$), precum si sa tinem cont de faptul ca am mai consumat inca un bit de $1$. Algoritmul in pseudocod este urmatorul:

* $nrbiti = 3$
* $for i = N -> 1$
** $daca num[i-1, nrbiti] >= M atunci$
*** $bitul i este 0$
** $altfel$
*** $bitul i este 1$
*** $M = M - num[i-1, nrbiti]$
*** $nrbiti = nrbiti - 1$

== code(c) |
nrbiti = 3
for i = N -> 1
  daca num[i-1, nrbiti] >= M atunci
    bitul i este 0
  altfel
    bitul i este 1
    M = M - num[i-1, nrbiti]
    nrbiti = nrbiti - 1
==

h3. Probleme asemanatoare

O parte din acesti pointeri pot fi calculati in momentul in care, in faza de constructie a arborelui de intervale 2D, se interclaseaza coordonatele $Y$ corespunzatoare fiului stanga si fiului dreapta. Cealalta parte a pointer-ilor se calculeaza realizand inca $2$ parcurgeri ale coordonatelor $Y$ sortate, una de la stanga la dreapta si alta de la dreapta la stanga (in conditiile in care am memorat pentru fiecare coordonata $Y$ de la care din cei doi fii provine).

Unul dintre concurenti a obtinut $100$ de puncte folosind o structura de date 2D numita 'kd-tree':http://en.wikipedia.org/wiki/Kd-tree, care poate oferi aceleasi operatii ca si un arbore de intervale 2D. Diferenta consta in cantitatea de memorie folosita ($O(N)$, in loc de $O(N*logN)$), dar si in complexitatea cautarii in interiorul unui dreptunghi ($O(sqrt(N))$, in loc de $O(log^2^N)$ sau $O(logN)$ cu optimizarea mentionata).
h3. Link-uri utile