infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Dan-Leonard Crestez din Martie 08, 2004, 20:00:20

Titlul: 007 Datorii
Scris de: Dan-Leonard Crestez din Martie 08, 2004, 20:00:20

Aici puteţi discuta despre problema Datorii (http://infoarena.ro/problema/datorii).

Titlul: 007 Datorii
Scris de: lemon din Martie 26, 2004, 16:28:24

exista cumva o modalitate mai rapida decat fscanf de a citi dintr-un fisier?
oricum se poate divulga care este m si n pentru primul test pt ca imi iese din timp la toate testele si eu zic ca nu e chiar asa de prost algoritmul care l-am trimis?!

Titlul: 007 Datorii
Scris de: Cristian Strat din Martie 26, 2004, 19:27:53

citirea se incadreaza sigur in timp. parca mergea in timp si cu stream-uri. totul tine de algoritm.
pentru ca altfel ar fi o problema usoara, toate testele au M si N imens, adica spre maxim. :twisted:
o complexitate O(MlgN + NlgN) e de ajuns.

Titlul: 007 Datorii
Scris de: Bogdan-Alexandru Stoica din Decembrie 11, 2004, 19:47:38

Eu am rezolvat problema in o(M*sqrt(N)) si am primit TLE la toate testele. Chiar ajea de mari sunt valorile???Totushi M*sqrt(N) e ceva fata de un M*N. :P

Titlul: 007 Datorii
Scris de: Twister din Ianuarie 28, 2005, 19:09:07

si cum calculati voi suma de la p la q intr-un moment anume in O(lg N) ? :oops: :? :?:

Titlul: 007 Datorii
Scris de: Silviu-Ionut Ganceanu din Ianuarie 28, 2005, 23:39:05

Cauta informatii despre Arbori indexati binar. Hmm.. uite o idee de un articol pe info.devnet .. :)

Silviu

Titlul: 007 Datorii
Scris de: Cosmin Negruseri din Ianuarie 29, 2005, 00:09:18

Articol despre arbori indexati binar din ginfo: http://www.ginfo.ro/revista/13_1/focus.pdf

Titlul: 007 Datorii
Scris de: Twister din Ianuarie 29, 2005, 20:00:54

multumesc frumos, o sa studiez materialul chiar acum

Titlul: 007 Datorii
Scris de: Bogdan-Cristian Tataroiu din Ianuarie 30, 2005, 14:47:06

mersi :wink: cool thing to know.

Titlul: 007 Datorii
Scris de: Silviu-Ionut Ganceanu din Ianuarie 30, 2005, 19:40:14

Bogdane, sa nu-mi spui ca ai inteles !! :)

Titlul: 007 Datorii
Scris de: Bogdan-Cristian Tataroiu din Ianuarie 31, 2005, 14:37:16

Da am inteles (pt unidimensional, celelalte nu le-am citit inca). Nu era greu, daca stiai teoria.

Titlul: 007 Datorii
Scris de: cristi8 din Februarie 10, 2005, 17:05:44

poate sa imi zica si mie cineva testul 2 ? ..iau 80/100 ca imi iese din timp la T2

edit: nevermind... gata, am luat 100 :D

Titlul: 007 Datorii
Scris de: Tiberiu-Lucian Florea din Februarie 10, 2005, 20:16:07

Si la ce ti-ar fi folosit testul 2? Ca sa te convingi ca iti iese din timp? 8)

Titlul: 007 Datorii
Scris de: cristi8 din Februarie 11, 2005, 17:13:07

..hmmm... pai poate era un bug si nu mai iesea dintr-un subprogram recursiv sau ceva de genu asta...

Titlul: 007 Datorii
Scris de: Twister din Martie 24, 2005, 13:01:45

#-o #-o :oops: :oops:

Titlul: 007 Datorii
Scris de: Gogu Marian din Martie 24, 2005, 13:34:05

Testele sunt toate aproape de maxim. Incearca sa nu mai folosesti subprograme, ca sunt un pic mai incete. Calculeaza totul in programul principal.
Nu stiu cat de mult o sa te ajute, dar sa stii ca am incercat cu arbori de intervale si imi iese din timp la un test(si de fiecare data e alt test parca, dar).
Nu stiu nici eu ce optimizari sa fac, dar poate e doar fiinca am facut in pascal.

Titlul: 007 Datorii
Scris de: Cosmin Negruseri din Martie 24, 2005, 13:44:07

Programul tau face log^2 n calcule pt un query pt ca la fiecare aflare a celui mai nesemnificativ bit de 1 tu faci for .... daca tot stii ca ai acelasi numar si i-ai anulat pe o pozitie ultimul bit de 1 atunci nu mai are rost sa faci de la 0 forul ci de la ultimul bit pe care l-ai anulat, astfel complexitatea pt un query o sa fie log n. Sau ai putea folosi formula:

Cod:

