Merita in general, implementarea binara la cmmdc?

Depinde de limite de timp.Inca nu am intalnit o problema in care sa faca diferenta implementarea cmmdc-ului binar.Spre exemplu, la Copaci, nu e absolut nici o diferenta de timp daca fac un Cmmdc normal sau unul binar, dar oricum, probabil, la o problema cu limita de timp stransa, se vor vedea ceva diferente, desi ma indoiesc ca ar fi prea mari. 

 

Ultimul test e mic, primele 2 sunt alea mari... Nu prea aveai cum sa iei TLE pe ultimu si sa-ti intre primele 2

Nu intra problema fara sa parsezi citirea

Mda.. ..ai avut dreptate. 
M-am uitat acuma si eu in monitor la sursa aceea de 90, fara parsare a mea.

Cod:

Test	Timp executie	Memorie folosita	Mesaj	Punctaj
1	320ms	224kb	Time limit exceeded.	0
2	288ms	248kb	OK	10
...........................................................

Primul test e ala nasol.
 

Nu stiu ce sa zic... Eu luam 90 fara parsare.
( Am parsat cu fread ).

Tie cred ca O(m) din citire iti face probleme mai degraba decat O(n) din rezolvare.
Incearca sa parsezi citirea si vezi ce iese.  , desi sincer sa fiu e destul de ciudata faza, atata timp cat iti intra ultimul test in timp si nu iti intra primele doua 

Oricum, incearca si parsare ca nu ai nimic de pierdut 
 

Eu am parsat citirea...desi nu a fost nevoie decat pentru ultimul test 
 

