004 Biti

[•lucibit]

Deci, am facut circuit eulerian, frumos, ar trebuii sa imi merarga..numai ca iau doar 10 puncte...nu ma prind. Sgiur e ceva cu ordinea lexicografica, ca  de ex la N=4 NU imi iese ca la exemplul ala din linkul postat(cu de Burjin), chit ca e corect rapsunsul, numai ca deh, nu e ordinea lexicografica ca la ala. Am facut ciclul de mana si imi da bine cum imi da mie, nu inteleg de ce nu e asa.

Cand selectezi nodurile , selectezi mai intai muchia ce se termina in 1 si a doua oara pe cea care se termina in 0. Daca faci invers se blocheaza algoritmul pt ca nu contruieste ciclul bine. Daca va uitati la circuitul pe care il  da ca exemplu in link o tot ia pe 1,la inceput , cum am zis..si la un moment dat are de ales intre 1 si 0 si o ia pe 0 prima oara. not fair
Ma ajuta cineva?

[tmac]

caut un ciclu eulerian pe un graf format din elementele de lungime n-1 (0 ... 2^(n-1)) in care fiecare nod i are muchie la (2*i) % 2^(n-1) si la (2*i+1) % 2^(n-1). si apoi cum fac sa dau de sirul ala minim ?? cam incercat toate posibilitatile ... ?

[•alexthero]

Citeste postul lui Stilgar de mai sus.. te poate ajuta

[•Viksen]

Am vazut k evaluarea se face pe 20 de teste (f. probabil pt. toate cele 20 de valori ale lui n). Am rezolvat problema, iar mie, acasa , pt. testele cu n=(1, 2, 3, 4) imi da corect (cel putin pt. aceste teste.. tind sa cred k shi celelalte raspunsuri sunt tot corecte  ). Oricum, iau doar 5 p. Nu primesc TLE, ci WA (timpul maxim e de 0.14 s/ test).

  Va rog, daca se poate, sa imi dati un exemplu de output corect pt n intre 4 shi 6 k sa ma asigur k am facut bine... Chiar nu inteleg unde pot sa greshesc. Am tinut cont shi de prioritatea lexicografica.

[•Adriana_S]

Pentru n = 5 da

Cod:

36
000001000110010100111010110111110000

[•Viksen]

Iti multumesc mult! Cred k am o greseala pe undeva.Raspunsul meu nu era minim lexicografic after all.. 

[•points_hunter]

Am rezolvat problema cu ciclu eulerian dar nu stiu cum ati facut-o voi cu back iterativ. Datorita dimensiunilor mari mi se pare aproape imposibil. Ce puneti pe un nivel???

[•Viksen]

nu shtiu cum faci U parcurgerea, dar dak porneshti sa spunem din 000 pt. n=3 ar trebui sa treci prin drumul:
000>001>010>101>011>111>110>100
cum fiecare nod din graph are exact 2 fii, poti retine ushor in care din ei te-ai dus la un moment dat, codificand fiul mai mic al unui nod cu 0 shi pe celalalt cu 1. pt. ex de mai sus ai avea:
(radacina : 000)>1>0>1>1>1>0>0
dak il citeshti asha, vei vedea k e raspunsul corect . Oricum, secventa se genereaza back, in maxim 2^n (2^20 ~ 1 000 000). Pornind cu radacina in 0..000 (sau maxim in 0..001) vei avea minim lexicografic.

______________
Rog moderatorii Infoarena sa stearga acest post daca nu corespunde cerintelor forumului

[•Coty]

ma scuzati ca intervin dupa atata timp... dar ce vrea problema asta sa facem nu este un ciclu hamiltonian? ala stiu eu ca cere sa trecem prin toate nodurile si nu prin toate muchiile (ca in problema, daca trecem prin toate muchiile, o sa avem o lungime mult mai mare)
si determinarea unui ciclu hamiltonian nu are complexitate exponentiala (adica... nu e back ? ? ? ) eu asa stiam, desi e probabil sa gresesc