(x ^ (x-1)) & x

pentru a afla cel mai mic bit de 1 al numarului. Problema s-ar putea sa nu fie asta ... cateva puncte ar trebui sa prinzi si cu rezolvarea ta.

Titlul: 007 Datorii
Scris de: Twister din Martie 24, 2005, 15:05:26

ok, multumesc frumos, dar si cu formula tot iau 0 puncte; in sfarsit cred ca o s-o las balta; cel putin pentru moment...

Titlul: 007 Datorii
Scris de: Cosmin Negruseri din Martie 24, 2005, 18:13:27

Vad ca tu ai lasat sirul neinitializat .... si asa e ca si cum ar porni de la 0.

Titlul: 007 Datorii
Scris de: Cosmin Negruseri din Martie 24, 2005, 18:17:45

Am adaugat la sursa ta:

Cod:


   for (int i=1; i<=n; i++) {
     fscanf(fi, "%ld", &x); 
     sell(i,-x);     
   }

si am folosit si

Cod:

 x -= (x ^ (x-1)) & x;

in loc de getk sau ce foloseai tu acolo si a mers de 100 de puncte.

Titlul: 007 Datorii
Scris de: Twister din Martie 24, 2005, 21:40:43

As vrea sa-mi cer scuze pt tot; mai ales ca sunt incepator in C++, dar mie tot nu-mi iese; adica am adaugat ce mi-ai spus tu si sursa a devenit asa:

am scos codul;;

si tot imi iese din timp; te rog, daca nu sunt prea enervant sa-mi spui unde gresesc, si imi cer scuze inca o data pentru deranjul provocat.
Multumesc frumos.

Titlul: 007 Datorii
Scris de: Cosmin Negruseri din Martie 24, 2005, 21:53:55

Bineinteles ca la sell e x += (x ^ (x-1)) & x; nu cum ai scris tu ...

Titlul: 007 Datorii
Scris de: Cosmin Negruseri din Martie 24, 2005, 21:57:00

Ar trebui sa iti editezi toate posturile si sa scoti codul ca sa nu faca un simplu copy paste baietii pt a lua 100 de puncte.

Titlul: 007 Datorii
Scris de: Twister din Martie 24, 2005, 22:00:24

#-o #-o #-o :oops: :oops: :oops:
Incredibil!!! Cat conteaza un + in loc de - la C++ :shock: ;
in pascal nu era o asa tragedie; in orice caz iti multumesc mult mult de tot pentru tot ajutorul acordat :oops: :oops: :oops:

Titlul: 007 Datorii
Scris de: Twister din Martie 24, 2005, 22:02:15

o sa tin minte problema asta toata viata mea; mai ales ca este prima problema a mea facuta in C :) :)

Titlul: 007 Datorii
Scris de: Kelemen Stelian din Martie 24, 2005, 22:02:17

hey cosmin, ce ID de yahoo messenger ai ?

Titlul: 007 Datorii
Scris de: Cosmin Negruseri din Martie 24, 2005, 22:02:43

Ai glumit cred cu faza cu pascalu .... si eu tot in pascal lucrez de obicei.

Titlul: 007 Datorii
Scris de: Twister din Martie 24, 2005, 22:04:08

Citat din mesajul lui: Cosmin

Ai glumit cred cu faza cu pascalu .....

:) :) :)

Titlul: 007 Datorii
Scris de: Cosmin Negruseri din Martie 24, 2005, 22:04:53

Bah Matrix, am vazut ca esti din Bistrita si am zis ca nu mai fac misto de tine, da can zici hey ma exasperezi :) vorbeste si tu ca omu normal ... id pe messenger iti zice bindea sau tucu

Titlul: 007 Datorii
Scris de: Kelemen Stelian din Martie 24, 2005, 22:05:58

bine, scuze ca te-am enervat, am cerut id, pt ca si eu is din bistrita

Titlul: 007 Datorii
Scris de: Kelemen Stelian din Martie 24, 2005, 22:07:32

acum si Calin, si domnul profesor sunt la Galati si de aceea te-am intrebat

Titlul: 007 Datorii
Scris de: Cosmin Negruseri din Martie 24, 2005, 22:10:08

Forumu asta are optiune de a trimite mesaje private ... iti trimit acuma.

Titlul: 007 Datorii
Scris de: Piros Lucian din Mai 27, 2005, 09:37:28

0.2....limita de timp? Cu tot cu arbori indexati binar si operatii la nivel de bit nu reusesc sa scot un timp mai bun de 0.21-0.23.

Titlul: 007 Datorii
Scris de: Cosmin Negruseri din Mai 27, 2005, 10:12:10

Cum gasesti cel mai putin semnificativ bit diferit de 0?

Titlul: 007 Datorii
Scris de: Piros Lucian din Mai 27, 2005, 10:21:05

Citat din mesajul lui: Cosmin

