Indicatii KthSumSecv

/**
    Problema propusa va folosi urmatoarele :
    - Cautare binara pe rezultat
    - Fereastra glisanta / sliding window technique

    Enunt pe scurt : Se sorteaza crescator toate sumele
    subsecventelor dintr-un sir de valori si le punem
    intr-un tablou v. Se cere afisarea elementului v[k].
    Ex : sir : 1,2,4 , k = 5
    Subsecventele si sumele lor sunt :
    (1)-> 1
    (1,2)-> 3
    (1,2,4)-> 7
    (2)-> 2
    (2,4)-> 6
    (4) -> 4
    Sumele sortate sunt :
    1 , 2 , 3, 4 , 6 , 7.
    V[k] = 6. (k=5)(Raspunsul).

    Sa spunem ca avem n elemente.
    Vom avea n*(n+1)/2 subsecvente
    (in exemplu n = 3 -> 3*4/2 = 6 subsevente)
    Din restrictii n <= 10.000 asadar putem avea
    pana la 50 de milioane de subsecvente...

    Evident nu putem simula ce ne cere problema
    (eu nu propun probleme foarte usoare in caz de a-ti observat)

    REZOLVARE
    F(x) - returneaza cate subsecvente sunt mai mici sau egale cu x;
    Daca stim aceasta informatie stim a cata subsecventa este ultima subsecventa cu suma x.
    Deci daca gasim cel mai mic x pentru care F(x) >= k atunci si elementul k din sirul sortat
    va avea aceiasi suma;

   Sa luam un sir sortat de sume ale subsecventelor sa intelegem mai bine :

   Sir 1 2 4 6 6 6 8 10  (suma = 43)
   Poz 1 2 3 4 5 6 7 8   (Vrem sa returnam Sir[5] = 6 (acel 6 de la mijloc.)

   Cand f(x) >= k vom salva acea pozitie evident.
   k = 5 , cand F(x) < k -> st = mid+1, cand F(x) >= k -> dr = mid-1 si salvam mid ca noua solutie.

   st = 1 , dr = 43 -> mid = 21 -> F(x) = 8 (evident toate sumele sunt mai mici decat 21) (noua solutie = mid)
   st = 1, dr = 20 -> mid = 10 -> F(x) = 8 (iarasi) (noua solutie = mid)
   st = 1, dr = 9 -> mid = 5 -> F(x) = 3 (de la pozitia 4 incolo sunt mai mari sumele decat 5)
   st = 6, dr = 9 -> mid = 7 -> F(x) = 6 (noua solutie = mid)
   st = 6, dr = 6 -> mid = 6 -> F(x) = 6 (noua solutie = mid)
   st = 6, dr = 5 -> exit.  sol = 6

   De aceea luam f(x)>=k si nu doar f(x)==k, pentru ca putem avea mai multe subsecvente cu aceiasi suma.

   Acum sper ca reiese cum ne ajuta functia F(x) si cum putem folosi rezultatele ei in cautarea binara
   pentru a determina valoarea sumei de pe pozitia k. Dar pana acum am folosit doar rezultatele functiei din ochi
   pentru ca putem vedea din datele exemplului..

   Acum complexitatea solutiei va fi logN ( de la cautarea binara) * ceva (complexitatea functiei F(x))
   Dar stim deja ca n^2 nu este suficient de eficient deci e clar ca complexitatea necesara functiei F(x)
   este O(n)... Deci cam printr-o singura trecere a elementelor va trebui sa spunem cate subsecvente
   au suma mai mica sau egala decat x. Nu avem asa de multe optiuni de considerat. E clar ca vom
   avea nevoie de fereastra glisanta / sliding window technique.
   Vom retine suma elementelor de la i la j. Cand mutam i suma scade , cand mutam j suma creste.
   Asadar daca suma de la i la j <= x atunci toate subsecventele cu j fixat acolo si cu i crescand
   pana la j vor avea si ele suma mai mica sau egala decat x (suma scade) deci putem din start
   sa crestem sol cu lungimea intervalului (j - i + 1).
   Daca suma de la i la j este mai mare decat x atunci mutam i pana cand suma este mai mica sau egala.

   Aveti aici functia F(x) in cod.
   */
   int F(int x)
   {
      int sol = 0; // cate subsecvente au suma mai mica sau egala decat x
      int i = 1, j = 1, // cei doi pointeri
      int sum = 0; // suma de la i la j
      while(i<=n&&j<=n)
      {
          sum+=v[j];
          while(sum>x) //ne asiguram ca suma e mai mica sau egala decat x.
            sum-=v[i], i++; //mutam capatul din stanga al intervalului.
          sol+=(j - i + 1); //crestem sol cu lungimea intervalului.
          j++;
      }
      return sol;
   }