usaco training ..sectiunea 1.4 .. checker challenge

[•teplesnescdenutevezi]

imi explica si mie cineva cum pot sa fac sa-mi intre ultimul test (n=13)  in limita de o secunda ? .... mie imi da 1.21 s  ...

[VladS]

Probabil ca atunci s-a oprit executia. La tine pentru n=13 in cat timp iti ruleaza?
Btw, ai implementat cu simetrizare?

[•teplesnescdenutevezi]

da....am folosit simetrizare .... pe calc meu ...la n=13 ...imi da timpul 0.44 s ... iar pe usaco imi da mai mult de o sec ....

[VladS]

Daca ai folosit toate hinturile inseamna ca implementarea ta nu este cea mai buna. Poti sa pui unele functii inline, variabile constante (daca nu faci asta deja). Daca nici asa nu merge incearca sa faci iterativ. Asta ar trebui sa fie suficient. Mai sunt unele optimizari super da te las sa le afli din Analysis.

[•teplesnescdenutevezi]

e de-a dreptul enervant... chiar nu-mi dau seama ce as putea sa ii fac ca sa mearga ...

[•teplesnescdenutevezi]

eu tot nu am reusit sa o bag sub o secunda ... am facut-o si iterativ si tot imi da un timp de 1.3 secunde .... sugestii cineva ?

Cod:

void back()
 {
  FILE *g=fopen("checker.out","w"),
       *f=fopen("checker.in","r");
  unsigned long m=0;
  int k=1,as,gasite=0,aux,n,limita;
  fscanf(f,"%d",&n);
  fclose(f);
  if(n>6)  aux=(n+1)/2;
  else aux=n;
  
  st[k]=val1;
  while(k>val1)
   {
    limita=n;
    if(k==1 || (k==2 && st[1]==7)) limita=aux; 
    do{
       if(st[k]<limita) {st[k]++;as=1;}
       else as=val1; 

       }while((as) && (diag[st[k]-k+n]!=val1 || diag2[k+st[k]]!=val1 || coloana[st[k]]!=val1));
    if(as) {
           diag[st[k]-k+n]=diag2[st[k]+k]=coloana[st[k]]=1;  
           if(k==n) {
                     //   noteaza();
                     if((st[1]!=aux && n>6) || (st[1]==aux && n%2==val1 && n>6) || (n==13)) m+=2;
                     else m++;
                     if(gasite<3)
                     { for(int j=1;j<=n;j++) {fprintf(g,"%d",st[j]);if(j!=n) fprintf(g," ");}
                       fprintf(g,"\n");gasite++; 
                     }  
                     coloana[st[k]]=diag[st[k]-k+n]=diag2[st[k]+k]=val1;
                       } 
                      else {k++;st[k]=val1;}
                   }
    else {k--;coloana[st[k]]=diag[st[k]-k+n]=diag2[st[k]+k]=val1;}
    }
    fprintf(g,"%ld\n",m);
    fclose(g); 
 
   }

Editat de moderator: Invatati sa puneti "[code]" inaintea unui fragment de cod

[•Cosmin]

Cu indentarea asta nu prea cred ca o sa aiba cineva chef sa iti citeasca sursa.

[•Cosmin]

O chestie simpla ce ai putea sa o faci ar fi sa ai x = st[k] ca sa nu tot faci calculul adresei lui st[k] de atatea ori, probabil asta o sa te ajute putin, cat despre chestia cu implementarea iterativa sau recursiva nush daca te ajuta implementarea iterativa cu ceva, fa niste comparatii intre implementari pe calculatorul tau nu schimba o chestie doar pentru ca ai auzit ca merge mai bine altfel, convinge-te singur ce merge si ce nu. Alta chestie ar fi expresia

Cod:

diag[st[k]-k+n]!=val1 || diag2[k+st[k]]!=val1 || coloana[st[k]]!=val1

in care obligi programul sa evalueze toate trei expresiile iar schimband in

Cod:

!(diag[st[k]-k+n]==val1 && diag2[k+st[k]]==val1 && coloana[st[k]]==val1)

programul se opreste la prima expresie evaluata la false. Pentru rapiditate poti face acelasi algoritm de doua ori: o data cu scrierea primelor trei solutii si o data cu numararea solutiilor, ca sa nu faci if (gasite < 3) de atatea ori. Nu m-am uitat pe codu tau ca sa il inteleg ... astea sunt sugestii asa dintr-o privire fugara. (super tare handle .... )