014 Secventa

[•Bit_Master]

Vre-un exemplu in care solutia nu are lungime k? Pt ca la o solutie ipotetica de lungime mai mare ca k i-ai taia elementele de la sfarsit sa ajunga de lungime k. Astfel ar avea prioritate in fata secventei initiale (are indicele de sfarsit mai mic), iar baza ei nu poate decat sa creasca in urma taierii, deci sa aiba o baza fie egala, fie chiar mai mare.

_______
Mai tarziu:
Da, am luat 100 considerandu-le doar pe cele de lungime k.
80 cu scanf, 100 cu stream-uri

[•mening12001]

Cod:

 

#include<fstream>
using namespace std;
int a[500000],b[500000],maxx=-30001,prim,ultim,p,u;
int main()
{ifstream f("secventa.in");
ofstream h("secventa.out");
int n,i,k,j,z;
f>>n>>z;
for(i=1;i<=n;i++)
f>>a[i];
for(i=1;i<=n;i++)
{j=i-1;
k=0;
while(j>=1&&a[j]>=a[i]&&k<z)
{k++;
j=j-1;}
prim=j+1;
j=i+1;
while(j<=n&&a[j]>=a[i]&&k<z)
{k++;
j=j+1;}
ultim=j-1;
k++;
if(a[i]>maxx&&k>=z)
{maxx=a[i];
p=prim;
u=ultim;}}
h<<p<<" "<<u<<" "<<maxx;	
return 0;}

ma poate ajuta cineva...spunandu'mi ce este gresit la aceast algoritm ?
iau doar 10 puncte ,wrong answer pe cele ramase

[•klamathix]

Ok, hai sa clarificam niste ground rules. Nu posta cod pentru debug, pentru ca cel mai des nu o sa stea nimeni sa inteleaga ce ai facut. Spune in schimb ce idee ai in spate ca sa verifici daca e corecta, iar implementarea testeaza-ti-o singur, fiindca te ajuta foarte mult.

De-asemenea, ar fi bine ca sursa sa nu arate ca o poezie de-a lui Blaga, identeaza si tu pe-acolo, mai lasa niste spatii, tot pe tine te ajuta. Nu stiu cum dovedesti sa potrivesti macar acoladele in forma asta. Best of luck

[•visanr]

Nu stiu ce n-am facut bine, dar deque + citire parsata = 70 de pct  
Imi poate spune si mie cineva ce pot sa mai optimizez? Teoretic complexitatea asta ar trebui sa intre in timp.


http://infoarena.ro/job_detail/742104?action=view-source

[•klamathix]

Nu prea e parsare ce faci acolo, fiindca citesti caracter cu caracter. Citeste tot randul cu fgets sau fread.

[•visanr]

Incercasem initial cu cin.getline si strtok, luam 60 de pct.  http://infoarena.ro/job_detail/742096?action=view-source


O sa incerc si cu fgets/fread si revin cu rezultatul


LE: 100 cu fgets, multumesc pt sfat!

[•depevlad]

Eu facusem initial problema cu o stiva, cu compexitate O(n) si o constanta de vreo 4, dar lua 80 de puncte din cauza a doua teste care dadeau TLE . Pentru cei care au aceeasi problema, sa stiti ca pentru mine parsarea a scos 100 pct. 

[•SilviuI]

Nu e necesar de folosit deque,o solutie cu RMQ se incadreaza perfect in timp.

[•klamathix]

Dar un deque e mai simplu decât un RMQ  .

[•MareSite]

Yaay, dupa atata timp, insfarsit mi-a iesit solutia

[•TeodorCotet]

Solutia in O(N) ia 80 de puncte. M-am uitat pe ultimele surse de 100 si nu am gasit niciuna care sa nu parseze citirea, ar trebuie marita limita de timp.

[•NinjaCube]

imi poate spune cineva unde gresesc ?

Cod:

for (i=1;i<=n;++i){
        fin>>x;
        if (ps==0)
            d.pop_back();
        while(x<d.front()&&!d.empty()){
            d.pop_front();
            ++ps;
            }
        d.push_front(x);
        --ps;
        if (d.back()>maxZ&&i>=k){
            maxZ=d.back();
            dr=i;
            st=i-k+1;}
    }

[•Bodo171]

Cred ca trebuie sa ai mai multa grija cum elimini elementul back din deque.

[•NinjaCube]

imi poate spune cineva ce e gresit la sursa asta

Cod:

    for (i=1;i<=n;++i){
        while(!d.empty() && v[i]<=v[d.front()]) d.pop_front();
        d.push_front(i);
        if(d.back()<=i-k)
        d.pop_back();
        if (i>=k && v[d.back()]>maxZ){
            maxZ=v[d.back()];
            dr=i;
            st=i-k+1;}
    }

[•NinjaCube]

am gasit problema, e de la citire, trebuie parsata