007 Datorii

[•fluffy]

Aici puteţi discuta despre problema Datorii.

[lemon]

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?!

[•wickedman]

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.
o complexitate O(MlgN + NlgN) e de ajuns.

[•fireatmyself]

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.

[•Twister]

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

[•silviug]

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

Silviu

[•Cosmin]

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

[•Twister]

multumesc frumos, o sa studiez materialul chiar acum

[•bogdan2412]

mersi cool thing to know.

[•silviug]

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

[•bogdan2412]

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

[cristi8]

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  

[•greco]

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

[cristi8]

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

[•Twister]

     

[•gogu]

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.

[•Cosmin]

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.

[•Twister]

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

[•Cosmin]

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

[•Cosmin]

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.

[•Twister]

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.

[•Cosmin]

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

[•Cosmin]

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.

[•Twister]

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

[•Twister]

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