690 Euro2

[•astronomy]

Aici puteţi discuta despre problema Euro2.

[•Stigma]

ceva special la testele 3 si 5? 
EDIT:  nevermind! trebuia mai multa atentie la restrictii!

[•Florian]

A facut cineva de 100, calculand cmlsc in O(n^2) ?

[•Mirage]

Ma indoiesc avand in vedere ca n=10000.
Dar poti sa calculezi cmlsc in n*log(n)

[•marin]

In enunt zice ca:

Numerele reprezentand valoarea unui Euro in RON au toate exact patru cifre in partea zecimala si sunt distincte

Mai intai am trimis o sursa in care memorez datele ca long int inmultindu-le cu 10000. Iau 80 puncte.
Cand lucrez cu ele ca float iau 100.

[•andrei-alpha]

Poate ai uitat sa faci undeva conversi cand aveai operatii pe tipuri diferite de date.
Alfel ar trebui sa mearga . 

[•f.v.anton]

trebuie inclus neaparat valoarea maxima, adica raportarile sa creasca pana la valoarea maxima, si apoi sa scada? sau pur si simplu trebuie gasit nr. maxim de raportari. Eu as inclina spre var. nr 2. pt ca spre exemplu pt un fisier de intrare de forma

Max
val
val
val

nu cred ca ai cum sa introduci maximul in raportari. so?

[•Florian]

Da. Varianta a doua e corecta. 

[•f.v.anton]

ok multumesc, am sa ma apuc de ea maine, sau poimaine .

[•xtreme]

ceva special la testele 3 si 5? 
EDIT:  nevermind! trebuia mai multa atentie la restrictii!

Nici mie nu imi da corect pe aceste teste.De ce nu iti dadea corect?

[•DraStiK]

ceva special la testele 3 si 5? 
EDIT:  nevermind! trebuia mai multa atentie la restrictii!

Nici mie nu imi da corect pe aceste teste.De ce nu iti dadea corect?

Reciteste aceasta restrictie si fi sigur ca o respecti:

Raportarile alese de Banca Nationala trebuie sa contina o secventa crescatoare (formata din cel putin doua elemente), urmata de o secventa descrescatoare (formata din cel putin un element)

[•xtreme]

Asa fac alegerea subsecventei maximale:

Cod:

freopen("euro2.out","w",stdout);int i,max=2;
      for(i=2;i<=n-1;i++)  /* curs[i].stanga(dreapta)-nr de valori mai mici sau egale ca si valoarea elementului i cu indice mai mic(mai mare) ca i */
             if(curs[i].stanga>=1 && curs[i].dreapta>=1 && max<(curs[i].stanga+curs[i].dreapta)) 
                              max=curs[i].stanga+curs[i].dreapta;
      printf("%d\n",max+1);
      fclose(stdout);

Asa calculez vectorul curs:

Cod:

void solvea()
     {int i,j,max;
      for(i=2;i<=n;i++)
          {max=-1;
           for(j=1;j<i;j++)
               if(max<curs[j].stanga && curs[j].val<=curs[i].val)    max=curs[j].stanga;
           curs[i].stanga=max+1;
         }
      }
void solveb()
     {int i,j,max;
      for(i=n-1;i>=1;i--)
         {max=-1;
          for(j=n;j>i;j--)
              if(max<curs[j].dreapta && curs[j].val<=curs[i].val)    max=curs[j].dreapta; 
          curs[i].dreapta=max+1;
         }
      }

Consider ca respect toate restrictiile.

[•funkydvd]

Desi mi-am dat toate testele care mi-au venit in cap, nu inteleg de ce nu iau decat 70 de puncte. Imi puteti da un test  ca sa imi dau seama ce gresesc?
Eu retin in max [ i ] scmax daca vectorul se termina pe pozitia i, iar in min[ i ] scmin daca vectorul incepe pe pozitia i.
La sfarsit afisez maximul dintre min[ i ] si max[n-i+1], i apartinand intervalului (2;n-1) si am grija ca min[ i ] si max [n-i+1] sa fie mai mari decat 1.
Ce gresesc?

[•Florian]

Rezolvi in O(NlogN) ? Si ce anume primesti: TLE sau WA ?

[•nautilus]

Solutia la problema asta nu consta in:
- determinarea maximului din sirul de valori
- determinarea lungimii Subsirului Crescator Maximal de la primul element din vector pana la pozitia maximului (determinat anterior)
- determinarea minimului din sirul de valori de dupa pozitia maximului
- determinarea lungimii Subsirului Descrescator Maximal de pe pozitia maximului+1 pana la pozitia minimului (determinat anterior)
- adunarea celor 2 lungimi si afisarea rezultatului ?

Eu am facut asa dar numai la 3 teste imi da corect, iar la restul WA...

[•Mishu91]

Primești incorect pentru că algoritmul tău nu este corect. Dacă ai ceva de genul

Cod:

9
3,567
4,000
3,000
3,678
3,679
3,712
3,812
3,567
3,345

Tu vei zice că răspunsul este 3, considerând doar secvența formată din primele 3 elemente, dar răspunsul corect este 7.

[•popoiu.george]

Fac la fel ca in solutie. Pentru fiecare i de la 1 la N calculez scmax ce se termina cu i si subsirul descrescator maximal de la i pana la N.

Astea le calculez in O(NlogN) si pe testele [8,15] iau TLE, iar pe testele 5 si 3 WA.

Any hints plz? 

[•nando]

Cat ar trebui sa fie rezultatul pentru testul:

Cod:

8
3.0
3.1
3.2
3.4
3.4
3.4
3.4
3.3

?

[•mathboy]

5 este rezultatul.

[•Nemultumitu]

Mi se pare ambiguu formulat:

Raportarile alese de Banca Nationala trebuie sa contina o secventa crescatoare (formata din cel putin doua elemente), urmata de o secventa descrescatoare (formata din cel putin un element).

Nu inteleg, de exemplu, daca o secventa de tipul
3.1
3.2
3.3
3.5

este solutie valida - adica acel "cel putin un element" include si elementul maxim sau nu? Iau WA pe testele 3 si 5, si din ce s-a discutat pana acum inteleg ca solutia sta in formularea asta. Poate cineva sa-mi traduca va rog?

[•eudanip]

Mi se pare ambiguu formulat:

Raportarile alese de Banca Nationala trebuie sa contina o secventa crescatoare (formata din cel putin doua elemente), urmata de o secventa descrescatoare (formata din cel putin un element).

Nu inteleg, de exemplu, daca o secventa de tipul
3.1
3.2
3.3
3.5

este solutie valida - adica acel "cel putin un element" include si elementul maxim sau nu? Iau WA pe testele 3 si 5, si din ce s-a discutat pana acum inteleg ca solutia sta in formularea asta. Poate cineva sa-mi traduca va rog?

Da, este valida.

[•Bit_Master]

Daca cursul pentru euro o sa iasa pana la urma din intervalul 3 - 4, o sa se actualizeze problema?
_________________

Oricum, eu m-am gandit in felul urmator:
Fac subsir crescator maximal pe numere (in O(NlogN)) si retin pentru intervalele
[1,1]; [1,2]; ...; [1,n] lungimea celui mai lung subsir comun.
Rastorn v-ul si repet ca sa obtin pt intervalele [n,n];[n-1,n]...;[1,n].

Apoi incerc in toate cele n-2 pozitii (sau in fine n, ca am incercat si asa) sa stabilesc
unde se termina sirul crescator si incepe cel descrescator
si retin maximul sumelor scmax(1,i) + sdmax(i+1,n), punand conditii
scmax(1,i) >= 2            (crescatoare)
sdmax(i+1,n) >= 1       (descrescatoare)

Totusi, iau 95p. E vre-un caz particular?

[•PlayLikeNeverB4]

Probabil pici (tu,eu inainte si restul cu 90+ puncte) unul dintre urmatoarele teste:

Cod:

4
3.1123
3.1124
3.1125
3.1124

Cod:

4

Cod:

4
3.1123
3.1124
3.1125
3.1126

Cod:

0

Cod:

4
3.1126
3.1125
3.1124
3.1123

Cod:

0

(primul l-am pus pentru comparatie si ultimele doua ca sa scot in evidenta restrictiile pentru alegerea raportarilor)

[•Bit_Master]

Dar de ce raspunsul e 0 la a doua? Nu sunt bune
3.1123
3.1124
3.1125
ca secvanta crescatoare si
3.1126
ca secventa descrescatoare?

____________

never mind. Am luat 100. Vad ca secventa descrescatoare trebuie sa inceapa descrescator fata de cea crescatoare.

[•lucian666]

imi dati si mie un test de intrare pt problema asta...ca iau 5 pct dar algoritmul mi se pare corect....adica fac cel mai lung subsir crescator+cel mai lung subsir descrescator;