009 Tabela

[•k_ounu_eddy]

Cine poate sa imi dea demonstratia la problema aceasta,cand se executa doar o instructiune adica xor-ul ala,ca as fi tare curios?Va rog frumos,am cautat cartea dar nu am gasit-o.Daca vrea cineva ,sa posteze pe forum,sau daca nu sa trimita pe adresa de  mail [email protected] am fost prea indraznet,adica in sensul in care am cerut prea mult,iertati-ma.

[•wefgef]

demonstratia nu prea cred ca o stie nimeni fara sa aiba cartea respectiva.

oricum, poti sa o faci in timp logaritmic oricand. 

[•k_ounu_eddy]

Pai eu asta am intrebat ,daca are cineva si cartea,si poate sa posteze demonstratia.dar tu dark_raxvan ,nu o zic deloc cu rautate,tu de unde ai stiut formula,presupun ca o stii tot dintr-o carte,si daca ai cartea,nu poti sa ne explici si noua? :thumbup:Multumesc anticipat.

[•Agent_Smith]

Hai lasati XOR u ala in pace k daca erati la olimpiada nu va venea voua ideea aia......
Totusi observ k aven simetrie tot la 2^k (2,4,8,16,32,etc)......
si intrebarea mea se poate rezolva prin reducerea  "patratelelor" pana cand avem un patrat de 4 lemente (2x2) ?? k nu vreau sa ma apuc degeaba de ea.......  

[•andreitheo87]

De ce nu ar merge, daca esti asa de sigur pe simetria aia? Apuca-te de ea( mai mult de 10-15 linii nu ar trebui sa scri la ea) si in caz ca nu iese stai si o sa faci sa mearga... daca dupa multe ore de munca nu reusesti nimic( adica te dai batut) poti intreba pe forum...

[•skydome]

chiar ca ar trebui o minte luminata sa ne ajute si pe noi pacatosii sa ne dam seama ce face xor ala.. (helpu de la pascal nu prea ajuta    )

[•devilkind]

chiar ca ar trebui o minte luminata sa ne ajute si pe noi pacatosii sa ne dam seama ce face xor ala.. (helpu de la pascal nu prea ajuta   Thumb down )

xor e o operatie pe biti gen and sau or in pascal (&& respecti || in c/c++).

1 xor 1 =0
0 xor 1 =1
1 xor 0 =1
0 xor 0 =0

succes !

[•svalentin]

explicat in cuvinte, xor este "exclusiv or", adica fie una fie alta, dar nu ambele

[•Adix]

chiar ca ar trebui o minte luminata sa ne ajute si pe noi pacatosii sa ne dam seama ce face xor ala.. (helpu de la pascal nu prea ajuta    )

Cred ca el vroia sa intrebe cum duce XORul acela la solutia problemei.. Daca el nu atunci eu da

[•Darth_Niculus]

 E ditamai demonstratia si nush daca o mai tine cineva minte exact... de exemplu eu am cam uitat.... oricum scrie si mai sus pe forum ca poti sa gasesti demonstratia in "Probleme Neelementare Tratate Elementar" de A.M.IAGLOM si I.M.IAGLOM. Cartea o gasesti mai pe la orice bibleoteca... de exemplu eu am luat-o de la biblioteca liceului.... ceea ce-mi aduce aminte ca trebui s-o returnez   
 Oricum o sa ai de cautat pana dai de problema......
-----------------
[Later Edited] Dar o rezolvare in timp logaritmic imi pare mult mai INDICATA , demonstratia aia cu XOR nu te invata mare lucru..... oricum nu strica sa rezolvi problema in ambele moduri 

[•devilkind]

Cred ca el vroia sa intrebe cum duce XORul acela la solutia problemei.

Atunci nu inteleg ce cauta in helpu din pascal :-/

[•skydome]

am inteles ca demonstratia e lunga si nimeni nu vrea sa o scrie pe forum

am aflat si eu tabelul de adevar si nu stiam exact de unde ia valorile 0 si 1
mersi de ajutor

[•Viksen]

Vad ca nimeni nu s-a incumetat sa raspunda intrebarii cu demonstratia. Cosmin are dreptate totusi. Citind forumul (nu am cartea, shi ma indoiesc sa fie pierduta prin vreo biblioteca din Ploiesti ) mi-am dat seama de "demonstratia intuitiva" la care se referea Cosmin.
Defapt, rezolvarea in O(1) porneste din rezolvarea logaritmica. Si iata cum:

"simetriile" despre care s-a vorbit (si de care banuiesc ca s-au prins toti care au implementat logaritmic) se bazeaza pe faptul ca, daca la un pas, una din coordonate era mai mare sau egala cu 2^k, atunci ea se decrementa cu 2^k, iar daca ambele erau mai mari decat 2^k, atunci se decrementau ambele. Ideea este ca, tabela de dimensiune 2^k+1X2^k+1 se imparte in 4 cadrane de latura 2^k. (consideram cadranele in ordine trigonometrica) Daca ne aflam in cadranul 4 , atunci solutia este identica ca si cand ne-am situa in cadranul 2, pe coordonate cu 2^k mai mici. In cadranele 1 , respectiv 3, solutia este tot ca si cand am translata cadranul in cadranul 2 ( micsorand coordonata mai mare cu 2^k ) , numai ca este ca valoare cu 2^k mai mare. Acum, dupa ce am facut reducerea la cadranul 2, aplicam recursiv pentru acesta. Suma valorilor din translatarile cadranelor 1 si 3 in cadranul 2 reprezinta solutia problemei.