[•Viksen]

shi eu ce spuneam???!!! E back! E back!    ^

[•Cosmin]

Ati citit tot threadul?? Se poate face cu algoritm polinomial de gasire a unui ciclu eulerian!!!!!!!!!! Se poate face si cu back, dar nu e o problema NP! Deci cum spuneam NU e back! NU e back!

[•Coty]

am citit tot threadul de 10 ori... si d-aia zic.  Am gasit niste definitii:

  Ciclu eulerian = ciclu simplu care contine toate muchiile unui graf
  Ciclu hamiltonoan = ciclu elementar care contine toate nodurile unui graf

la asta ma refer... s-o fi facand si fara back, nu zic... dar daca facem un ciclu eulerian o sa avem toate muchiile => or sa fie unele noduri de mai multe ori => secventa nu mai e minima... nu?

[u-92]

Nu ai inteles... atribui fiecarei muchii un cod si din cauza asta iti trebuie toate muchiile

[blasters]

Hmmm......... ciudat........ eu am luat 100 d puncte cu un backtracking recursiv ( am folosit operatii p biti) dar totushi local pentru testele cu n=19 shi 20 primesc segmentation fault....

[•sir_icemaster]

Am vazut niste idei de rez a problemei de am cazut in cur da io zic ca cel mai usor s-ar face cum am facut-o io  !!! cine nu vrea sa stie rezolvarea sa nu citeasca mai departe!!!!



Se face cu un algoritm arhicunoscut:greedy daca stim ca trebuie sa fie prima din punct de vedere lexicografic atunci punem tot timpu 0 si numa daca nu se poate(un sir de booleane ne spune daca o fost luat nr sau nu) atunci punem 1 si nu mai veificam nimic(ceea ce reduce marimea sirului la jumatate).Mai trebuie facuta o precizare imp.:la inceput se pun n de 0 si la sf n-1 de 0 si atunce cand pornim greedyu toate nr de forma 10000, 1100 ,1110 se iau ca si cum ar fi folosite si dupa ce se termina greedy punem zerourile ca sa apara si ele.
prin metoda asta nu ne trebuie decat un singur sir 500.000 de booleane care daca chiar vreau se poate trece in lucru pe biti si si face mult mai mic da neeee !

io am luat 100 asa ca puti incerca

Nu se poate spune ca e greedy, considera urmatorul contraexemplu: sa zicem ca la pasul k se poate pune si 0 si 1. Alegem 0, facem un nr n  de pasi inainte si ne blocam (pentru ca 0 a fost alegerea gresita). Acum trebuie sa facem n pasi inapoi si sa punem 1. Dar greedy nu face intoarceri, ci contruieste solutia progresiv alegand optiunea care pare cea mai buna la un moment dat.
Probabil ca ai folosit backtracking nerecursiv si nu ti-ai dat seama.

[•codrin]

fara sa cunosc notiunea de graf..nu voi putea rezolva problema?

[•wefgef]

Ba da, merge cu backtracking .

[•gggbbbyyy]

Asa la intuitie: dupa cate vad incerci sa folosesti backtracking (recursiv?).

Noah, dupa anumit numar de apeluri recursive (cica k=318297?) stiva se umple (ca n-are decat 1 mega) si noul apel recursiv incearca sa se aloce in continuare cum ar veni, ocupand o zona de memorie care nu este a lui.

Si de acolo SEGMENTATION FAULT.

Parerea mea,  

[•O_Neal]

o mica rugaminte .. niste exemple .. mai precis pt 5 de ex cat trebuie sa deie? nu inteleg ce am putut face de imi merge numa pt < 4 

[•gabitzish1]

pt 5:

Cod:

36
000001000110010100111010110111110000

pt 6:

Cod:

69
000000100001100010100011100100101100110100111101010111011011111100000

[•SilverMoon]

