infoarena

Aici puteţi discuta despre problema Tabela (http://infoarena.ro/problema/tabela).

aici e formula... nu? :idea:

Nu se stie  :P

Sigur nu are  formula, ca ma chinui de 3 zile sa ma prind de problema!!!!!!

Cristy: problema e cunoscuta, are si formula, dar eu am luat [mai demult, ce-i drept] maxim FARA formula [sunt niste relatii de simetrie parca, aduci nr la linia 1, colona nr. pe care tre sa afisezi].

Succes  :D

eu am o solutie (extrem de simpla) pentru problema (doar pentru unele cazuri - nu am continuat  "generalizarea" pt ca ma asteptam ca din cele 50 de teste macar 10, 20 sa functioneze )  pe care o consider corecta dar cand o incerc imi da wrong answer la toate testele ..  poate cineva sa ma ajute???

Eu am gasit o solutie EXTREM de simpla la problema (pe care am luat 100 - dar pe un user cu alt nume). E O(1) si e asa de simpla incat orice indiciu ar duce imediat la rezolvare... deci nu voi da indicii.

Ma intrebam totusi daca solutia O(1) este cunoscuta, fiindca recent cineva (de fapt mai multe persoane) mi-au spus ceva de o solutie ce folosea mod 4 si parea a fi o solutie O(log(n)) relativ complicata.

... si pentru ca solutia O(1) pare prea simpla pentru o problema de pe infoarena  :roll:

Solutia oficiala e tot O(1)  :-$

Am facut o rez in log4(n), care e compusa din 5 randuri de algoritm... Sunt curios cum faci problema in O(1).... Daca poate cineva, sa-mi trimita si mie aceasta rezolvarea pe mail...  [redacted]@gmail.com

Gandita in termeni de algoritmi problema e prea draguta pentru a scrie o formula intr-un fisier sursa. Rezolvarea in log4(n) nu e complicata deloc. Mai mult, algoritmul se arata foarte natural.

Hint....incercati recursivitate. Din algoritm aproape se arata si formula.... La formula (daca tot vreti formula), un element ajutator ar fi sa incercati sa scrieti L si C ca suma de puteri ale lui 4 (legat de puterile lui 4 --- este inca un element ajutator pentru "detectarea" algoritmului ;)).

Succes

:? De ce ar vrea cineva sa rezolve problema in 5 randuri in O(ln(n)), atunci cand ea poate fi rezolvata in 1 rand, O(1)? Nu cred ca scopul unui programator ar trebui sa fie gasirea algoritmului mai complicat, ci a celui mai rapid (care in acest caz este si mai simplu).

am 100 la problema asta...care are o solutie de o(1) sa mi ` o trimita pe adresa mea de mail ...sunt curios pt eu n ` am gasit asa ceva!
[email protected]
mersi

ps . solutia mea e in o(log 4 de n)

Buna! Sunt si eu unul dintre cei care am rezolvat in O(log4(n))  :D. Si daca cineva ar putea, as vrea sa vad si eu solutia in O(1). Daca ar putea cineva sa mi-o dea si mie pe mail i-as fi recunoscator.  :wink: .

da, si eu la fel. PM pls.. sau mail :D

Aceasta este o problema extrem de simpla.
Am 100 de puncte si problema mea merge in cel mai scurt timp posibil deoarece eu fac doar o singura operatie. Operatie de "^" adik xor.
Aplicand aceasta operatie intre cele doua numere decrementate obtinetzi 100 de puncte. Garantez 8)

poti sa imi si demonstrezi asta???
p.s.  nu trebuia sa pui formula pe forum!!! acuma o sa stie oricine!!!  [-X   , geniule  :-#

Esti bazat mah :) si nici nu esti egoist ... nu e prea bine sa fie direct ideea pusa pe forum ca sa mai gandeasca oamenii, un hint ar fi fost mai folositor, dar daca tie iti place asa nu e nici o problema, oricum chestia cu xoru era cam greu sa iti vina daca nu o vedeai inainte, si problemele de formula sunt naspa ...

..chiar.. cum te-ai prins ca trebuie sa faci xor ?

..btw, stii sa demonstrezi ?

Fratzilor trebuie sa acceptatzi realitatea si la aceasta poblema nu am ce sa demonstrez. Intelectul meu este superior asa k nu are rost sa demonstrez de ce fuctioneaza. Trebuie sa o luatzi de buna.Plus k nu putetzi intelege o demonstratie asa de complicata.

