infoarena

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.

Merge cu back nerecursiv ...

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

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.

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

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:

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.

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

io am luat 100 asa ca puti incerca

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,  :wink:

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.

care manual??? :-s

Pentru n = 5 da

Tu cum ai reusit sa rezolvi problema fara sa trimiti sursa? Daca dau filtrare la monitor, nu apare nici o sursa, dar pe profilul tau apare problema drept rezolvata.  ???

Auzi iti bati joc de forumul asta? Nu vezi ca postul ala e deja de mult timp ? Nu apare sursa fiindca a fost pe InfoArena 1 si nu s-au mai pastrat sursele  :eyebrow:.

Auzi iti bati joc de forumul asta? Nu vezi ca postul ala e deja de mult timp ? Nu apare sursa fiindca a fost pe InfoArena 1 si nu s-au mai pastrat sursele  :eyebrow:.