1216 Crescator

[•wefgef]

Aici puteţi discuta despre problema Crescator.

[•S7012MY]

o mica greseala :

numere naturale intregi

[•informatician28]

Nu cumva cea mai lunga secventa crescatoare este 1 2 4 5 ? 

[•informatician28]

Scuze, am facut o mica confuzie, m-am lamurit!

[•VisuianMihai]

ce au special primele 3 teste? Iau incorect doar pe ele

[•TheNechiz]

Nu sunt sigur dacă am înțeles problema.  
Pentru:
In:

Cod:

6
1 2 3 4 5 6

Out:

Cod:

21
6

Cele 21 de secvențe:

1
12
123
1234
12345
2
23
234
2345
23456
3
34
345
3456
4
45
456
5
56
6

 
?

În fiecare șir sunt cel puțin n secvențe crescătoare?

in:

Cod:

5
5 4 3 2 1

out:

Cod:

5
1

in:

Cod:

 10
1 2 3 4 5 4 3 1 2 3

out:

Cod:

23
5

?

[•Schumi]

Da, ai minim n secvente crescatoare. E corect ce iti da pe acele teste.

[•darkseeker]

Cod:

l * l - (l * ( l - 1))/2 

In codul tau rezultatul intermediar (l * l) si rezultatul final poate depasi tipul int. Incearca sa folosesti long long.

[•TheNechiz]

Nu era asta . Sigur greșeala e la algoritm,dar nu găsesc niciun test pentru care să nu meargă.Mă puteți ajuta? 

[•Schumi]

Pe testul

Cod:

10
1 2 3 5 4 4 3 1 2 6

iti pica solutia. Raspunsul e 20 4, iar tie iti da 19 4.

[•TheNechiz]

" 4  4 " este o secvență crescătoare?


Am făcut o modificare și pentru testul tău obțin:

Cod:

20
4

Dar tot iau 0 puncte.Mai poți să-mi dai un test? 

[•Schumi]

Algoritmul e bun. Aparent problema vine de la afisare. Tu dai enter dupa ce afisezi prima valoare si dupa o afisezi pe a doua. Trebuie sa afisezi cum arata si exemplul, adica sa pui spatiu intre cele doua valori. E aiurea ca se intampla asta. Ar trebui facut un eval pentru problema asta ca sa nu se mai intample chestii de genul.

[•TheNechiz]

Nu pot să cred că am greșit asta.
Mulțumesc pentru ajutor.

[•Schumi]

In enunt nu e preciat cum sa le afisezi, iar de obicei nu conteaza cum le afisezi atata timp cat sunt valori intregi.

LE: Gata, s-a modificat enuntul.

[•Sapientia]

Cod:
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("crescator.in");
ofstream g("crescator.out");
int main()
{
    int n,v[100000],i,max=1,s,j,nr;
    bool ok;
    f>>n;
    for(i=1; i<=n; i++)
        f>>v;
    f.close();
    s=n;
    for(i=1; i<=n-1; i++)
    {
        j=i;ok=1;nr=0;
           do
        {
            j++;
            if (v[j]>v[j-1])
              { s++; nr++;}
               else ok=0;
               if (nr>max) max=nr;
        }
        while (ok);
        }
        if (max>1) max++;
        g<<s<<" "<<max;
        g.close();
        return 0;
}
Obtin doar 40 de puncte..complexitatea e cu mult mai mica decat O(nxn).O mica idee cineva?

[•SebiSebi]

Complexitatea e O(n*n). Gandeste-te ce se intampla cand ai sirul 1,2,3, ... ,n-1,n.

[•Sapientia]

Si cum as putea optimiza algoritmul?

[•TheNechiz]

Cu putina matematica

Complexitatea e O(n*n). Gandeste-te ce se intampla cand ai sirul 1,2,3, ... ,n-1,n.

[•BLz0r]

Imi da WA pe ultimul test, cineva vreo idee va rog?   

[•otniel]

cum pot sa optimizez problema ca nici cum nu imi dau seama?
#include<iostream>
using namespace std;
#include<stdio.h>
FILE *f,*g;
long n,i,j,nr,lungime,maxim=1;
long a[100001];
int main()
{
    f=fopen("crescator.in","r");
    g=fopen("crescator.out","w");
    fscanf(f,"%ld\n",&n);
    nr=n;
    for(i=1;i<=n;i++)
        fscanf(f,"%ld",&a);
    for(i=1;i<=n;i++)
    {lungime=1;
        for(j=i+1;j<=n;j++)
            if(a[j]>a[j-1])
                {nr++;
                lungime++;}
            else
               break;
               if(j==n)
                i=n;
               if(lungime>maxim)
                maxim=lungime;
    }

   fprintf(g,"%d %d",nr,maxim);
}

[•AlexandruValeanu]

Nu prea ai ce optimiza socotind faptul ca tu ai o solutie de complexitate O(N^2), ce in aceasta problema nu poate lua 100p. Incearca sa te gandesti asa: daca ai o secventa de exemplu: 1,2,3; ai de fapt 6 secvente crescatoare: {1},{2},{3},{1,2},{2,3},{1,2,3}. Incearca sa deduci o formula de aici. Oricum daca nu reusesti ai solutiile oficiale aici: http://www.infoarena.ro/girls-programming-camp-2011/selectie/solutii; Succes!

[•otniel]

am dedus formlua pana la urma si fara solutii dar multumesc oricum