intelectul tau superior cred ca va lua foc....

intelectu tau superior merita o palma...

Daca vrea cineva sa discute cu mine mai intai trebuie sa invetze de ce tabela se poate rezolva asa de usor.Plus ca daca cineva care o pus problema asta pe site si ala nu are curajul sa recunoasa realitatea sa se lase de informatica si sa se duca sa sape santzuri si dak asa, acela nu e demn de problema lui nu e demn de informatica este o rusine pentru toti cei care stiu ce inseamna informatica.

Ma, tu glumesti?
(btw, this isn't funny)

Si pana la urma care era subiectul si care era predicatul in fraza aia lunga de tot? Eu am rezolvat problema fara sa fac faza aia cu xor...am ales o rezolvare in o(log4 (n)). Si eram curios daca poti sa imi explici de unde ai dedus aceasta rezolvare care , da , este corecta! Nah ... daca esti asa bazat poate ma luminezi si pe mine! Da tu imi vii mie cu fraze si vrajeli de astea... Nu meriti nimic!

Sincer, in general am un mare respect fata de oamenii care au idei mai bune ca mine, dar in cazul tau o sa sper k chiar glumesti, fiindca replicile tale imi provoaca greata. :-&  :-& Nu te cunosc, nu vreau sa te cunosc, si iti urez bafta, fiindca cu asa o atitudine o sa ai multa nevoie.

PS: Decat sa postezi k sa te dai mare, mai bine taci si posteaza cand ai ceva de zis.

imi cer scuze in numele lui raxvan ala ... da... il cunosc... e d kkt... da nu-l bagati in seama k saracu are ceva probleme psihice  :-({|=  oricum o sa-l pocnesc pt ce o scris pe forum

lol . Locul asa e de discutat despre Tabela.  [-X

Deci draga Razvane atunci tu eshti primul care ai luat-o razna cu intelectu tau.
Tot ce ai reusit e ca te-ai facut de ras pe acest forum.

Daca tot s-a desconspirat solutia oficiala, pentru cei care vreau o demonstratie si nu numai impresiile lui razvan care probabil a auzit si el de undeva doar de formula, dar nu are nici un argument pt ea, vedeti in "Probleme neelementare tratate elementar" Iaglom Iaglom (e o carte destul de veche, dar se gasete la biblioteca) exista o demonstratie pt aceasta problema si are vreo doua pagini, eu am citit-o odata si am inteles-o atunci dar acum nu o mai tin minte. Oricum cartea are o gramada de probleme interesante si ar trebui citita ca pregatire pt olimpiada.

Mersi pentru informatie. Chiar o sa caut cartea ca suna foarte utila.  :wink:

Bafta in continuare!

razvan:
cand iti zice cineva ca esti beat, nu trebuie sa il crezi, cand iti zic doi...te duci si te culci. Tie deja ti-au zis vreo 4 ca esti prost  [-X  :-#

Razvan:
buna! Sunt sora lui Dobre si m-am inregistrat la forum doar ca sa iti zic ca si eu cred ca esti... citeste si tu ce a scris frate-meo cu un mesaj mai sus

interesanta situatie..

..oricum, sunt altii mult mai * ca razvan.. nu trebuie sa umpleti forumul luandu-va de el.. mai ales ca aici ar trebui discutata problema Tabela, nu micile probleme ale unui membru

Totul era doar o gluma si sory pentru situatzia creata.Pe viitor nu o sa monopolizez discutzia despre mine.Imi cer scuze tuturor.

fara suparare, citisem faza cu xoru intr-o carte si am incercat-o inainte sa citesc pe forum si... ghici ce ! am luat 0  ](*,)  stie cineva DE CE?

NU

poate nu ai decrementat numerele.
sau nu ai nimerit fisierul de iesire si ai scris in alta parte.
sau poate ai incercat sa citesti din alta parte.
sau poate ai gresit semnul de XOR ('^')

1, 2, 3 sau 4 ?

oricum, iti recomand sa rezolvi problema si logaritmic..

:shock:  :shock:  :shock:  :shock:  :shock:  :shock:  :shock:  :shock:

is blocat , faina rezolvare , acuma ma uit si eu peste problema , si nu imi vine sa cred ce faina e rezolvarea , pls puneti undeva pe infoarena demonstratia ca pe mine m-o lasat rece , si poate posteaza careva pe forum solutia in log n ca oricum nu o mai cauta nimeni si is curios sa vad care e

Solutia e O(log4 N) nu n log n... Fa si tu matricea aia pe dimensiuni mari si o sa vezi unele simetrii... E super frumoasa si rezolvarea in log4 N:P Ar fi bine s-o cauti singur, decat sa ceri solutia altcuiva...

Mersi, Bogdane, am vazut si eu simetrii si alte chestii... dar de ce sa rezolv in log4(n) cand pot rezolva... intr-un singur pas?!?
By the way, nu decrementam numerele... si stie cineva daca cartea aia cu demonstratia se mai poate gasi pe undeva?

Ma inclin [-o< in fata audientei si a celui care a descoperit formula

am facut deja matirucea pe dimensiuni marisoare si am obeservat foarte multele simetrii , repetiitii si astfel de chestii dar daca m-as apuca sa caut rezolvarea m-as simti ca si cum as face ceva fara sens , totusi am sa ma uit sa vad daca imi vin idei

Nu vad ce e asa de fara sens in a rezolva o problema intr-un mod algoritmic. Fara sens mi se pare sa iei 100 puncte pe o formula nedemonstrata sau, mai mult, pe care nu ai observat-o tu.

nu imi place;
orice retard , care stie sintaxa de c / pascal si putina matematica . poate sa rezolve juma din problemele din arhiva de probleme numa cu ajutorul forumului. tampenie mare

Nu inteleg ce vrei sa spui. Oricum nu ai dreptate : jumatate din probleme reprezinta 8300 puncte. Si pana acuma sunt 20 oameni cu 8300.  :P
Btw tu nu ai vazut acm.timus.ru ?

PS: Imi place ca acest topic dedicat problemei tabela a devenit un fel de cafenea

Si chiar daca s-ar rezolva jumatate din probleme cum zice batzu... (ceea ce nu cred ca e adevarat) ... mai ramane jumatate de arhiva care si aia e ceva... plus ca cine e interesat... recurge la forum doar cand este adevarata nevoie... si se mai gandeste si el un pic.. si se invata multe asa.. parerea mea...

pai cam asta e ideea forum`ului.. sa se ofere sfaturi de rezolvare.. dar nu e cum zici tu

oricum, rezolva tu cealalta jumatate :P

ps: sorry ca sunt off

Oricum, de la mine incepuse vorbaria... chestia cu xor o stiam nu de pe forum, dar uitasem formula... am dat de problema, am incercat,  am luat 0 (era de asteptat...) am citit tot, iar am luat 0(moment de  ](*,) ) si pe urma m-am uitat in cartea unde vazusem formula prima data... si a mers :D
De ce sa nu folosim o rezolvare perfecta dar nedemonstrata? si nu ma refer pt ca sa luam puncte aici, pe infoarena, ci la concursuri la care participi... cum sa zic, fara sa fie pe net...

In Probleme neelementare tratate elementar, Iaglom Iaglom, apare solutia cu demonstratia de vreo 2 pagini, nu stiu daca e vreo demonstratie mai simpla si intuitiva, dupa ce am citit problema printr-a 11-a ma gandeam si eu sa o dau intr-un concurs ca e interesanta, dar e mai bine asa intr-o arhiva pt concursuri sunt potrivite problemele in care mai si implementezi ceva.

Imi explica si mie cineva va rog ce inseamna decrementare?
Decrementarea a doua numere?
Multumesc! :cry:

decrementare, adica scazi o unitate din valoarea variabilei (a--)

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.

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

oricum, poti sa o faci in timp logaritmic oricand.  :wink:

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.

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....... :D  8)

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

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   :thumbdown: )

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 ! ;)

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

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

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

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

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

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

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)

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

Imi da eroare in evaluator la problema asta  orice scriu :horsy:

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 [...]

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

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

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

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

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

Eu zic sa recitesti enuntul.

 :fighting: 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) :D bine .. cu niste calcule in plus adunari .. inmultiri si altele .... dar totusi e penal rau :(  :angry:  :angry:   ](*,)

Edit:
 :D miam dat seama ceam gresit :) da tot penal ramane programu :(  ](*,)  ](*,)

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

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"

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!

Va rog sa imi explice de ce functioneaza formula (l-1)^(c-1) la adresa [email protected]  :sad: