Folositi qsort (randomizat daca il faceti de mana) cu incredere. Sansele sa va mearga mai prost decat heapsort sunt mai mici decat sa castigati la loto.

eu stiam ca qsortul din stdlib este implementarea exacta a quicksortului, dar abia acum am vazut ca e cam depasit, adica de multe ori merge mai incet decat heap-u (am refacut intr-o seara "reactivi" si "submat" doar schimband sortarea si mergea ceva mai repede si concuma ceva mai putina  memorie (80% din  cat concuma qsortul) si la pb "orase" heap-ul avea pe cel mai mare test 80 de ms pe cand qsortu si iesea cu 204 ms pe un test

voi ce sortari folositi?


si eventual argumentati

eu pana la un moment dat foloseam qsortul din stdlib.h pentru ca era usor de implementat, dar de curand am trecut la heapsort pentru ca are intotdeauna N lg N (lucrez in c deci nu folosesc algorithm si sort care e pt c++)

pai, intri pe pagina concursului , la grupa de varsta corespunzatoare o sa-ti apara 2 sau 3 pb (nuj cate sunt) si faci click pe ele si iti apar enunturile la fel ca la arhiva

solutiile se trimit la fel ca in arhiva

si daca e fara rating nu trebuie sa ne inscriem nu? ca nici nu am gasit pagina de inscriere

din cate  stiu eu feof (stdin) iti baga ultimu  caracter de doua ori... incearca asa:

pentru citire de numere:

Cod:

while  (scanf("%d",&x)!=EOF){
     /*instructiune
        instructiune
     */
}

pentru citire de caractere

Cod:

while (scanf("%c",&x)!=EOF){
      /*
       instructiune
      */
}

pentru citire de siruri de caractere

Cod:

while (gets(s)){
    /*
      Instructiune
    */
}

spor

Da am invata alt limbaj si am renuntat la borland ...

adica ai trecut la pascal? ca pana la urma devu e tot c++ deci e ac limbaj

un iepure poate avea doi sefi directi?

problema asta a mai fost data la ACM Varna 1992 (din intamplare am gasit-o intr-o culegere acum trei zile )

asta ca o simpla curiozitate

aaa... m-am prins acum mersi 

Problema se poate rezolva asa:

1. Faci un graf cu nucile + pozitia initiala.
2. Faci o dinamica, a[ i ][ j ] -> costul minim sa mergi prin nodurile din configuratia binara a lui i si sa te afli in nodul j.

Daca nu intelegi, mai detaliez. Complexitatea finala e O(2 ^ n * n ^ 2) si ar trebui sa intre in timp.

mai exact?  de unde apare 2^n (din parcurgerea intre i si j? )

cum se face problema asta? eu am asezat nucile pe un graf (sunt mai putin de 15) si am facut permutari sa vad drumul minim, dar nu-mi intra in timp (se poate face altfel? cu lee nu cred ca merge )

http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&page=show_problem&problem=1885

da... nu stiu sigur daca am implementat sort din stl bine (eu lucrez in c) da cu qsort nu intra in timp... cu asta intra dar imi da incorect

pai... ar fi cateva chestii daca vrei sa te apuci serios:

1:   lucrat mult pe ia  (sunt multe probleme frumoase daca stii de unde sa le apuci)

2:   oji-urile din anii trecuti de facut   (le poti lua de pe olimpiada.info cu tot cu evaluator si teste)

3:   sa inveti ceva algoritmi (dinamica,lee,etc)

4:   ar mai fi si cartea Introducere in algoritmi, Thomas Cormen, editura Agora, Cluj-Napoca (de asta am auzit si eu pe aici pe forum... nuj cum e da am auzit ca e buna... ma corectati daca gresesc... desi nu cred  )
  uite aici un link.. de unde poti sa o comanzi (e 720 000 pt elevi ) http://libris.agora.ro/algoritmi.html


daca mai gasesc ceva iti mai zic

tu ai o sortare in N*N care nu este foarte eficienta... incearca sa pui alta... presupun ca nu stii qsort cu structuri  ... gandeste-te ca tu ai temperaturile cuprinse intre -100 si 100... te ajuta la ceva? (le pui in galeti (cate sunt cu -100 cate cu -99... etc (bucket sort  o(n+200)   )      ) adica incearca bucket sort sau incearca cu qsort... amandoua merg rapid (cu sort din STL nu prea stiu exact cum e pt structuri pt ca eu lucrez in c nu in c++)

mie imi da NU NU NU... tre sa mai lucrez la ea  si aia cu reinitializarea o aveam la inceput si nu imi mergea nici testu din enunt parca... dupaia am modificat si mi-a mers deci nu-i problema de la aia... da ciudat e ca am doua rezolvari (una in N^3 si una in N^4) care iau 0 puncte

LE: Cu cealalta sursa imi da NU DA DA dar iau 0 puncte

Cod:

for (k=0;k<nr;++k){
        xx=x[k];
        //printf("%d %d %d\n",x[k].val,x[k].i,x[k].j);
		if (d[ii[xx]][jj[xx]]>val[xx] && y[ii[xx]][jj[xx]]!=1 || d[ii[xx]][jj[xx]]<val[xx] && y[ii[xx]][jj[xx]]!=1){
           printf("NU\n");
           return;
        }
        if (d[ii[xx]][jj[xx]]>val[xx] && y[ii[xx]][jj[xx]]==1){
           d[ii[xx]][jj[xx]]=val[xx];
           for (a=0;a<n;++a)
               for (b=0;b<n;++b)
                      d[a][b]=min(d[a][b],min(d[a][ii[xx]] + val[xx] + d[jj[xx]][b], d[a][jj[xx]] + val[xx] + d[ii[xx]][b]));
        }
    }
    printf("DA\n");

asa fac... x este vectorul sortat iar d este matricea cu distantele. in val retin valoarea initiala in ii linia pe care se afla si in jj coloana

[afectate de setarea valorii x pe muchia (i,j). Mai exact, pentru fiecare pereche de noduri (a,b), D[a] va fi egal cu minimul dintre valoarea actuala D[a] si min { D[a] + x + D[j], D[a][j] + x + D }.Daca nu am intalnit nici o contradictie pe masura ce am parcurs muchiile, atunci raspunsul este "DA" ; in caz contrar, raspunsul este "NU".]

fac exact ca in articolul de solutii

Vom sorta toate cele O(N2) distante din matrice in ordine crescatoare si vom initializa o matrice D[j]=infinit, pentru i <> j, respectiv 0, pentru i=j. Pe masura ce parcurgem sirul sortat al distantelor, vom actualiza valorile din matricea D. Sa presupunem ca am ajuns la o distanta avand valoarea x, ce reprezinta distanta minima dintre 2 noduri i si j. Daca D[j] < x sau D[j] > x si nu exista muchie in graf intre i si j, atunci nu avem solutie si ne oprim. Daca D[j] > x si exista muchie intre i si j, atunci vom pune pe aceasta muchie costul x. In continuare, va trebui sa actualizam valorile D[a] afectate de setarea valorii x pe muchia (i,j). Mai exact, pentru fiecare pereche de noduri (a,b), D[a] va fi egal cu minimul dintre valoarea actuala D[a] si min { D[a] + x + D[j], D[a][j] + x + D }.

Daca nu am intalnit nici o contradictie pe masura ce am parcurs muchiile, atunci raspunsul este "DA" ; in caz contrar, raspunsul este "NU".

am schimbat sortarea din qsort in sort din stl si acum merge in timp da imi da incorect...

puteti si voi sa puneti un test mai lung? ca nu ma prind

solutia in n^4 nu intra in timp? (nici cea din articolul de solutii nu-mi intra)

pai numarul de cifre al rezultatului este retinut in rez[0]

cat c++ cunosti tu daca nu sti baza? adica using namespace si stdio (e bine sa te obisnuiesti fara streamuri)

si using namespace std e in c++

la problema asta iau 90 de pct si imi da pe un test fisier de iesire corupt... ce inseamna? ca nu am creat fisier de iesire? sau ca nu am avut raspunsul corect?

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

deci... de ce iti da SIGSEGV? declari un vector de 100 si tu folostesti componenta 150 de ex?

1: editeaza postu' si baga tagul "code"

2: incearca sa citesti cu citire in c (scanf si fscanf) merge mai repede

mai  mici limitele de timp    tu ce sortare folosesti? ca daca folosesti bubble nu ma mir ca ai TLE si iei doar 30 pentru ca sunt grupate testele

adica? cum iei 0? ce mesaj iti da?

si nu e gresit... eu am luat 100