007 Datorii

[•toni2007]

Se poate si in pascal:
http://infoarena.ro/monitor?task=datorii&compiler=fpc&score_begin=100&display_entries=25&first_entry=0

[•PetcuIoan]

Aceasta sursa este copiata dupa:http://infoarena.ro/job_detail/266861?action=view-source
am observat ca a mai trimis cateva surse pe 4 martie 2009 direct de 100 ar merita verificate si ele

[•alex_bucevschi]

Salut!! Imi puteti spune unde depasesc timpul pe aceasta sursa #include <fstream>
 
using namespace std;
 
int main()
{
    ifstream fin("datorii.in");
    ofstream fout("datorii.out");
    unsigned N,M,A[15010],i,T,V,C,P,Q,s,j;
    fin>>N>>M;
    for(i=1;i<=N;i++)
        fin>>A;
    for(i=1;i<=M;i++)
    {
        fin>>C;
        if(C)
        {
            s=0;
            fin>>P>>Q;
            for(j=P;j<=Q;j++)
                s+=A[j];
            fout<<s<<"\n";
        }
        else
        {
            fin>>T>>V;
            A[T]-=V;
        }
    }
    return 0;
}  

[•SebiSebi]

Complexitatea programului tau este O(N*M), ceea ce nu este optim. Pentru 100 de puncte trebuie sa scoti O(M*log₂ N).
Incearca sa inveti arbori de intervale sau arbori indexati binar. Succes!

[•ionut98]

datimi o idee cum sa fac ca programu sa nu mai iasa dinj limita de timp cod sursa:job #1073106

[•PlayLikeNeverB4]

Citeste threadul in care tocmai ai postat.

[•VVasy1997]

Stie cineva de ce imi da tot peste timp!!!
Pe compul meu imi da 0.050 s dar dupa ce trimit programul scrie ca timpul e depasit    
#include<fstream>
using namespace std;
int main()
{
unsigned int m,n,a[15001],i,j,p,q,t,v,k,s;
ifstream f("datorii.in");
ofstream g("datorii.out");
f>>n>>m;
for(i=1;i<=n;i++)
{
     f>>a;
}
for(i=1;i<=m;i++)
{f>>k;
switch(k)
{case 0:
{
f>>t>>v;
a[t]=a[t]-v;
}
break;
case 1:
{
f>>p>>q;
s=0;
for(j=p;j<=q;j++)
{
s=s+a[j];
}
g<<s<<"\n";
}
break;}
}
f.close();
g.close();
}

[•SebiSebi]

IÈ›i iese din timp pentru ca testele folosite la evaluarea sursei tale au dimensiuni mult mai mari decât cel din exemplu. Programul tau nu este optim. Trebuie sa scoti O(M log N). ÃŽnvață arbori de intervale sau arbori indexaÈ›i binari. 

[•alexandru.ghergut]

Problema se poate face cu arbori de intervale? Am tot încercat să văd de ce o persoană ia TLE cu structura asta de date, dar acum văd că și sursa pe care am luat eu 100 ia TLE pe toate testele. Dacă n-am greșit la implementare, complexitatea e de O(NlogN + MlogN). Ar trebui să ruleze în ~0.0015 secunde, iar limita e 0.15.

[•klamathix]

Salut

Din câte îmi dau eu seama tu apelezi pentru ambii subarbori atât query-ul cât și update-ul de fiecare dată, ceea ce înseamnă că parcurgi tot arborele.

[•alexandru.ghergut]

Salut.
La query verific de fiecare dată când intru în funcție dacă intervalul curent (cLeft, cRight - capete) se cuprinde în totalitate în intervalul dorit (left, right - capete) și returnez suma de pe interval în caz afirmativ. Apoi verific dacă nu se cuprinde deloc și returnez 0 în caz afirmativ. Apoi dacă se cuprinde parțial, îl sparg în 2 intervale și e adevărat că lansez unele apeluri degeaba, dar dacă vede că nu are loc o intersecție între intervale, îmi returnează 0 și nu continuă mai departe.
La update dacă poziția e cuprinsă în intervalul curent, iar intervalul nu e de forma left == right, îl sparg în 2 intervale. Dacă intervalul e de forma left == right, mai fac o verificare să văd dacă sunt pe poziția bună, adun valoarea și mă opresc. Apoi de la frunză, mă duc înapoi și adaug val la toate intervalele prin care am trecut ca să ajung la frunză.

Am mai trimis o modificare acum, unde vizitez doar subarborele care îmi trebuie și am folosit operații pe biți la înmulțirile/împărțirile cu 2. Însă... tot TLE și e ciudat că am luat 100 pe sursa anterioară luna trecută. Dacă parcurgeam tot arborele, aveam O(N^2 + M*N) și asta sigur nu intra în timp.