Cred ca e o diferenta enorma intre compilatorul de aici si al meu de acasa. Aici iau 100% punctaj, cu 0.5 sec pentrul ultimul test, iar pe calcu meu scot vreo ~2 sec la el, si e core2duo la 3ghz cu 4gb ram . In fine, problema am rezolvat-o cu un backtracking iterativ optimizat la greu, nu e nevoie sa retii niciunde un graf, deoarece fiecare nod are 2 arce care ies din el si 2 care intra in el (unele noduri au chiar un arc catre ele insele). Este un graf orientat si fiecare arc poate fi gasit printr-o formula in O(1), cu alte cuvinte stim daca intre nodurile N si M exista arc in O(1), de aceea stim care este graful fara sa il retinem. Trebuie gasit un ciclu care trece prin toate nodurile o singura data, si incepe cu cel mai mic nod. Primul ciclu gasit este cel cerut. Astfel, programul se termina dupa ce s-a gasit primul ciclu. Numarul de cifre ale solutiei se calculeaza printr-o formula, deci tot in O(1). Bafta si celor care nu au rezolvat problema asta!

Apropos,

NU este ciclu eulerian!!!! Este un simplu drum care contine toate nodurile grafului si incepe cu cel mai mic posibil. Nu conteaza unde se termina si NU trebuie sa contina toate arcele.

Editat de moderator: Nu posta consecutiv pe aceeasi tema! Modifica mesajele anterioare!

[•pauldb]

Ma bucur ca esti entuziast ca ti-a iesit problema, dar lasa-i si pe altii sa gandeasca pentru ei.

[•wefgef]

Apropos,

NU este ciclu eulerian!!!! Este un simplu drum care contine toate nodurile grafului si incepe cu cel mai mic posibil. Nu conteaza unde se termina si NU trebuie sa contina toate arcele.

Vlad, intamplator aceasta problema chiar este ciclu eulerian. Doar pentru ca tu nu ai fost in stare sa gasesti graful corect, nu inseamna ca el nu exista .

[•SilverMoon]

Ok, poate nu m-am exprimat suficient de bine. Vroiam sa exprim faptul ca am gasit o rezolvare mai simpla (dupa parerea mea). De ce trebuie sa gasesti graful? De ce trebuie sa gasesti ciclu eulerian? Cand graful il stii deja in O(1), adica stii orice "parte" din el printr-o singura formula, deci nu mai trebuie retinut, nu mai trebuie alocata matrice de 2^n * 2^n (sau liste liniare simplu inlantuite, cum facusem eu pana sa-mi dau seama ca nu trebuie). De ce trebuie ciclu eulerian cand un backtracking simplu (dar mai optimizat) rezolva totul? Este o regula ca trebuie gasit graful si apoi ciclul eulerian? Nu. Problema o poti rezolva in orice fel, atat timp cat raspunsul este corect. Eu am gasit o solutie ce scoate 0.5 s pentru ultimul test. Si am plecat de la un singur post de mai sus, care este defapt exemplul n=3 al lui Voicu Octavian. Nu consideri ca probleme astea le rezolvi si ca sa-ti largesti orizontul gandirii, originalitatea? Daca tot ce faci este sa citesti posturile si sa te iei dupa ele, practic tu nu ai "evoluat" decat pe plan teoretic, pentru ca acum stii de deBruijn, de graful lui si eventual de ciclu eulerian, daca nu stiai deja. Si da, initial am citit ca e ceva cu ciclu eulerian, dar inainte de a asterne pe ecran algoritmul pentru gasirea lui, am stat si m-am gandit, am scris pe foaie solutia si am vazut ca nu e ciclu eulerian pentru ca nu trece prin toate arcele. Daca fiecare nod are 2 arce de iesire si 2 de intrare, un ciclu eulerian ar trece prin fiecare nod de 2 ori, adica am avea o secventa 010100101xxxxx...xxx de 2 ori in solutia finala, ceea ce ar duce la lungirea solutiei, si deci nu la cea mai scurta solutie.

Cu alte cuvinte, te complici cu graful si ciclul eulerian, consumi memorie si timp de computatie.

[•wefgef]

Hai sa o lasam balta.