017 Combinari

[•wefgef]

Aici puteti discuta despre problema Combinari.

[•hulparuadrian]

Nu ar trebui ca backul iterativ sa fie mai eficient decat ce recursiv? Io iau 90 cu un back iterativ, si asta dupa ce am schimbat citirea si scrierea in fisiere, pt k luam doar 80 cu streamuri... Ciudata si chestia asta...
Imi poate spune si mie cineva cum as putea optimiza backul meu iterativ k sa iau 100??

[•Binary_Fire]

Am vazut ca in sursa ta tot faci verificarea asta:

Cod:

for(int j=1;j<i;j++)  
                    if (x[j+1]<=x[j]) return 0;  
return 1;  

Gandeste-te ca poti sa generezi permutarile direct, corect, fara verificare.
Exemplu daca ai deja generat : 1 3 5 atunci urmatorul element il vei alege ca fiind mai mare decat 5, nu le mai incerci si pe alea mai mici sau egale decat 5 pentru ca sigur nu vor fi bune.
Analizeaza si alte surse, ca sa vezi diferite implementari.

[•hulparuadrian]

Mersi mult pentru sfaturi...am schimbat putin cck() si acum imi merge de 100...   

[•sigrid]

Nu ar trebui ca backul iterativ sa fie mai eficient decat ce recursiv? Io iau 90 cu un back iterativ, si asta dupa ce am schimbat citirea si scrierea in fisiere, pt k luam doar 80 cu streamuri... Ciudata si chestia asta...
Imi poate spune si mie cineva cum as putea optimiza backul meu iterativ k sa iau 100??

eu luam 90 cu streamuri si back recursiv, cu citire in c iau 100

stiu ca sunt offtopic, dar de ieri la monitorul de evaluare nu mai pot sa vedea "solutiile mele" , de fiecare data trebuie sa ma uit la "toate solutiile", aveti idee de ce ?

[•MciprianM]

Eu iau 100 cu streamuri si back recursiv. Fara functie de verificare. Cel mai lung test 2->160ms
restu in jur de 0;

[•vlad_oltean]

Am vazut ca in sursa ta tot faci verificarea asta:

Cod:

for(int j=1;j<i;j++)  
                    if (x[j+1]<=x[j]) return 0;  
return 1;  

Gandeste-te ca poti sa generezi permutarile direct, corect, fara verificare.
Exemplu daca ai deja generat : 1 3 5 atunci urmatorul element il vei alege ca fiind mai mare decat 5, nu le mai incerci si pe alea mai mici sau egale decat 5 pentru ca sigur nu vor fi bune.
Analizeaza si alte surse, ca sa vezi diferite implementari.

daca stiam chestia asta inainte de oji luam 130 de puncte si poate aveam si eu sanse... oricum buna sugestie

[•Tase_C]

M-a necajit problema asta   .

Tot am incercat sa o rezolv. Apoi cand am studiat sursa lui Cezar, care afisa la fel am vazut ca are 100 puncte.

Daca am utilizat byte (din datele problemei se vede ca e destul) am luat 0 puncte. Daca am schimbat pe longint, am luat 100 puncte. E o eroare in evaluator, sau e bine de stiut pentru concursuri?

Tase

[•wefgef]

Tu compari s[k] cu s[k-1] la un moment dat. Dar vectorul s este de forma s[1..20]. De aici cred eu ca ti se trage eroare. Cand ai pus pe longint vad ca ai schimbat niste paranteze. Trimite ultima varianta pe byte in care modifici DOAR din byte in longint sa vedem cat iei. Ar trebui sa iei 0 puncte.

[•zuzulica]

Cod:

program p1;   
type t=1..18;   
var f1,f2:text;   
    n,k,i,j:t;   
    a:array[1..18] of t;   
    ok:boolean;   
    begin  
    assign(f1,'combinari.in');   
    reset(f1);   
    readln(f1,n,k);   
    close(f1);   
    for i:=1 to k do  
    a[i]:=i;   
    assign(f2,'combinari.out');   
    rewrite(f2);   
    if n=k then  
    begin  
    for i:=1 to n do  
    write(f2,a[i],' ');   
    end  
    else  
    begin  
    repeat  
    ok:=true;   
    for i:=1 to k do  
    write(f2,a[i],' ');   
    writeln(f2);   
    inc(a[k]);   
    if a[k]=n+1 then  
    for i:=k downto 2 do begin  
    if a[i]>=n-k+i+1 then  
    begin  
    inc(a[i-1]);   
    for j:=i to k do  
    a[j]:=a[j-1]+1;   
    end;   
    end;   
    if a[1]=n-k+1 then  
    ok:=false;   
    until ok=false;   
    for i:=1 to k do  
    write(f2,a[i],' ');   
    end;   
    close(f2);   
    end.  

ce parere aveti de acesta?imi cer scuze pt modul zapacit si ,,nefinisat" in care e facut dar asa e dupa o pauza mare

[•toni2007]

sincer m-i se pare ca o scandura    (de curiozitate... ai auzit de indent? ) in rest pare bine

[•zuzulica]

nuj ce am de scriu as a da altfel ma incurc, culmea:)

[•ciprianf]

La "probleme care se pot rezolva cu generare de combinari" puteti adauga problema reteta.

