Poate sa imi spuna cineva ce face urmatoarea secventa de cod si mai ales partea cu "#define new DEBUG_NEW". Imi aloca o constanta dinamica care va fi preprocesata ?

#ifdef _DEBUG
#define new DEBUG_NEW
#endif

Da ma gandeam ca trebuie sa parsez si am luat 100. Mersi mult pentru cele 2 sfaturi cruciale. Mai ales ala cu Graf.clear am sa-l retin toata viata 

Wow am luat 90. Inca iau TLE pe 2 teste.

Intr-adevar uitasem sa setez la 0 toti vectorii. Insa am facut aceasta modificare si iau 10 pcte. Iau si WA si TLE  pe unele teste.
Uite acum arata acum programul:

Cod:

#include <cstdio>
#include <vector>
#include <cstring>
#define NMAX 10010
using namespace std;

vector < int > Graf[NMAX];
int vizitat[NMAX];
int dr[NMAX];
int g[NMAX];
int st[NMAX];
int n,m,e,nr;
int T;
bool ok;

bool Hopcroft_Karp(int nod){

   if(vizitat[nod]) return 0;
   vizitat[nod] = 1;
    for(vector < int >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if(!dr[*it]){
            dr[*it] = nod;
            st[nod] = *it;
            return 1;
        }
    for(vector < int >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if( Hopcroft_Karp(dr[*it])){
            dr[*it] = nod;
            st[nod] = *it;
            return 1;
        }

return 0;
}

int main(){

freopen("java.in","r",stdin);
freopen("java.out","w",stdout);
int x,y;

    scanf("%d",&T);
    while(T){
          nr=0;
        scanf("%d%d%d",&m,&n,&e);
    while(e){

        scanf("%d%d",&x,&y);
        Graf[x].push_back(y);
        g[x] = 1;

    --e;
    }

    ok=1;
    nr=0;
    while(ok){

        ok = 0;
        for(register int i=1;i<=m;++i)
        if(!st[i])
        if(Hopcroft_Karp(i)) ok=1;
        memset(vizitat,0,sizeof(vizitat));
    }
        for(register int i=1;i<=n;++i)
            if(dr[i]) ++nr;
            printf("%d\n",nr);

     for(register int i=1;i<=m;++i)
        if(g[i])
        Graf[i].assign(Graf[i].size()+1,0);
        memset(g,0,sizeof(g));
        memset(dr,0,sizeof(dr));
        memset(st,0,sizeof(st));
        memset(vizitat,0,sizeof(vizitat));
    --T;

    }
return 0;
}

Editat de moderator: Foloseste tag-ul [ code ] [/ code ] cand postezi cod!

Algoritmul meu este de a obtine un cuplaj maxim intre cercetatori(multime 1-m) si gandaci. Iau WA pe toate testele. In exemplu imi da bine. Am optimizat sa nu iau TLE sau MME. Imi bat capul de ore intregi si nu vad greseala. Ce am putut gresi aici ?
<code>
 #include <cstdio>
#include <vector>
#include <cstring>
#define NMAX 10010
using namespace std;

vector < int > Graf[NMAX];
int vizitat[NMAX];
int dr[NMAX];
int g[NMAX];
int st[NMAX];
int n,m,e,nr;
int T;
bool ok;

bool Hopcroft_Karp(int nod){

   if(vizitat[nod]) return 0;
   vizitat[nod] = 1;
    for(vector < int >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if(!dr[*it]){
            dr[*it] = nod;
            st[nod] = *it;
            return 1;
        }
    for(vector < int >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if( Hopcroft_Karp(dr[*it])){
            dr[*it] = nod;
            st[nod] = *it;
            return 1;
        }

return 0;
}

int main(){

freopen("java.in","r",stdin);
freopen("java.out","w",stdout);
int x,y;

    scanf("%d",&T);
    while(T){
          nr=0;
        scanf("%d%d%d",&m,&n,&e);
    while(e){

        scanf("%d%d",&x,&y);
        Graf

• .push_back(y);

       g

• = 1;

    --e;
    }

    ok=1;
    nr=0;
    while(ok){

        ok = 0;
        for(register int i=1;i<=m;++i)
        if(!st)
        if(Hopcroft_Karp(i)) ok=1;
        memset(vizitat,0,sizeof(vizitat));
    }
        for(register int i=1;i<=n;++i)
            if(dr) ++nr;
            printf("%d\n",nr);

     for(register int i=1;i<=m;++i)
        if(g)
        Graf.assign(Graf.size()+1,0);
        memset(g,0,sizeof(g));
    --T;

    }
return 0;
}
</code>

Si eu am aceeasi problema ca a lui George, algoritmul este le fel gandit, si iau 10 pcte si chiar nu stiu ce sa mai fac .
Idei ?

Mersi mult, acum stiu ce am de facut.

Imi spune si mie cineva ce face operatorul <<= , respectiv >>= ?

Imi poate spune cineva ce reprezinta vecotul A in care se retin elemente din vector ?

Am o matrice de n*m si trebuie sa gasesc toate submatricile a caror suma este divizibila cu 3. Eu fac in O(n^3), fixandu-mi 2 linii si calculand toate submatricile dintre acele linii si verificand daca suma respectiva e divizibila cu 3.
Imi da raspuns aproximativ, insa stiu ca imi scapa ceva marunt  
Cod:
for(register int i=1;i<=n;++i)
        for(register int j=i;j<=n;++j){

         S = 0;
            for(register int C=1;C<=m;++C){
                for(register int ii=i;ii<=j;++ii)
                    B[C]+=M[ii][C];

              S+=B[C];
                    if(S%3 == 0)
                        nr++;
}

        memset(B,0,sizeof(B));
        }

Gasesti tot ce ai nevoie pe Infoarena la sectiunea Downloads. Ai subiecte cu indicatii de rezolvare + surse oficiale.

Eu incerc sa fac O(n*m), adica sa verific pentru fiecare oita daca intra intr-o ograda. Imi da raspuns corect doar in unele cazuri si chiar nu inteleg ce imi scapa la implementare : Oita[j] coord unei oi si Ograd coord din stanga jos a ograzii.

Nmax = M;
    for(register int i=1;i<=N;++i)
        for(register int j=1;j<=M;++j)
            if(Oita[j].x <= Ograd.x +H && Oita[j].x >= Ograd.x && Oita[j].y <= Ograd.y +L && Oita[j].y >= Ograd.y)
                Nmax--;

    printf("%d",Nmax);

Am facut O(n^3) cu hashuri si iau 65 de pct cu TLE si am incercat sa fac putin altfel si acum iau 25 de pct cu MME. Cum e posibil sa iau MME cand memoria folosita este aceeasi ? Chiar nu inteleg ce naiba se intampla 
Iata codul initial:

inline void solve(){
 
int S=0;
    for(register int i=1;i<=N-2;++i){
        for(register int j=i+1;j<=N-1;++j){
            for(register int k=j+1;k<=N;++k){
                    S = V+V[j]+V[k];
 
            if(C-S>0)
                Search(C-S);
            }
 
        }
 for(register int z=1;z<i;++z)
            Add(V+V[z]);
}
 
printf("%d",nr);
}

Si iata codul cu care iau MME:

inline void solve(){

int S=0;
    for(register int i=1;i<N;++i){
        for(register int j=i+1;j<=N;++j){

                    S = V+V[j];
                if(C-S>0)
                Search(C-S);
}

 for(register int z=1;z<i;++z)
    for(register int j=z+1;j<i;++j)
            Add(V+V[z]+V[j]);
}

printf("%d",nr);
}

Am facut KMP si am luat 100, insa vreau sa fac si Rabin Karp. Am inteles foarte bine cum se face teoretic insa ceva nu imi iese la implementare. Aveti vreo idee ?

Cod:

#include <cstdio>
#include <cstring>
#define NMAX 2000001
#define min(a,b) a<b ? a:b
using namespace std;

char A[NMAX],B[NMAX];
int n,m,nr,a,b;
int Sol[NMAX];
int t[NMAX];

inline unsigned long putere(int x,int k,int MOD){

    if (k == 0)
        return 1;
   else if(k%2 == 0){
       a = putere(x,k/2,MOD);
        return a*a%MOD;
   }
   else{
        a = putere(x,k/2,MOD);
        b = a*a%MOD;
        return b*x % MOD;
   }
}

inline int match(char *T, char *P,int j){

    for(register int i=0;i<m;++i)
        if(T[i+j] != P[i])
            return 0;
return 1;
}

inline void Rabin_Karp(char *T,char *M,int d,int MOD){

    unsigned long h,P=0;
    n = strlen(T);
    m = strlen(M);

        t[0] =0;
        h = putere(d,m-1,MOD);
    for(register int i=0;i<m;++i){
        P = (d*P + M[i])% MOD;
        t[0] = (d*t[0] + T[i])%MOD;
}

    printf("%d\n",P);
    for(register int i=0;i<=n-m;++i){

        printf("%d\n",t[i]);
        if(P == t[i]){
            if(match(T,M,i))
                    Sol[++nr] = i;
                    printf("%d\n",i);
                  }

         t[i+1] = (d*(t[i] - T[i+1]*h) + T[i+m+1])%MOD;
        }
}

int main(){


freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);

fgets(B,sizeof(B),stdin);
fgets(A,sizeof(A),stdin);

    Rabin_Karp(A,B,256,100003);
    printf("%d\n",nr);
    for(register int i=1;i<=min(nr,1000);++i)
        printf("%d ",Sol[i]);

return 0;
}

Editat de admin: Foloseste tagul "code" atunci cand postezi surse.

Da .. mi-am dat seama ce nu facusem bine. Acum am luat 100. Mersi mult   

Ok, am modificat in sensul ca de fiecare cand gasesc un rezultat al sume i^3 + j^3 + K^3 scot din hash valoarea respectiva si tot nu imi da bine. De ex pe codul meu imi da 109 de 654. Sorry dar tot nu reusesc sa imi dau seama ce nu e bine  .
Iata ce am modificat fata de data trecuta: Am facut o functie remove

void remove(int X){

    int key = abs(X%NMAX);
     for(vector < int >::iterator it = Hash[key].begin();it!=Hash[key].end();++it)
        if(*it == X){
            Hash[key].erase(it);
            return ;
        }
}

si cand numar solutiile fac asta :

 for(int k=-50;k<=50;++k)
        for(int i=-50;i<=50;++i)
            for(int j=-50;j<=50;++j)
                    if(search(V[3]*k*k*k + V[4]*i*i*i + V[5]*j*j*j)){
                            Nmax++;
                        remove(V[3]*k*k*k + V[4]*i*i*i + V[5]*j*j*j);
                    }

Am incercat si eu sa fac problema si nu inteleg unde gresesc. Am wa dar totusi soloutie mea este aproape de alte exemple, insa nu stiu
ce nu fac bine. Salvez toate solutiile posibile a primelor 2 necusoncute apoi caut toate solutiile posibile pentru urmatoarele 3 necunoscute astfel incat suma lor sa fie egala cu opusul sumei primelor 2. Iata si codul meu :

#include <cstdio>
#include <vector>
#include <stdlib.h>
#define NMAX 660000
using namespace std;

int V[5];
vector < int > Hash[NMAX];
int Nmax;

 void citesc(){

    freopen("eqs.in","r",stdin);
    freopen("eqs.out","w",stdout);
    for(register int i=1;i<=5;++i)
    scanf("%d",&V);
}


 int search(int X){
    int key = abs(X%NMAX);
    for(vector < int >::iterator it = Hash[key].begin();it!=Hash[key].end();++it)
        if(*it == X)
            return 1;
return 0;
}

 void add(int X){
    int key = abs(X%NMAX);
    Hash[key].push_back(X);
}


void solve(){

    for(int i=-50;i<=50;++i)
        for(int j=-50;j<=50;++j)
                add(-V[1]*i*i*i - V[2]*j*j*j);

    for(int k=-50;k<=50;++k)
        for(int i=-50;i<=50;++i)
            for(int j=-50;j<=50;++j)
                    if(search(V[3]*k*k*k + V[4]*i*i*i + V[5]*j*j*j))
                            Nmax++;


}

int main(){

    citesc();
    solve();
    printf("%d",Nmax);

return 0;
}

Bine ca mi-ati spus ca e O(n^2). Acum stiu ca trebuie sa invat KMP.

Eu iau 60 de puncte pe problema cu TLE la 2 teste si fac direct cu strstr care este KMP deja optimizat din cate stiu eu. Care ar putea fi problema ? E mai rapid cu hashing ?

Imi poate da cineva si mie un exemplu mai mare sa vad ce nu imi merge ? Mie imi da costul prea mare.

Ok am inteles, thanks man

Vreau sa gasesc cea mai mare valoare intre 2 numere cunoscute de tip float. Acea valoare o voi scadea pe toate muchiile unui graf, astfel incat sa nu obtin ciclu negativ daca aplic algoritmul Bellman Ford.
Eu am incercat ceva si nu inteleg ce nu merge. Mie mijloc imi returneaza la final ca fiind 1.5 si eu trebuie sa obtin 1.75.Ma intereseaza cel mai mult de ce nu merge cand caut binar in main, in rest cred ca am facut bine. Iata sursa mea:

#include <cstdio>
#include <vector>
#include <list>
#include <utility>
#include <queue>
#include <cstring>
#include <iomanip>
#define inf 1000000
#define NMAX 1001
using namespace std;

typedef pair<int,float> pereche;
vector < list < pereche > > Graf;
queue < int > q;
int inQueue[NMAX],vizitat[NMAX];
vector < int > aparitii;
vector < float > d;
int n,m,scaderi;
float minim = inf;

void citesc(){

    int x,y;
    float c;
    freopen("ciclu.in","r",stdin);
    freopen("ciclu.out","w",stdout);
    scanf("%d%d",&n,&m);
    Graf.resize(n+1);
    d.resize(n+1);
    aparitii.resize(n+1);
    for(register int i=1;i<=m;++i){
        scanf("%d%d%f",&x,&y,&c);
        Graf
.push_back(pereche(y,c));
        Graf[y].push_back(pereche(x,c));
        if(c < minim)
            minim = c;
    }
}

void DFS(int nod){

    vizitat[nod] = 1;
    for(list < pereche >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if(!vizitat[it->first]){
            it->second -= minim;
            DFS(it->first);
    }}

int Bellman_Ford(int nod){

    int top;
    q.push(nod);
    inQueue[nod] = 1;
    ++aparitii[nod];
    d[nod] = 0;
        while(!q.empty()){
            top = q.front();
            q.pop();
            inQueue[top] = 0;
                for(list <pereche>::iterator it = Graf[top].begin();it!=Graf[top].end();++it)
                    if(d[it->first] > d[top] + it->second){
                        d[it->first] = d[top] + it->second;
                        if(!inQueue[it->first]){
                            inQueue[it->first] = 1;
                            q.push(it->first);
                        }
                    ++aparitii[it->first];
                    if(aparitii[it->first] >= n)
                    return 0;
            }
        }
return 1;
}

int main(){

    citesc();
    DFS(1);
        scaderi++;
 d.assign(n+1,inf);
 while(Bellman_Ford(1)){
            d.assign(n+1,inf);
            memset(vizitat,0,sizeof(vizitat));
            aparitii.assign(n+1,0);
            DFS(1);
        scaderi++;
        }

   float inceput = (scaderi-1)*minim;
   float sfarsit = scaderi*minim;
   float mijloc = 0;

        while(inceput <= sfarsit){

            memset(vizitat,0,sizeof(vizitat));
            aparitii.assign(n+1,0);
            d.assign(n+1,inf);

            mijloc = (inceput+sfarsit)/2;
            minim = mijloc;
            DFS(1);
            if(!Bellman_Ford(1))
            sfarsit = mijloc-1;
            else
            inceput = mijloc+1;

        }

printf("%d\n",scaderi);
printf("%f",mijloc);
return 0;
}

Eu am o nelamurire. La un momentdat in exemplu, arborele de cost minim era 6, apoi cand s-a mai adaugat un nod costul in loc sa creasca a scazut la 5.656854. Daca adaug un nod nou nu trebuie sa gasesc distanta minima la unul din nodurile arborelui deja construit si sa o adaug la suma de cost minim a arborelui?

Vreau sa gasesc cea mai mare valoare intre 2 numere cunoscute de tip float. Acea valoare o voi scadea pe toate muchiile unui graf, astfel incat sa nu obtin ciclu negativ daca aplic algoritmul Bellman Ford.
Eu am incercat ceva si nu inteleg ce nu merge. Mie mijloc imi returneaza la final ca fiind 1.5 si eu trebuie sa obtin 1.75.Ma intereseaza cel mai mult de ce nu merge cand caut binar in main, in rest cred ca am facut bine. Iata sursa mea:

#include <cstdio>
#include <vector>
#include <list>
#include <utility>
#include <queue>
#include <cstring>
#include <iomanip>
#define inf 1000000
#define NMAX 1001
using namespace std;

typedef pair<int,float> pereche;
vector < list < pereche > > Graf;
queue < int > q;
int inQueue[NMAX],vizitat[NMAX];
vector < int > aparitii;
vector < float > d;
int n,m,scaderi;
float minim = inf;

void citesc(){

    int x,y;
    float c;
    freopen("ciclu.in","r",stdin);
    freopen("ciclu.out","w",stdout);
    scanf("%d%d",&n,&m);
    Graf.resize(n+1);
    d.resize(n+1);
    aparitii.resize(n+1);
    for(register int i=1;i<=m;++i){
        scanf("%d%d%f",&x,&y,&c);
        Graf

• .push_back(pereche(y,c));

        Graf[y].push_back(pereche(x,c));
        if(c < minim)
            minim = c;
    }
}

void DFS(int nod){

    vizitat[nod] = 1;
    for(list < pereche >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if(!vizitat[it->first]){
            it->second -= minim;
            DFS(it->first);
    }}

int Bellman_Ford(int nod){

    int top;
    q.push(nod);
    inQueue[nod] = 1;
    ++aparitii[nod];
    d[nod] = 0;
        while(!q.empty()){
            top = q.front();
            q.pop();
            inQueue[top] = 0;
                for(list <pereche>::iterator it = Graf[top].begin();it!=Graf[top].end();++it)
                    if(d[it->first] > d[top] + it->second){
                        d[it->first] = d[top] + it->second;
                        if(!inQueue[it->first]){
                            inQueue[it->first] = 1;
                            q.push(it->first);
                        }
                    ++aparitii[it->first];
                    if(aparitii[it->first] >= n)
                    return 0;
            }
        }
return 1;
}

int main(){

    citesc();
    DFS(1);
        scaderi++;
 d.assign(n+1,inf);
 while(Bellman_Ford(1)){
            d.assign(n+1,inf);
            memset(vizitat,0,sizeof(vizitat));
            aparitii.assign(n+1,0);
            DFS(1);
        scaderi++;
        }

   float inceput = (scaderi-1)*minim;
   float sfarsit = scaderi*minim;
   float mijloc = 0;

        while(inceput <= sfarsit){

            memset(vizitat,0,sizeof(vizitat));
            aparitii.assign(n+1,0);
            d.assign(n+1,inf);

            mijloc = (inceput+sfarsit)/2;
            minim = mijloc;
            DFS(1);
            if(!Bellman_Ford(1))
            sfarsit = mijloc-1;
            else
            inceput = mijloc+1;

        }

printf("%d\n",scaderi);
printf("%f",mijloc);
return 0;
}

Eu iau 10 puncte cu wrong answer si nu stiu de ce. Imi puteti da va rog niste teste si rezultatul lor ca sa ma conving unde este greseala ?