h1(#iopds). 'Iopds':problema/iopds

h2. Aceasta pagina trebuie sa ramana private pana la sfarsitul rundei!

Se pot obtine $30$ de puncte folosind o abordare de tip backtracking, construind pe rand toate sirurile care respecta conditia din enunt.
De asemeni, $30$ de puncte se obtin folosindu-ne de propritatea $A = B = 0.000$ si $C > 0.000$. Atunci relatia se transforma in $C * X{~i~} * X{~i-1~} > 0$, pentru ca aceasta sa fie respectata atunci atat $X{~i~}$ cat si $X{~i-1~}$ trebuie sa aiba aceiasi signatura, de unde rezulta ca subsirul va fi format fie numai din numere pozitive, fie numai din numere negative. Fie $poz$ numarul de numere pozitive din sirul initial, atunci ele pot forma $2^poz^-poz-1$ subsiruri. Pentru a afla subsirurile de numere negative se procedeaza asemanator.
Un program care pentru $N < 12$ calculeaza rezultatul folosind backtracking iar pentru $A = B = 0.000$ calculeaza rezultatul cu ajutorul formulei ar obtine $50$ de puncte.
Solutia de 100 de puncte contruieste rezultatul folosind programarea dinamica, sa consideram $D[i] = numarul de subsiruri care il au pe ultima pozitia pe V{~i~}$. Pe $D$ il putem calcula astfel $D[i] = suma(D[j] + 1)$ daca $A * V{~i~}^2^ + B * V{~j~}^2^ + C * V{~i~} * V{~j~} > 0$. Aceasta formula reiese din observatia ca daca $V{~i~}$ si $V{~j~}$ respecta conditia, atunci il putem pune pe $V{~i~}$ la sfarsitul oricarui subsir care se termina cu $V{~j~}$. Aceasta solutia are complexitatea O(N^2^).
Problema poate fi rezolvata si in complexitate $O(NlogN)$ rezolvand inegalitatea in functie de parametrul $X{~i~}$ si folosind o structura de date care permite calcularea sumei pe un interval si update-ul unui element in $logN$, ramane ca tema pentru cei interesati.

private

public