004 Biti

[•fluffy]

Aici puteţi discuta despre problema Biti.

[•greco]

voi ce intelegeti prin "Program recieved signal SIGSEGV, Segmentation fault. 0x080485ba in bkt(k=318297 at biti.c:44"? io credeam ca eroarea SEGMENTATION FAULT apare cand incerci sa accesezi o zona de memorie nedeclarata, sau ceva de genu asta. Da acuma chiar am reverificat sursa si nu imi dau seama ce se intampla. Daca ar putea cineva sa se uite putin peste sursa mea si sa dea un diagnostic i-as fi foarte recunoscator. Spuneti si va dau un mail cu ea. Nu de alta, da chiar nu-mi dau seama  

[•eneamtiu]

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,  

[•malex]

eu nu am inteles din enunt ce trebuie sa fac? cineva poate sa imi explice mai clar ce trebuie sa gasesc?

[•bogdan2412]

Cum s-ar putea face problema asta fara backtracking?

[•Cosmin]

Cauta pe net despre secventa deBrujin si o sa gasesti ca problema se rezolva cu ajutorul algoritmului de determinare a unui lant eulerian.

[VladS]

Am citit intr-un text USACO:

Analysis: The vertices of the graph are the possibilities of N-1 cows. Being at a node corresponds to the last N-1 cows matching the node in color. That is, for N = 4, if the last 3 cows were wbw, then you are at the wbw node. Each node has out-degree of 2, corresponding to adding a black or white cow to the end of the sequence. In addition, each node has in-degree of 2, corresponding to whether the cow just before the last N-1 cows is black or white.

The graph is strongly connected, and the in-degree of each node equals its out-degree, so the graph has a Eulerian circuit.

The sequence corresponding to the Eulerian circuit is the sequence of N-1 cows of the first node in the circuit, followed by cows corresponding to the color of the edge.

Dar nu cred ca am inteles prea bine.
Deci pentru n=3 am nodurile "00", "01","10","11"? Si am muchie de la "00" la "00"?

P. S. : Daca veti considera ca acest mesaj nu respecta regulile forumului va rog sa-l stergeti.

[•LtRaven]

Nu ar merge problema mai bine daca ai afisa direct rezultatul!
Il generezi intr-un fisier auxiliar cu backtracking si copiezi rezultatele in fisierul sursa. Avand in vedere ca n<=20, ar trebui sa mearga.

[•druid]

Pt N=3 ai nodurile 000, 001, 010, 011, 100, 101, 110, 111. Ai muchile astea (graf orientat):

000 => 000, 001
001 => 010, 011
010 => 100, 101
011 => 110, 111
100 => 000, 001
101 => 010, 011
110 => 100, 101
111 => 110, 111

De aici ai un circuit, de ex: 110=>101=>010=>100=>000=>001=>011=>111

Si ca sa obtii sirul, iei N-1 biti din primul nod si ultimul din restul:
1101000111 (e solutie si daca il citesti invers).

[•bogdan2412]

Am reusit s-o fac in sfarsit. Pana la urma tot un fel de backtracking e, dar a fost nashpa ca nu mergea recursiv. Anyway, thanks

[•Cosmin]

Merge cu back nerecursiv ... dar ideea e de fapt gasirea unui ciclu euler in graful prezentat mai sus, daca vrei sa inveti ceva mai mult decat backtraking ar trebui sa incerci si a doua idee de rezolvare.

[•dany3dx]

Merge cu back nerecursiv ...

eu cu back (cu kmp) nu scot decat 65....  

[•calinux]

Eu pentru a determina un ciclu eulerian in graf foloseam o functie recursiva (poate nu cea mai buna metoda....) dar oricum.... imi lua doar 90 de pcte... Si ... am apelat la o idee mai neortodoxa si am transformat functia recursiva in functie iterativa cu niste goto-uri si am luat 100 de pcte.  Eram doar curios cum se poate face sa determini un ciclu eulerian fara o functie neaparat recursiva.

[•pirosl]

Cauta pe net despre secventa deBrujin si o sa gasesti ca problema se rezolva cu ajutorul algoritmului de determinare a unui lant eulerian.

Ai si un link? Eu am cautat pe net insa n-am gasit nimic

[•Cosmin]

Probabil motivul pentru care nu gasesti e ca am scris gresit ... e  deBruijn nu deBrujin cum am scris eu si daca vrei si un link uite aici: http://planetmath.org/encyclopedia/DeBruijnDigraph.html . Probabil o sa gasesti chestii mai bune daca vei cauta pe google.