coada alocata static, atunci aloca dinamic si sterge toate elemetnele cozii de care nu ai nevoie (adica atunci cand te duci cu p in p->next, il si stergi pe p initial...
Eu zic ca asta e cea mai usoara implementare de Lee ..

Nu stiu daca e nevoie de alocare dinamica.(  ) Merge si fara, are la dispozitie memorie destula. (  ).Desi, cred ca ar merita sa incerce cum spui tu 

Secretul problemei cred ca era sa bagi in coada Q[p] paznici si sa lasi Lee-ul sa mearga singur. ( tin minte cat m-a enervat TLE-ul si pe mine la problema asta  )

By the way, daca iese asta, merita sa incerci Barbar ( misto problema de tot  )

http://www.youtube.com/watch?v=swCqCY_d5DM&NR
Ce tolomaci...

Uite si aici....halal joc de Tycoon...
 
http://www.youtube.com/watch?v=uQrC_C6SexI&mode=related&search=

Aspra baba http://youtube.com/watch?v=dhXBBvPhGDQ
Si e din BN de pe bargau pt cine stie.

   ( Cunoastem regiunea ...  )

2. Ar fi bine sa nu folosesti structuri [mai ales in Pascal].

Sunt in C++.( ba chiar C, in sursa de fata  )

1. Ar fi bine sa folosesti sortul din STL.

Inainte sa trec sursa in STL, as vrea insa sa ma lamuresti la ceva.

3. Nu trebuie sa faci cautarea binara pentru fiecare punct. Ajunge de doua ori pe fiecare noua directie.

Cum adica ? Ca eu din ce ai spus as intelege ceva de genul : daca sunt la punctul curent (i,j), si citesc o noua directie, calculez punctul final conform directiei ( i',j') si caut binar cate numere din vectorul de capcane se afla intre cele doua puncte ( i,j ), si ( i',j' ) pe aceeasi axa evident.
Am inteles bine ?  

[m]

Iau 40 de puncte.( 6 TLE-uri )

Am rezolvat ca in solutia oficiala, dar fara STL .
Va rog sa imi spuneti exact pasii care i-ati facut, ca am impresia ca as putea optimiza putin aici la mine.
Eu fac asa:
Citesc m, n si coordonatele celor n puncte capcane.Imediat dupa aceea calculez punctele in vectorul de capcane si le sortez ( Qsort de mana ).Apoi citesc cate o directie, si ma duc la fiecare pas cerut in directie si aplic cautarea binara pentru fiecare punct( dat de directia curenta )

Imi pare rau ca am detaliat asa metoda *( care ar putea parea evidenta  ),dar sunt chiar nedumerit.. .Sa fie oare de la faptul ca nu am tinut coordonatele in doi vectori x[] si y[] ci le am  intr-o structura ? ( astfel ca nu am facut decat o singura cautare binara ... )

Any ideas ? 

pare a fi
tot ceva de genu
 http://www.youtube.com/watch?v=S18or58RHDE

  asta chiar merita vazut !!! 

( faza cu biciclistul ala care se bucura inainte sa ajunga la linia de finish e mortala  )

Nu a fost chiar 2-1, dar e bun si 0-0.In plus, dupa parerea mea, au jucat destul de bine.
Lasati ca stoarcem noi "portocala mecanica" cand jucam acasa, iar miercuri facem scor cu Luxemburg. 

Hai Romania! 

[Later Edit] 3-0 cu Luxembourg 
( nu neaparat victoria Romaniei cu un adversar totusi modest, cat egalul Bulgariei acasa cu Albania !!  )

Eu mizez pe 2-1 pentru Romania! 

Hai Romania !   

Da, pe ala il stiu, dar vreau sa invat ceva nou cu problema asta. (si in plus nu-mi intra in timp "bulaneala"). Si mi-e o lene sa ma apuc de AIB...  . De aia intrebam de el...

Daca ai manualul de clasa XI-A, de Dana Lica si Mircea Pasoi, cauta la pagina 240-241.E explicatie si implementare 

 

[later edit] Cred ca il gasesti si pe net 

ok, asta e o problema prea simpla sa nu iau 100 de p la ea...
ce are testul 6, ca vad ca toata lumea are probleme cu el? E singurul la care primesc WA.
Am pus conditia aia cu 1+8*n sa fie patrat perfect, daca nu e, afiseaza direct -1, daca e, atunci cauta suma cu algoritmul meu, si daca nu o gaseste, afiseaza -1.
Deci, exista o suma cu proprietatea respectiva... De ce primesc WA? (cu restul merge, am 95p)...
Vreo idee? Ce am uitat sa pun pe-acolo?

Si eu am stat vreo 10 minute si tot nu am reusit sa rezolv testul 6 cum trebuie.
Am luat 100 dupa ce am facut cum a spus ag3nt_junior 

Pentru a testa validitatea solutiei, comparati toate combinarile din numerele obtinute cu cele date in fisierul de intrare. Nu mai trebuie nimic altceva, si se incadreaza si in timp.

asa nu mai e nevoie de nici un caz particular de tratat, nici o impartire dubioasa etc.
 

E preferatul meu de pe YouTube 

http://youtube.com/watch?v=Smi7JDGAHWo

 

Cred ca nu s-au implementat toate chestiile astea.Si eu as fi vrut sa imi pun ziua de nastere in calendar si sa imi pot pune sa mi se vada adresa de mail, dar nu am reusit.Cred ca sunt pe to-do list la admini.
 

Ana mulgea vaca si-n apa se vedea invers.  

un banc de asta am citit (pe bune) in cartea de fizica de a 9-a, doar ca nu era considerat banc acolo... zicea ca "daca gigel ii da o palma lui ionel si ionel se supara si ii da si el o palma lui gigel, acesta nu este un exemplu de manifestare a principiului actiunii si reactiunii". 

Hai ca asta e tare.Cred ca mi l-a spus si mie mama odata ( e profesoara de fizica    )

 

Imi puteti spune dupa si inainte de care caractere sunt puse spatiu pentru ca nu pot da cu presupusul ca asa iau doar 30 puncte  , iar algoritmul meu se bazeaza pe lucrul asta. Multumesc de ajutor!

Poi daca ai facut cu separatori, pune toate caracterele care crezi ca ar putea aparea.
"`~1234567890!{@#$%^&**()-}|":+?=><,./;'[]\"

Oricum, in caz ca nu iti iese, merita sa faci cu algoritmul acela naiv din solutie ca nu scrii mai mult de 10 linii de cod in total.
 

daca dau 8 * 200 000 merge pe juma din teste...daca dau 8 * 1 000 000 ...nu merge pe niciuna:|..care mah poate ajuta sa imi dea shi mie un add

E ciudat.Mie mi-a intrat cu matrice de 1000000*8 si si acel sir ndp[] de 1000000.
Trimite-mi sursa pe mail, daca vrei, ca si mie azi dimineata mi-a iesit problema de 100 (  )

 

Nu poti trimite pe infoarena surse mai mari de 100 kb. Ideea e ca pregenerarea sa o faci la inceputul programului pe care il trimiti, nu sa folosesti o matrice de constante.

Mda..ai dreptate. Nu stiu unde mi-a fost capul.
Am luat 100.

Multumesc inca o data.
 

Am implementat exact ca in solutia oficiala.Ori sunt acuma obosit si nu mai imi dau seama de ceea ce fac insa ... e o mica problema.

Am calculat acel sir ndp[] de 1 000 000 de numere.Iar matricea aia din cate am inteles eu si din cate vad, trebuie sa aiba 1 000 000 * 8 ....sau nu ?.Problema e ca fisierul meu .cpp are 3 Mb si nu mi-l trimite.Dar tot nu inteleg cum pot calcula matricea aia fara sa tin in actualul fisier si sirul ndp[]....
Poate sunt tampit si nu vad acuma ceva minor in abordare, dar chiar nu imi dau seama ce gresesc..

*programul meu compileaza foarte greu, dar imi da bine pe exemplu si ceva teste in plus.

..help ! 

[algoritmus]

Daca e asa, s-ar mai putea si problemele de la
   -Bursele Agora ( GInfo ), cateva mai importante si de baza din punct de vedere algoritmic.
    -Lista lui Francu ( e amintita si in documentatie daca nu ma insel )
    - cele de pe algoritmus sunt iarasi misto de tot( vreo doua sunt deja pe infoarena daca nu ma insel... ).Pacat ca a incetat concursul. 

 
ma ofer si eu voluntar.

As vrea si eu sa ma bag.

Eu as propune problema Munte de la ONI 2003 Focsani. ( E problema mea preferata din toate timpurile ).Am facut o rezolvare putin mai deosebita..mai ales spre final. 

In plus am facut si eu o problema, nu e foarte grea, insa daca cineva considera ca e ok, o trimit.( Am si teste si descriere si enunt ).

  Super ideea! 

Am incercat eu si cu char si tot 60 iau.Dar faza este ca daca ar fi de la memorie nu ar trebui sa ma astept la ceva de genul : Memory Limit Excedeed sau KILLES BY SIGNAl ....
In schimb eu iau WA 

Eu cred ca gresesc algoritmul.
Am facut o matrice b[i,j] - numarul minim de diamante cu care am putut ajunge pe pozitia (i,j), iar in Lee am facut asa

Cod:

if ( b[iv][jv] > b[i][j] && a[iv][jv] == a[i][j] )
                    {
                         b[iv][jv] = b[i][j];
                         ultim++;
                         c[ultim][0] = iv;
                         c[ultim][1] = jv;
                    }
                    if ( b[iv][jv] - b[i][j] > 1 && a[iv][jv] != a[i][j] )
                    {
                         b[iv][jv] = b[i][j] + 1;
                         ultim++;
                         c[ultim][0] = iv;
                         c[ultim][1] = jv;
                    }

unde iv, jv sunt pozitiile actuale cu care merg, iar i,j pozitiile de pe care am venit.
a[i,j] - matricea initiala, iar c e coada.

Eu nu reusesc nici cum sa trec de 50 de puncte...

Cu matrice de 1000x1000 si coada de 1000x1000 iau sigsegv pe toate testele, cu coada de 1000x1000 si matrice de 700x700 iau 50... un memory limit exceeded, 3 sigsegv si un incorect...

Ceva indicii pentru reducerea memoriei? :/

Ma mir... ..mie imi intra doua matrici de 1000*1000 plus o coada de c[2501][2].
Oricum, daca crezi ca de la memorie ti se trage ai putea face cu alocare dinamica cand calculezi a doua matrice ( cea dinamica ) si retii doar rezultatul final care te intereseaza.
 

P.S. Daca iei 100, sa ma dumiresti si pe mine ca nu inteleg ce am gresit