Cum gasesti cel mai putin semnificativ bit diferit de 0?

Adun si scad cu formulele acestea (ma refer la noua pozitie in vector)
poz += (poz ^ (poz-1))&poz;
poz -= (poz^(poz-1))&poz;

Titlul: 007 Datorii
Scris de: Cosmin Negruseri din Mai 27, 2005, 11:50:42

Probabil ai bushit altceva pe acolo, s-ar putea si sa ai un ciclu infinit pe undeva pt ca la depasire de timp evaluatoru iti opreste solutia.

Titlul: 007 Datorii
Scris de: Piros Lucian din Mai 27, 2005, 12:44:52

Citat din mesajul lui: Cosmin

Probabil ai bushit altceva pe acolo, s-ar putea si sa ai un ciclu infinit pe undeva pt ca la depasire de timp evaluatoru iti opreste solutia.

OK. Am gasit care era problema. Scrierea/citirea din fisier. Am schimbat de la c++ io la c io adica de la ifstream/ofstream la fscanf/fprintf....si intra lejer in timp. Foarte urat din partea lui :(

Titlul: 007 Datorii
Scris de: PopDragos din Noiembrie 15, 2005, 19:32:06

imi poate da shi mie cineva un test ca mie imi merg toate acasa shi iau tot 0 puncte ](*,)

Titlul: 007 Datorii
Scris de: Cristian Strat din Noiembrie 15, 2005, 19:44:09

Ideea e să foloseşti un algoritm suficient de rapid, nu doar corect.
Probabil iei 0 puncte din cauză că obţii

Time Limit Exceeded

(btw, asta poţi vedea în monitorul de evaluare)

Titlul: 007 Datorii
Scris de: PopDragos din Noiembrie 16, 2005, 19:19:12

Prima data ma luat WA dar acum am rezolvat problema si iau TLE.
Imi spune si mie cineva echivalentul pascal la
poz += (poz ^ (poz-1))&poz;
poz -= (poz^(poz-1))&poz;

Titlul: 007 Datorii
Scris de: Vlad Berteanu din Noiembrie 16, 2005, 19:21:47

poz:=poz + ((poz)xor(poz-1))and(poz)
poz:=poz-((poz)xor(poz-1))and(poz)

Titlul: 007 Datorii
Scris de: Lucescu Andrei Bogdan din Decembrie 15, 2005, 21:21:16

NU se poate asa ceva , am facut problema , am invata arbori indexati binari, am mers de la c++ la c ca sa-mi intre in timp si acuma aflu ca nu e bun rezultatu , exemplus si orice alt ceva am testat imi merge perfect , va rog da-ti-mi si mieva rog un test mai complicat sa ma conving ca nu merge

nu mai conteaza , am reusit sa o fac , era o greseala stupida , ceva ce nu se observa decat la testele mari

Titlul: 007 Datorii
Scris de: Savin Tiberiu din Februarie 08, 2006, 11:59:07

am shi eu o nelamurire. De ce atunci cand folosesc urmatoarea functie ptr a determina nr de 0-uri terminale imi zice Run Error - invalid memory reference

Cod:


void nr0(int k)
{return (k^(k&(k-1)))>> 1;}

iar dak o folosesc pe urmatoarea

Cod:


int nr0(int k)
{int nr,x;
x=k;
nr=0;
while (!(x%2))
{x=x >> 1;nr++;}
return nr;
}

imi iesa din timp. Care e problema la prima functie??

Titlul: 007 Datorii
Scris de: Silviu-Ionut Ganceanu din Februarie 08, 2006, 12:25:43

Pentru K = 10100 prima functie face asa:

(10100 ^ (10100 & 10011)) >> 1
(10100 ^ 10011) >> 1
(00111) >> 1
= 00011 = adica 3 in baza 10

=> Functia nu returneaza numarul de zerouri terminale !

Functia ta incearca sa determine cel mai nesemnificativ bit dar ar merge doar daca elimini siftarea la dreapta si ai inversa & cu ^ (cred). Daca faci lucru asta atunci functia va return 2^x, unde x e numarul de zerouri terminale (adica ce returneaza functia a doua).

Inainte sa folosesti o functie in programele tale, gandeste-te un pic ce face. Eventual ia un exemplu si vezi cum functioneaza. Eu cred ca ai incercat sa iei functia de-a gata de pe undeva si sa o bagi in programul tau (zic si eu, poate gresesc).

Silviu