[•roro82ro]

  Ma intereseaza daca ma poate ajuta cineva sa imi spuneti cu ce program se poate sa vad toate combinarile dintre doua numere. de exemplu combinatii de 4 luate cate 3 ar trebui sa-mi apara: a b c
          a b d
          a c d
          b c d
  Avand in vedere ca combinari de 4 luate cate 3 sunt doar 4 variante e simplu, dar daca am numere mai mari, de ex. 12 cate 4

   Multumesc

[•Florian]

Pai vezi in arhiva educationala problema asta ( Combinari ). Vezi ca sursele trimise le poate vedea oricine. Cauta-ti un program de 100 puncte, si ala o sa-ti genereze combinari de n luate cate k. 

[•cr1st18]

Cod:

   1. #include<stdio.h>  
   2. int sol[101],n,m;  
   3. void back (int k,int m,int p)  
   4. {  
   5.     int i,j;  
   6.     if (k==m+1)  
   7.     {  
   8.         for (j=1; j<=m; ++j)  
   9.             printf ("%d ",sol[j]);  
  10.         printf ("\n");  
  11.     }  
  12.     else  
  13.         for (i=p+1; i<=n; ++i)  |imi poate spune si mie ce face secv asta?am invatat metoda backtracking .....asta genereaza
  14.         {                             |toate multimile?:-/ si m-u  reprezinta numarul de elem luate cate k?
  15.             sol[k]=i;                |
  16.             back (k+1,m,i);       |
  17.         }  
  18. }  
  19. int main()  
  20. {  
  21.     freopen("combinari.in","r",stdin);  
  22.     freopen("combinari.out","w",stdout);  
  23.     scanf("%d%d",&n,&m);  
  24.     back (1,m,0);  
  25.     return 0;  
  26. }  

Editat de admin: Foloseste tagul "code" cand postezi cod.

[•cr1st18]

m-am cam prins multumesc oricum

[•miculprogramator]

Asta nu se poate face cu next_permutatios si prev_permutation ? 

[•marcelcodrea]

Permutarile sunt diferite de combinari, deci nu prea le poti gasi cu next_permutation si prev_permutation. Dar intrebarea asta putea sa fie pusa si in topicul de permutari. Eu cred ca e util pentru elevi sa inteleaga ideea din spatele algoritmului, nu doar sa il apeleze.
 
Ca offtopic : STL va putea fi de acum folosit si la judeteana, eu l-as interzice la concursurile de liceu, indiferent de faza, pentru ca in opinia mea ideea nu e sa inveti cum sa folosesti o librarie de functii optim-implementate(asta se poate invata si la facultate), ci sa implementezi de mana algoritmii. 
Am fost si sunt un sustinator al introducerii gcc la toate fazele olimpiadelor, insa nu cred ca ar fi dificil sa se interzica apelarea STL-ului in surse si astfel sa se testeze capacitatea olimpicului de a proiecta structuri si a implementa de mana algoritmii care lucreaza cu ele.

L.E.(Ca sa nu perpetuez un offtopic): Cred ca ai dreptate, wefgef, insa doar daca ne gandim la faza nationala si mai sus de atat. La faza locala sau judeteana nu putem vorbi de o majoritate de olimpici "cu pretentii", asa cum ai formulat si cred ca STL-ul va dauna. 

[•wefgef]

Orice olimpic cu pretentii stie sa implementeze tot ceea ce foloseste din STL (cu mici exceptii, gen seturi). Olimpiada este un concurs in care accentul ar trebui sa se puna pe gasirea ideilor din spatele problemelor, nu pe implementarea unor algoritmi arhicunoscuti.

Intr-adevar, pentru elevii mai slabi care nu stiu sa scrie o cautare binara poate ca reprezinta un mare avantaj STL-ul, dar pentru olimpicii de top e vorba doar de a castiga timp la implementare - ceea ce mi se pare foarte in regula. E stupid ca intr-o proba de concurs de 5 ore sa stai sa scrii sortarea de mana de 3 ori.

Sa implementezi niste algoritmi vechi de zeci de ani pe care toata lumea ii cunoaste nu ar trebui sa reprezinte scopul vreunui concurs, ca sa nu mai vorbim de olimpiada

[•alexandru92]

Desi intrebarea o sa sune ciudat, de ce merge sursa http://infoarena.ro/job_detail/369554?action=view-source  si asta nu http://infoarena.ro/job_detail/369556?action=view-source .
Ambele il au pe k neinitializat.

[•andunhill]

Am si eu o intrebare daca se poate. Pe exemplul dat mie imi scrie in fisier urmatoarele: 1 2 3

Cod:

1 2 4 
1 3 2 
1 3 4 
1 4 2 
1 4 3 
2 1 3 
2 1 4 
2 3 1 
2 3 4 
2 4 1 
2 4 3 
3 1 2 
3 1 4 
3 2 1 
3 2 4 
3 4 1 
3 4 2 
4 1 2 
4 1 3 
4 2 1 
4 2 3 
4 3 1 
4 3 2 

Total diferit de raspunsul din exemplu. Si totusi am luat 100 pt. Imi poate explica si mie cineva?

[•dornescuvlad]

Tu ai generat de fapt aranjamente in ordine lexicografica, nu combinari.
Tocmai am rulat sursa ta de 100 puncte si afiseaza ce trebuie 

[•andunhill]

Bun dar tot nu inteleg de ce nu imi afiseaza ca in enunt.

[•SpiderMan]

Eu am rulat sursa ta, si arata cum trebuie, probabil ai modificat ceva si ai uitat sa compilezi sau ... nu stiu