•fluffy
|
|
« : Martie 08, 2004, 19:54:18 » |
|
Aici puteţi discuta despre problema Biti.
|
|
|
Memorat
|
|
|
|
•greco
|
|
« Răspunde #1 : Aprilie 08, 2004, 23:42:31 » |
|
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
|
|
|
Memorat
|
Jump in the cockpit and start up the engines Remove all the wheelblocks there's no time to waste Gathering speed as we head down the runway Gotta get airborne before it's too late.
|
|
|
•eneamtiu
Strain
Karma: 3
Deconectat
Mesaje: 7
|
|
« Răspunde #2 : Noiembrie 18, 2004, 18:34:38 » |
|
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,
|
|
|
Memorat
|
|
|
|
•malex
Client obisnuit
Karma: 6
Deconectat
Mesaje: 53
|
|
« Răspunde #3 : Noiembrie 20, 2004, 13:33:24 » |
|
eu nu am inteles din enunt ce trebuie sa fac? cineva poate sa imi explice mai clar ce trebuie sa gasesc?
|
|
|
Memorat
|
Programarea e frumoasa daca o inveti logic..
|
|
|
•bogdan2412
|
|
« Răspunde #4 : Februarie 26, 2005, 09:53:59 » |
|
Cum s-ar putea face problema asta fara backtracking?
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #5 : Februarie 26, 2005, 15:24:09 » |
|
Cauta pe net despre secventa deBrujin si o sa gasesti ca problema se rezolva cu ajutorul algoritmului de determinare a unui lant eulerian.
|
|
|
Memorat
|
|
|
|
VladS
Vizitator
|
|
« Răspunde #6 : Februarie 27, 2005, 20:52:39 » |
|
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.
|
|
|
Memorat
|
|
|
|
•LtRaven
Strain
Karma: 1
Deconectat
Mesaje: 2
|
|
« Răspunde #7 : Martie 12, 2005, 00:33:33 » |
|
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.
|
|
|
Memorat
|
|
|
|
•druid
Strain
Karma: 1
Deconectat
Mesaje: 27
|
|
« Răspunde #8 : Martie 12, 2005, 00:59:23 » |
|
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).
|
|
|
Memorat
|
|
|
|
•bogdan2412
|
|
« Răspunde #9 : Martie 12, 2005, 11:34:56 » |
|
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
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #10 : Martie 12, 2005, 16:13:42 » |
|
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.
|
|
|
Memorat
|
|
|
|
•dany3dx
Strain
Karma: 0
Deconectat
Mesaje: 14
|
|
« Răspunde #11 : Aprilie 12, 2005, 23:00:53 » |
|
Merge cu back nerecursiv ... eu cu back (cu kmp) nu scot decat 65....
|
|
|
Memorat
|
|
|
|
•calinux
Strain
Karma: 5
Deconectat
Mesaje: 42
|
|
« Răspunde #12 : Aprilie 13, 2005, 20:47:18 » |
|
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.
|
|
|
Memorat
|
"And all that is now, And all that is gone, And all that's to come, And everything under the sun is in tune But the sun is eclipsed by the moon" The Dark Side of The Moon - Pink Floyd
|
|
|
•pirosl
Strain
Karma: -2
Deconectat
Mesaje: 34
|
|
« Răspunde #13 : Mai 19, 2005, 12:53:35 » |
|
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
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #14 : Mai 19, 2005, 18:18:04 » |
|
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.
|
|
|
Memorat
|
|
|
|
•pirosl
Strain
Karma: -2
Deconectat
Mesaje: 34
|
|
« Răspunde #15 : Mai 20, 2005, 12:27:38 » |
|
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
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #16 : Mai 20, 2005, 13:13:16 » |
|
Mie mi se pare destul de clara ideea si din linkul ce ti l-am dat eu ....
|
|
|
Memorat
|
|
|
|
•pirosl
Strain
Karma: -2
Deconectat
Mesaje: 34
|
|
« Răspunde #17 : Mai 27, 2005, 10:25:48 » |
|
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
|
|
|
Memorat
|
|
|
|
cristi8
Vizitator
|
|
« Răspunde #18 : Mai 27, 2005, 16:25:16 » |
|
si eu am facut tot cu back nerecursiv.. cum se determina lantul eulerian ?
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #19 : Mai 27, 2005, 17:49:31 » |
|
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: # 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.
|
|
|
Memorat
|
|
|
|
cristi8
Vizitator
|
|
« Răspunde #20 : Mai 27, 2005, 21:20:26 » |
|
mersi mult
|
|
|
Memorat
|
|
|
|
•pirosl
Strain
Karma: -2
Deconectat
Mesaje: 34
|
|
« Răspunde #21 : Mai 30, 2005, 09:58:59 » |
|
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
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #22 : Mai 30, 2005, 11:26:48 » |
|
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.
|
|
|
Memorat
|
|
|
|
•Stilgar
Strain
Karma: -2
Deconectat
Mesaje: 18
|
|
« Răspunde #23 : August 01, 2005, 13:26:04 » |
|
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
|
|
|
Memorat
|
|
|
|
VladS
Vizitator
|
|
« Răspunde #24 : August 01, 2005, 13:44:39 » |
|
Pai asta e implementarea iterativa a circuitului eulerian.
|
|
|
Memorat
|
|
|
|
|