[Later edit]: Btw tipul din avatarul tau e kinda` gay :) Sau e tipa ?

Titlul: 007 Datorii
Scris de: Savin Tiberiu din Februarie 08, 2006, 12:32:08

intr-adevar formula aia am gasit-o undeva insa am gasit-o asha cum mi-ai zis u (fara shiftare) si imi afiseaza 2^x , x fiind nr de zerouri in baza 2, shi dak ii pun acea shiftare imi da exact x (nu asha ar trebui). VEZI CA AI GRESHIT CAND AI CALCULAT 10100 & 10011, E 10000. Shi plus dak ar fi asta ar trebuie sa dea Wrong answer nu run error - memory reference failed.

BTW :tipu de la avatar e DANI FILTH, shi nu e gay, ptr cei care nu au auzit de el e solistul trupei CRADLE OF FILTH, cine nu a auzit de aceasta trupa sa caute nishte melodii ptr ca (virgula) canta mishto, asta dak va place black metalul sau gothikul

Titlul: 007 Datorii
Scris de: Savin Tiberiu din Februarie 08, 2006, 13:27:12

scuze ptr insistenta dar ma lamureshte shi pe mine cineva pana la urma??

Titlul: 007 Datorii
Scris de: Filip Cristian Buruiana din Februarie 08, 2006, 18:07:50

Nu fa functie de fiecare data ca sa afli nr. de 0-uri terminale, pentru ca nu trebuie sa incepi numaratoarea de fiecare data de la 0. Uite, de exemplu, iti dau functia de query ( suma numerelor de la 1 la X ) - poate te lamureste:

Cod:

int query(int X)
{ int p; // numarul de biti de 0 terminali;
   int S = 0;

   while (X > 0)
   {
          S += v[X]; // v este AIBul tau
          while ( ((1<<p)  & X) == 0) p++;
          X -= (1<<p);
          p++;
   }
  return S;

}

Update-ul fa-l tu similar :)

Titlul: 007 Datorii
Scris de: Silviu-Ionut Ganceanu din Februarie 08, 2006, 18:58:14

Citat din mesajul lui: devilkind

Intr-adevar am gresit acolo :) My bad :-$

Raspunsul lui Filip e la obiect, te lamureste de ce iei TLE si cum ai putea sa scapi de el.

(2^x) >> 1 = (2^x) div 2 != x (pentru multe cazuri)

Eu cred ca tu sa vrei implementezi AIB-uri si nu-ti trebuie numarul de zero-uri terminale ci 2^(numarul de zerouri terminale). Asadar functia initiala fara shiftare will do (si solutia propusa de Filip merge dar cred ca e mai inceata).

Have fun,

Silviu

PS: Stim Cradle .. dar nu ne place :P Join the good side man! :)
:surrender:

Titlul: 007 Datorii
Scris de: Savin Tiberiu din Februarie 08, 2006, 19:49:55

intr-adevar ai dreptate am nevoie de 2^x. doar ca eu copil idiot faceam numaru de zerouri terminale shi apoi faceam 2^x, fara sa imi dau seama ca il aveam deja calculat. me stupid.

PS: Gusturile muzicale nu se discuta

Titlul: 007 Datorii
Scris de: andreit1 din Martie 07, 2006, 18:18:40

Ai citit ce s-a discutat mai sus pe forum? 2^nr_zerouri il calculezi in timp constant? Citirea si afisarea poti sa o faci linistit cu fscanf si fprintf ca intra in timp.

Titlul: 007 Datorii
Scris de: Filip Cristian Buruiana din Martie 07, 2006, 20:24:11

Uite functiile de update si query:

Cod:

int query(int x)
{
    int r = 0;
    for (; x; x -= x ^ (x-1) & x)
        r += A[x];
    return r;
}

Cod:

void update(int x, int v)
{
      for (; x <= n; x += x^(x-1) & x)
          A[x] += v;
}

Si cand citesti operatiile din fisier, pur si simplu apelezi functiile. Iar ca sa determini suma pe secventa <i,j> faci query(j)-query(i-1).
Si nu mai postati :aggressive: surse :annoyed: :annoyed: :annoyed:
Spatiu irosit de aiurea pe forum.

Si eventual sterge-l tu cu butonul edit!!!

Edited by svalentin: tagul e "code", nu "quote" pentru formatare corecta ;)

Titlul: 007 Datorii
Scris de: Savin Tiberiu din Martie 08, 2006, 14:44:09

Filip, cum explici faptul ca folosind functiile pe care u le-ai scris mai sus obtin TLE la toate testele?

Titlul: 007 Datorii
Scris de: u-92 din Martie 08, 2006, 15:27:43

in ce lucrezi ? daca in pascal nustiu ce sa zic, dar eu am trimis mai`nainte surse cu extensia .c si .cpp si intra in timp

Titlul: 007 Datorii
Scris de: Savin Tiberiu din Martie 08, 2006, 18:40:28

c++, shi am trimis mai devreme o sursa folosind aceste 2 functii shi nu mi-a intrat in timp.

Dak vrei iti trimit un pm cu sursa sa vezi daca e bine ce am facut.

[Later edit] am luat 100 intre timp, eu citeam cu streamuri. mersi u-92. Pacat ca mi-am dat seama asha tarziu, mi-am batut capul o gramada incercand tot felul de optimizari, cand nu trebuia decat sa schimb functia de citire. ](*,)

