infoarena

Aici puteţi discuta despre problema Crescator (http://infoarena.ro/problema/crescator).

o mica greseala :

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

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

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

Nu sunt sigur dacă am înÈ›eles problema.  :?
Pentru:
In:
Out:

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:
out:

in:
out:
:?
?

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

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

Nu era asta :sad: . Sigur greÈ™eala e la algoritm,dar nu găsesc niciun test pentru care să nu meargă.Mă puteÈ›i ajuta?  :oops:

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

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


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

:eyebrow:
Dar tot iau 0 puncte.Mai poÈ›i să-mi dai un test?  :-s

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.

Nu pot să cred că am greșit asta. ](*,)
Mulțumesc pentru ajutor. :thumbup:

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. :ok:

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?

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

Si cum as putea optimiza algoritmul?

Cu putina matematica :-'

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

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);
}

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!

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