[•pirosl]

Probabil motivul pentru care nu gasesti e ca am scris gresit ... e  deBruijn nu deBrujin cum am scris eu si daca vrei si un link uite aici: http://planetmath.org/encyclopedia/DeBruijnDigraph.html . Probabil o sa gasesti chestii mai bune daca vei cauta pe google.

Da....merci M-am prins ca era scris gresit dupa ce am postat . Anyway, site-urile pe care le-am gasit sunt mult prea expeditive....ma asteptam sa gasesc mai multe explicatii si argumente pt ceea ce zic ei . Thanks again

[•Cosmin]

Mie mi se pare destul de clara ideea si din linkul ce ti l-am dat eu ....

[•pirosl]

Mie mi se pare destul de clara ideea si din linkul ce ti l-am dat eu ....

Ai dreptate....thanks. Pacat ca nu merge problema recursiv . Anyway...nice to learn smth new. 10x

[cristi8]

si eu am facut tot cu back nerecursiv..
 cum se determina lantul eulerian ?

[•Cosmin]

Uite ce scrie pe usaco training gate:

The Algorithm
Detecting whether a graph has an Eulerian tour or circuit is actually easy; two different rules apply.

A graph has an Eulerian circuit if and only if it is connected (once you throw out all nodes of degree 0) and every node has `even degree'.
A graph has an Eulerian path if and only if it is connected and every node except two has even degree.
In the second case, one of the two nodes which has odd degree must be the start node, while the other is the end node.
The basic idea of the algorithm is to start at some node the graph and determine a circuit back to that same node. Now, as the circuit is added (in reverse order, as it turns out), the algorithm ensures that all the edges of all the nodes along that path have been used. If there is some node along that path which has an edge that has not been used, then the algorithm finds a circuit starting at that node which uses that edge and splices this new circuit into the current one. This continues until all the edges of every node in the original circuit have been used, which, since the graph is connected, implies that all the edges have been used, so the resulting circuit is Eulerian.

More formally, to determine a Eulerian circuit of a graph which has one, pick a starting node and recurse on it. At each recursive step:

Pick a starting node and recurse on that node. At each step:
If the node has no neighbors, then append the node to the circuit and return
If the node has a neighbor, then make a list of the neighbors and process them (which includes deleting them from the list of nodes on which to work) until the node has no more neighbors
To process a node, delete the edge between the current node and its neighbor, recurse on the neighbor, and postpend the current node to the circuit.
And here's the pseudocode:

Cod:

# circuit is a global array
   find_euler_circuit
     circuitpos = 0
     find_circuit(node 1)

# nextnode and visited is a local array
# the path will be found in reverse order
  find_circuit(node i)

    if node i has no neighbors then
      circuit(circuitpos) = node i
      circuitpos = circuitpos + 1
    else
      while (node i has neighbors)
          pick a random neighbor node j of node i
          delete_edges (node j, node i)
          find_circuit (node j)
      circuit(circuitpos) = node i
      circuitpos = circuitpos + 1

To find an Eulerian tour, simply find one of the nodes which has odd degree and call find_circuit with it.

Both of these algorithms run in O(m + n) time, where m is the number of edges and n is the number of nodes, if you store the graph in adjacency list form. With larger graphs, there's a danger of overflowing the run-time stack, so you might have to use your own stack.

[cristi8]

mersi mult

[•pirosl]

Tocmai...algoritmul pt determinarea lantului eulerian e recursiv....insa din pacate pt problema biti nu prea merge pt ca da stiva peste cap.... (Sau cel mai corect spus....eu nu am reusit sa fac algoritmul pt determinarea lantului eulerian recursiv). Si am recurs la metode total neortodoxe (gen goto ). Anyway 10x pt o gramada de lucruri noi invatate din aceasta problema. Si inca o data thanks Cosmin pt hinturi

[•Cosmin]

Pentru a nu il face recursiv poti folosi un vector in loc de stiva ... asa cum poti face dfs iterativ, poti face si ciclu eulerian iterativ. Backtraknigu nu il faci de obicei recursiv si cand ai nevoie de stiva mai mare iterativ??? Astea nu sunt trucuri sunt metode de implementare ale aceluiasi algoritm ... ce ai facut cu goto-uri probabil ca e mai dubios da asta nu inseamna ca nu exista metoda eleganta iterativa care face acelasi lucru.

[•Stilgar]

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

[VladS]

Pai asta e implementarea iterativa a circuitului eulerian.