Titlul: 007 Datorii
Scris de: Savin Tiberiu din Martie 10, 2006, 16:01:39

tibilets vezi sa foloseshti fscanf si fprintf, dak foloseshti streamuri nu o sa iti intre in timp orice optimizari ai face u, asha am patit shi eu. Dak nici asha nu iti merge trimite-mi sursa pe privat, nu o mai posta pe forum ptr ca poate fi o gresheala minora pe care uni sa o vada shi sa dea copy paste.

Titlul: Raspuns: 007 Datorii
Scris de: nivan din Septembrie 28, 2006, 18:18:59

Fac cu arbori indexati binar si folosesc scanf() printf() cu freopen(). Am optimizat cat am putut... totusi scot doar 80 puncte (TLE pe testul 4). :dontgetit: Singura optimizare pe care nu am facut-o e ca folosesc functii pentru Add, Sub si GetSum (adica sa introduc un element, sa scad valoarea unui element si sa gasesc suma pe intervalul <in,sf> ) :-' . Folosesc functii si pentru a obtine cate zerouri are la sfarsit un numar in binar.
Totusi nu cred ca influenteaza faza cu functiile.............

Titlul: Raspuns: 007 Datorii
Scris de: u-92 din Septembrie 28, 2006, 18:35:20

de ce nu afli numarul de zero-uri terminale in timp constant?

Titlul: Raspuns: 007 Datorii
Scris de: nivan din Septembrie 28, 2006, 18:36:08

nu prea inteleg la ce te referi.... :oops:

Titlul: Raspuns: 007 Datorii
Scris de: u-92 din Septembrie 28, 2006, 18:39:57

uita-te la postul de mai sus al lui filipb, la functiile alea.. "x+=x^(x-1)&x" sare direct la numarul care trebuie

Titlul: Raspuns: 007 Datorii
Scris de: nivan din Septembrie 28, 2006, 18:41:10

ms... :) pe viitor voi citi si mai sus pe forum :aha:

[Last Edit] Si eu parcurgeam ca prostu' prin ele......

Titlul: Raspuns: 007 Datorii
Scris de: David si Goliat din Octombrie 19, 2006, 17:55:47

Iau WA pe toate testele cu toate ca mie imi merge bine .
Am auzit ca daca vrei sa citesti cu scanf() un numar long int nu faci scanf("%ld",&x); ca in linux nu merge . E adevarat ?

Titlul: Raspuns: 007 Datorii
Scris de: u-92 din Octombrie 19, 2006, 19:34:44

poti face un program la a+b sa testezi
legat de WA, ai generat teste aleator si programul tau da acelasi raspuns cu brute-force`ul?

Titlul: Raspuns: 007 Datorii
Scris de: ditzone din Octombrie 20, 2006, 11:58:20

Tipul de date e long long.
Citirea si afisarea se aface cu %lld

Titlul: Raspuns: 007 Datorii
Scris de: David si Goliat din Octombrie 20, 2006, 20:47:51

Gata , am luat 100 :yahoo:

Citat

legat de WA, ai generat teste aleator si programul tau da acelasi raspuns cu brute-force`ul?

Da, numai ca testele le faceam eu
Ar trebui specificat de long long in restrictiile problemei

Titlul: Raspuns: 007 Datorii
Scris de: Bondane Cosmin din Octombrie 27, 2006, 18:59:02

chiar nu inteleg de ce iau WA pe toate testele. Fac cu arbori de intervale, folosesc long long . Toate testele care le dau imi ies. :oops:
poate sa ma ajute cineva?
[ii trimit sursa mea eventual ?]

Titlul: Raspuns: 007 Datorii
Scris de: Bondane Cosmin din Octombrie 28, 2006, 16:41:49

:oops: in sfarsit 100. multumesc celor care m-au ajutat. [greseala era ca declar prea mica dimensiunea arborelui :fighting:]

Titlul: Răspuns: 007 Datorii
Scris de: Gabriel Bitis din Martie 27, 2007, 19:47:50

iau 212ms si 216 ms ](*,) .. cred k renunt la ea

Titlul: Răspuns: 007 Datorii
Scris de: Codrea Marcel din Martie 27, 2007, 20:12:30

Probabil ca ai timpi de 212 si 216 ms pt ca evaluatorul intrerupe rularea programului dupa expirarea timpului limita , deci nu e relevant ! :peacefingers:

Titlul: Răspuns: 007 Datorii
Scris de: Bondane Cosmin din Martie 27, 2007, 20:41:10

Daca faci cu arbori de intervale renunta :P incearca AIB intra lejer in timp :thumbup:

Titlul: Răspuns: 007 Datorii
Scris de: Gabriel Bitis din Martie 28, 2007, 08:09:16

sunt doar clasa a 10'a.. si inca nu am invatzat chestii d'astea ca si "arbori indexati binari".. o alta solutie mai accesibila exista? :-s

Titlul: Răspuns: 007 Datorii
Scris de: Savin Tiberiu din Martie 28, 2007, 08:18:40

nu prea, dar daca ai sa citesti un articol despre arbori indexati binari (google it) cu siguranta vei intelege.

Titlul: Răspuns: 007 Datorii
Scris de: Sima Cotizo din Martie 28, 2007, 20:30:49

Nu e greu chiar daca esti a zecea... Si daca vrei sa treci peste exprimarea "pretentioasa" de aib, incearca sa vezi de fapt ce ar trebui sa aplici aici... si ai sa vezi ca nu e mare lucru...
Poate nu m-am exprimat eu cum trebuie, dar ideea ar fi sa nu te sperii de un nume de algoritm care pare mai ciudat...

Titlul: Răspuns: 007 Datorii
Scris de: Ionescu Victor din Martie 28, 2007, 23:37:10

e un articol in ginfo foarte bun despre arborii indexati binar...asta e linku: http://www.ginfo.ro/revista/13_1/focus.pdf sper sa fie de folos :D

Titlul: Răspuns: 007 Datorii
Scris de: Ivan Nicolae din Iulie 02, 2007, 20:09:41

Deci problema asta ma scoate din sarite de ceva timp..... cand o rezolv cu AIB iau 100 pct.......... cand incerc cu arbori de intervale iau 0 pct..... cu TLE pe toate testele..... pai ambele surse au aceeasi complexitate adica O(MlogN).
Chiar ar trebui sa fie un pic mai rapid cu arbori de intervale.... pt ca nu tre sa interoghez de 2 ori arborele ca sa aflu care e suma in Query.....

Titlul: Răspuns: 007 Datorii
Scris de: Airinei Adrian din Iulie 02, 2007, 22:04:23

Din contra, un aib merge mai bine decat un arbore de intervale :) [dar la problema asta merge de 100 si cu arbori de intervale]

Titlul: Răspuns: 007 Datorii
Scris de: Puni Andrei Paul din Iulie 02, 2007, 23:23:36

poate iti intra in ciclu infinit :-'

Titlul: Răspuns: 007 Datorii
Scris de: Ivan Nicolae din Iulie 03, 2007, 14:53:31

M-am gandit la chestia cu ciclu infinit... nu prea vad cum s-ar intampla asta.... pare corect totu'.... in fine gasesc eu ce are

--------

Mdea nush ce avea .... am implementat din nou si acuma merge... wierd

Titlul: Răspuns: 007 Datorii
Scris de: Dobre Catalin Andrei din Martie 09, 2008, 21:43:06

Am incercat sa rezolv problema cu Arbori de intervale si iau TLE la toate. Am incercat sa optimizez cat am putut, fac siftari in loc de div dar tot aceeasi chestie. Vad ca altii au reusit cu AI deci ar trebui sa mearga si la mine. Am atasat un link pentru sursa mea http://infoarena.ro/job_detail/152903?action=view-source

Titlul: Răspuns: 007 Datorii
Scris de: Nu Cred din Octombrie 16, 2008, 19:00:30

Problema este foarte usoara daca se studiaza http://infoarena.ro/aib si se rezolva http://infoarena.ro/problema/aib.

Sper ca ajuta pe cineva ce am scris mai sus. :)

Titlul: Răspuns: 007 Datorii
Scris de: Flaviu Pepelea din Octombrie 17, 2008, 13:21:36

Si cu arbori de intervale e la fel de usor ....

Titlul: Răspuns: 007 Datorii
Scris de: Carabet Cosmin Andrei din Iulie 09, 2009, 19:29:31

Poate cineva va rog sa se uite pe sursa mea?
http://infoarena.ro/job_detail/330398 Am citit articolul despre AIB si am facut exact ce spunea acolo.Exemplul merge,dar iau incorect pe toate testele
Mersi anticipat! :peacefingers:

Titlul: Răspuns: 007 Datorii
Scris de: Emanuel Cinca din Iulie 09, 2009, 20:02:06

Mai da-ti teste, nu te folosi doar de exemplu. In plus, la problema asta te poti uita pe sursele celorlalti ca sa-ti gasesti greseala!

Titlul: Răspuns: 007 Datorii
Scris de: Carabet Cosmin Andrei din Iulie 09, 2009, 22:13:48

Ma lamureste si pe mine cineva dc astea 2 fragmente de cod pentru aflarea pozitiei celui mai nesemnificativ bit de 1 nu sunt echilvalente:
1)

Cod:

		while (x%2==0)
		{
			poz++;
			x/=2;
		}

Cod:

while(!(x&(1<<poz))) 
	 poz++;

Mersi anticipat!

[editat] foloseste tag-ul "code" cand postezi cod pe forum

Titlul: Răspuns: 007 Datorii
Scris de: MciprianM din Iulie 10, 2009, 08:16:09

Verifica daca ai initializat poz cu 0; De ce tip e x?
Daca x e long long si cel mai nesemnificativ bit e pe o pozitie poz mai mare decat 30 (si daca, cred, poz e int ) atunci 1<<poz va fi diferit de numarul pe care il cauti, pentru ca 1<<poz va fi de tip int.

Titlul: Răspuns: 007 Datorii
Scris de: Carabet Cosmin Andrei din Iulie 10, 2009, 08:49:30

poz l-am initializat cu 0 si e de tip int.
Problema nu e ce se intampla mai incolo cu 1<<poz (desi oricum poz nu ajunge sa depaseasca 30 niciodata din cauza restrictiilor : x<=15000).Ce nu inteleg e de ce merge prima varianta de aflare a lui poz,in timp ce a 2-a merge.

Titlul: Răspuns: 007 Datorii
Scris de: Halalai Tudor Andrei din Februarie 12, 2010, 17:33:50

am incercat sa fac problema cu liste si abia acum am incercat cu arbori si... :yahoo:
Ma rog abia acum merge :aha: :fool:

Titlul: Răspuns: 007 Datorii
Scris de: Paul-Dan Baltescu din Februarie 12, 2010, 23:02:18

Nu mai posta daca nu ai nimic de spus.

Titlul: Răspuns: 007 Datorii
Scris de: alexandru stefan din Martie 26, 2010, 11:53:49

imi poate explica cineva ce face "x += (x&(x-1))^x;" :-k

Titlul: Răspuns: 007 Datorii
Scris de: George Marcus din Noiembrie 25, 2010, 21:10:27

omg diferenta dintre 40p si 100p au facut-o 4-5 linii de comentarii <=> 30-40 ms

Titlul: Răspuns: 007 Datorii
Scris de: Cornigeanu Calin din Ianuarie 27, 2011, 19:42:29

Eu cred ca teste sunt un pic prea "extreme", deoarece cu exact acelasi cod, odata am luat 40 pct, odata 80 si odata 100...

Titlul: Răspuns: 007 Datorii
Scris de: Eugenie Daniel Posdarascu din Ianuarie 27, 2011, 23:08:28

Probabil limita de timp e foarte stransa pentru a fi implementate AIB-urile in loc de Arbori de intervale.

Titlul: Răspuns: 007 Datorii
Scris de: UAIC Ion Caliman din Februarie 02, 2011, 23:16:51

am folosit arbori indexati binar dar imi iese din timp la toate testele, care poate fi problema?

Titlul: Răspuns: 007 Datorii
Scris de: Paul-Dan Baltescu din Februarie 03, 2011, 00:46:51

Am impresia ca in Pascal parametrii vectori se transmit prin valoare, deci la fiecare apel al functiei suma tu ai complexitate O(N) deoarece se copiaza intreg vectorul. Nu sunt sigur ca e asa, dar ai putea sa incerci si sa vezi daca te scapa de TLE.

Titlul: Răspuns: 007 Datorii
Scris de: UAIC Ion Caliman din Februarie 03, 2011, 01:18:55

ai avut dreptate, am luat 60p, dar la 2 teste la fel arata TLE :-k

[edit]
de fiecare data sunt teste diferite? luam 60p acum iau 0, dar nu am facut modificari :annoyed:

Editeaza-ti mesajele anterioare, nu posta consecutiv.

Titlul: Răspuns: 007 Datorii
Scris de: Paul-Dan Baltescu din Februarie 03, 2011, 03:56:50

Sunt mereu aceleasi teste, dar probabil ca programul tau ruleaza aproape de limita de timp si obtii punctaje diferite. Un alt motiv pentru care iei TLE-uri este ca folosesti Pascal, care e mai incet. In rest, ai putea optimiza operatiile pe care le faci deja sau sa parsezi citirea.

Titlul: Răspuns: 007 Datorii
Scris de: UAIC Ion Caliman din Februarie 03, 2011, 13:05:18

problema este ca nu stiu ce e parsare...

Titlul: Răspuns: 007 Datorii
Scris de: Gabriel Bitis din Februarie 03, 2011, 16:42:50

Uite un feature frumos al forumului : Cauta in forum (http://infoarena.ro/forum/index.php?action=search).
Foloseste-te putin de el sa vezi daca s-a mai discutat despre parsare. Nu are rost sa umplem toate topicurile cu aceleasi subiecte.
:)

Titlul: Răspuns: 007 Datorii
Scris de: UAIC Ion Caliman din Februarie 04, 2011, 01:48:44

Multumesc! teoretic am inteles ce inseamna parsarea, dar practic nu am inteles cum o folosesti, daca ma poti ajuta cu ceva, cum se face, pas cu pas, ti-as fi recunoscator! :)

Titlul: Răspuns: 007 Datorii
Scris de: Gabriel Bitis din Februarie 04, 2011, 09:20:55

http://infoarena.ro/forum/index.php?topic=4549.0 (http://infoarena.ro/forum/index.php?topic=4549.0) acolo ai model de implementare atat pt numere pozitive cat si pt numere negative (poate o sa ai nevoie de ele mai incolo).
Ideea e ca vrei sa reduci timpul folosit pentru citirea datelor. Atunci, ca sa nu citesti foarte multe numere, pe rand, din fisier, citesti bucati din fisier si le retii ca si string'uri (poti citi cate o linie, sau cum o sa vezi in link'ul postat mai sus - bucati de X caractere) si iti formezi tu manual numerele de care ai nevoie prelucrand stringurile respective. A zis cineva ca asa merge mai repede decat citirea normala :)
Mai "pas cu pas" cum sa'ti zic? - inlocuieste bucata de cod unde citesti tu datele, cu ce am explicat mai sus.

Titlul: Răspuns: 007 Datorii
Scris de: UAIC Ion Caliman din Februarie 04, 2011, 17:57:20

cu parsare la fel primesc TLE, cred ca autorii au uitat ca unii lucreaza in Pascal si au pus limita de timp prea mica :sad:

Titlul: Răspuns: 007 Datorii
Scris de: Pripoae Teodor Anton din Februarie 05, 2011, 20:23:09

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

Titlul: Răspuns: 007 Datorii
Scris de: Petcu Ioan Vlad din Aprilie 20, 2011, 18:31:38

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

Titlul: Eroare datorii
Scris de: Bucevschi Alexandru din Martie 16, 2013, 09:22:12

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;
} :?

Titlul: Răspuns: 007 Datorii
Scris de: Pirtoaca George Sebastian din Martie 16, 2013, 10:09:25

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!

Titlul: Răspuns: 007 Datorii
Scris de: Bejenariu Ionut Daniel din Ianuarie 26, 2014, 09:13:23

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

Titlul: Răspuns: 007 Datorii
Scris de: George Marcus din Ianuarie 26, 2014, 09:43:07

Citeste threadul in care tocmai ai postat.

Titlul: Răspuns: 007 Datorii
Scris de: Crisan Vasile din August 08, 2014, 13:17:47

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();
}

Titlul: Răspuns: 007 Datorii
Scris de: Pirtoaca George Sebastian din August 08, 2014, 14:07:46

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. :ok:

Titlul: Răspuns: 007 Datorii
Scris de: Alexandru-Gabriel Ghergut din Octombrie 11, 2015, 12:58:56

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.

Titlul: Răspuns: 007 Datorii
Scris de: Mihai Calancea din Octombrie 11, 2015, 13:41:54

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.

Titlul: Răspuns: 007 Datorii
Scris de: Alexandru-Gabriel Ghergut din Octombrie 11, 2015, 15:11:51

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 :D

Titlul: Răspuns: 007 Datorii
Scris de: Bizdoc Vasile Gabriel din Octombrie 13, 2015, 19:55:40

De ce imi da 0 la toate? am inteles eu problema gresit? :angry:
# 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;}

Titlul: Răspuns: 007 Datorii
Scris de: Alexandru Valeanu din Octombrie 13, 2015, 21:31:02

Ai declarat vectorul prea mic.

Cod:

N <= 15,000

Titlul: Răspuns: 007 Datorii
Scris de: Alexandru-Gabriel Ghergut din Octombrie 14, 2015, 22:44:44

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

Titlul: Răspuns: 007 Datorii
Scris de: Roman Tudor din Mai 25, 2016, 12:44:06

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;
    }
}

Titlul: Răspuns: 007 Datorii
Scris de: Alexandru Valeanu din Mai 25, 2016, 14:00:50

Ai O(N) pe operatia de update.

Titlul: Răspuns: 007 Datorii
Scris de: Roman Tudor din Mai 25, 2016, 21:19:13

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?

Titlul: Răspuns: 007 Datorii
Scris de: Alexandru Valeanu din Mai 25, 2016, 21:52:23

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 (http://www.infoarena.ro/job_detail/1707845)

Titlul: Răspuns: 007 Datorii
Scris de: Roman Tudor din Iunie 08, 2016, 12:19:23

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

Titlul: Răspuns: 007 Datorii
Scris de: Alexandru Valeanu din Iunie 08, 2016, 12:27:34

Citat

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

Titlul: Răspuns: 007 Datorii
Scris de: Badita George din Septembrie 25, 2016, 15:46:46

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;
}

Titlul: Răspuns: 007 Datorii
Scris de: Craciun Ioan-Flaviu din Februarie 16, 2017, 22:07:09

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

Titlul: Răspuns: 007 Datorii
Scris de: Tache Radu Ioan din Martie 05, 2019, 10:22:37

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.