Acum, varianta cu xor, care este surprinzator de asemanatoare.
Considerand reprezentarea pe biti a cordonatelor. In matricea de mai sus despre care vorbeam, pasul k ( cand dimensiunile sunt 2^k+1 ) reprezinta, defapt, perechea de biti de pe pozitia k din coordonata liniei si respectiv coloanei. ( mentionez ca prin "coordonate" ma refer la linia/coloana curenta, si acestea fiind decrementate cu 1 fata de input-ul problemei, deci primul element al tabelei se afla pe pozitia (0;0) )

Astfel, cele 4 cadrane vor fi date de perechile:
(0;0) - cadranul 2 ( ambele coordonate mai mici decat 2^k )
(0;1) - cadranul 1 ( coordonata coloanei mai mare sau egala cu 2^k )
(1;0) - cadranul 3 ( coordonata liniei mai mare sau egala cu 2^k )
(1;1) - cadranul 4 ( ambele coordonate mai mari sau egale cu 2^k )

acum, bitul k al rezultatului va trebui sa fie (dupa cum am spus la prima varianta) 0 daca ne aflam in cadranele 2 sau 4 si 1 daca ne aflam in cadranele 1 sau 3 ( adica numai in cazul translatarii din 1 sau 3 in 2 se aduna 2^k ). Iata ca , bitul k din rezultat este , defapt dat de operatia xor intre perechea de biti k descrisa mai sus:

cadranul 2 : 0 xor 0 = 0
cadranul 1 : 0 xor 1 = 1
cadranul 3 : 1 xor 0 = 1
cadranul 4 : 0 xor 0 = 0

sper ca demonstratia este suficienta si nu foarte dificil de urmarit. (daca este, va rog sa mai postati)

[•hulparuadrian]

super tare formula... ...dupa cum am mai zis: "In fiecare zi inveti un lucru nou!".  Fara hinturile de pe forum nu cred k
luam 100 prea curand...fortza "bitwise operations "

[•MciprianM]

Imi da eroare in evaluator la problema asta  orice scriu

[•amadaeus]

demonstratia nu prea cred ca o stie nimeni fara sa aiba cartea respectiva.

Pentru cine cunoaste ceva din teoria Sprague-Grundy (are Cosmin un articol bun pe tema asta), o demonstratie simpla si eleganta se poate deduce de aici [...]

[•devilkind]

spoiler..

Nu ar fi trebuit sa zici ideea din spatele demonstratiei. Eu am fost destul de fericit cand m-am prins singur de demonstratie (nu de formula). Nu ar trebui sa le rapim celorlalti useri aceasta bucurie

[•amadaeus]

Am editat postul precedent. Cred ca Tiberiu are dreptate, e mai frumos cand gasesti singur o astfel de demonstratie - tin minte ca si eu eram extrem de fericit in momentul respectiv

[•lsorin_94]

sall as vrea sa fac un comm la aceasta problema rezolvarea e "relativa".... deoarece tabelul se poate face in mai multe moduri!!!! ..... macar se se spuna in problema "pt aceest tip de tabel!!!"

[•wefgef]

Si cum anume se poate face constructia tabelului in mai multe moduri?

[•lsorin_94]

poi se poate ::: linie coloana linie coloana;;;; linie linie;;;; shi coloana coloana..... toate dand rez dif......

[•wefgef]

Eu zic sa recitesti enuntul.

[•veleandu]

  i foarte penal .. tot timpul wrong answer .. cred ca si cu o sursa buna miar da asta am facut ca alti cu simetrie in o(1) bine .. cu niste calcule in plus adunari .. inmultiri si altele .... dar totusi e penal rau      

Edit:
  miam dat seama ceam gresit da tot penal ramane programu    

Editat de admin: Nu mai posta de doua ori consecutiv. Foloseste butonul "Modifica".

[•darkseeker]

Cu algoritmul meu iau 0 puncte si nu inteleg dc imi da wa pe toate testele.eu folosesc o matrice de 4X4 in care generez cadranul in care se afla punctul de coordonate l,c,si apoi folosesc resturile impartirii la 4 a lui l si respectiv c, pentru a gasi punctul in matricea mea,dupa care il afisez.pe exemple imi merge,de asemenea merge pe orice numar din cele 6 cadrane ale tabelei.matricea este unsigned long la fel si variabilele l si c.

Edit:
daca nu puteti sa ma ajutati cu algoritmul dati-mi atunci niste teste cu valori mari sa vad daca le pica programul meu

Editat de moderator: Nu mai posta de doua ori consecutiv. Foloseste butonul "Modifica"

[•dornescuvlad]

Am o nelamurire la rezolvarea in O(log(N)).
Am citit posturile anterioare si am inteles cam asa.
Daca am o tabela de latura 2^(k+1) o sa am patru cadrane de latura 2^k (pe care le numerotam in ordine trigonometrica).O valoare de pe coordonatele (x,y) din cadranul 4 este egala cu valoarea de pe coordonatele(x - 2^k, y - 2^k) din cadranul 2.
Care este legatura dintre cadranul 3 si cadranul 1 si cum conduc relatiile astea la rezultat?
Multumesc!