MulÈ›umesc pentru răspuns 

[•Gabryel9898]

De ce imi da 0 la toate? am inteles eu problema gresit?
# include <fstream>
using namespace std;
int main()
{
    int M,N,s,i,P,Q,A[1000];
    ifstream f1("datorii.in");
    ofstream f2("datorii.out");
    f1>>N>>M;
    for(i=1;i<=N;i++)
    f1>>A;
    for (i=1;i<=M;i++)
        {
            f1>>Q;
            if(Q==0)
                {
                    f1>>Q>>P;
                    A[Q]-=P;
                }
            else
            { s=0;
                f1>>Q>>P;
                    while(Q<=P)
                        {
                            s+=A[Q]; Q++;
                        };
                f2<<s<<'\n';
            }
        }
f1.close();
f2.close();
return 0;}

[•AlexandruValeanu]

Ai declarat vectorul prea mic.

Cod:

N <= 15,000

[•alexandru.ghergut]

Până la urmă am luat 100 cu arbori de intervale + parsare 

[•tudorgalatan]

De ce am TLE pe toate testele?

Cod:

    for (i=1; i<=N; i++)
    {
        fin >> A[i];
        sum2(i,A[i]);
    }
    for (i=1; i<=M; i++)
    {
        fin >> type;
        if (type == 0)
        {
            fin >> T >> V;
            /// BUG
            A[T] -= V;
            for (j=1; j<=N; j++)
                tree[j] = 0;
            for (j=1; j<=N; j++)
                sum2(j,A[j]);
        }
        else
        {
            fin >> P >> Q;
            sum = sum1(Q) - sum1(P-1);
            fout << sum << '\n';
        }
    }

Cod:

int sum1 (int position)
{
    int sum=0;
    while (position > 0)
    {
        sum += tree[position];
        position -= (position^(position-1)) & position;
    }
    return sum;
}

void sum2 (int position, int value)
{
    while (position <= N)
    {
        tree[position] += value;
        position += (position^(position-1)) & position;
    }
}

[•AlexandruValeanu]

Ai O(N) pe operatia de update.

[•tudorgalatan]

Până la urmă mi-am dat și eu seama de asta. Dar cum pot reduce timpul de execuție și optimiza procesul de update?

[•AlexandruValeanu]

Nu cred ca ai inteles cum functioneaza un aib. Update-ul il faci doar pe un singur element deci nu ai nevoie sa modifici tot vectorul (doar log(n) elemente).

Sursa ta putin modificata : http://www.infoarena.ro/job_detail/1707845

[•tudorgalatan]

Mulțumesc frumos! Acum iau 100 de puncte. Dar nu am înțeles prea bine de ce se pune "-V" la update.

[•AlexandruValeanu]

A (achitare - se scade o valoare din suma restanta a unei zile anume)

[•GeoeyMexicanu]

M-ar putea ajuta cineva ? Am rezolvat problema , si cand rulez problema folosind datele de pe site , rezultatele sunt corecte , algoritmul nu depaseste timpul de executie . Oricum , pe site , toate raspunsurile apar a fi incorecte . Dar testul din exemplu pe care-l fac si in CodeBlocks , da rezultate corecte si lucreaza in timp . Imi pare rau daca intrebarea mea pare stupida , sunt nou in comunitate . Codul meu e acesta:
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("datorii.in");
ofstream g("datorii.out");
unsigned int i,j,nr=0,x,y,z;
unsigned int n,m,v[1010];
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        f>>v;
    }
    while(m!=0)
    {
        nr=0;
        f>>x>>y>>z;
        if(x==0)
        {
            v[y]=v[y]-z;
        }
        else
        {
            for(i=y;i<=z;i++)
                nr=nr+v;
                if((m-1)!=0)
                    g<<nr<<endl;
                else
                    g<<nr;
        }
        m=m-1;
    }
    return 0;
}

[•flaviu_2001]

Are o problema evaluatorul? Am facut o sursa cu arbori de intervale si imi da 0p tle, am facut parsare tot 0p tle, apoi am luat si o sursa cu arbori indexati binar(cred) de ~20ms din cele de 100 si tot 0p da cu tleuri.

Edit: nevermind, trimisem eu sursele gresite

[•JohnnyT]

Pentru ca am mai vazut un mesaj de genul, las si eu, drept confirmare. Si in cazul meu, facand citirea cu fstream a rezultat in TLE la toate testele. Trecand pe cstdio, problema s-a rezolvat si am luat 100 de puncte.