Iopds

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 * Xi * Xi-1 > 0, pentru ca aceasta sa fie respectata atunci atat Xi cat si Xi-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 2poz-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 Vi. Pe D il putem calcula astfel D[i] = suma(D[j] + 1) daca A * Vi2 + B * Vj2 + C * Vi * Vj > 0. Aceasta formula reiese din observatia ca daca Vi si Vj respecta conditia, atunci il putem pune pe Vi la sfarsitul oricarui subsir care se termina cu Vj. Aceasta solutia are complexitatea O(N2).
Problema poate fi rezolvata si in complexitate O(NlogN) rezolvand inegalitatea in functie de parametrul Xi 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.