10054  The Necklace
Moderator: Board moderators

 New poster
 Posts: 10
 Joined: Fri Jun 10, 2005 5:30 pm
Hello Eduard, this is my first post in board, so you should be very proud, that it trys to help you
i think there is a bug in your prog, the array cv, which stores the eularian circle can become as long as 1000, because you visit one node for every edge. So hence there are 1000 edges you can visit up to 1000 nodes on your way.
i think there is a bug in your prog, the array cv, which stores the eularian circle can become as long as 1000, because you visit one node for every edge. So hence there are 1000 edges you can visit up to 1000 nodes on your way.

 New poster
 Posts: 10
 Joined: Fri Jun 10, 2005 5:30 pm
and that is right too, especially by better your runtime complexity you can even shorten your program. when you just test if all nodes have odd degree and after that do your solve procedure this is enough. you just have to check weather all edges have been used to create the circle. if not all edges used then the graph wasnt connected...
yeah i tested it now, i got your code acc just leting procedure floyd away and do what i sayed
yeah i tested it now, i got your code acc just leting procedure floyd away and do what i sayed
Thanks everybody.Now I got AC.Yes The Bug was on My Cv array length.
I cut my code too.
Thanks once again.
Eduard
I cut my code too.
Thanks once again.
Eduard
someone who like to solve informatic problems.
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650

 New poster
 Posts: 28
 Joined: Mon Mar 01, 2004 11:29 pm
Hi,
I tried to solve this problem but I got WA only.
My program:
* Calc one euler cicle C
* For all vertex not in C, calc euler cicle c and union with C
This is my code:
Thanks.
I tried to solve this problem but I got WA only.
My program:
* Calc one euler cicle C
* For all vertex not in C, calc euler cicle c and union with C
This is my code:
Code: Select all
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
using namespace std;
#define V(c) vector <c>
#define ALL(c) (c).begin(),(c).end()
#define FOR(i,v,n) for(int i=v,_n=n;i<_n;++i)
#define FORD(i,v,n) for(int i=(n1),_v=v;i>=_v;i)
#define REP(i,n) FOR(i,0,n)
#define REPD(i,n) FORD(i,0,n)
#define FOREACH(it,c) for(typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define sz(c) (c).size()
int G[51][51],grau[51],usado[51],vis[51];
void calc(vector<pair<int,int> >& res, int i) {
REP(j,50) if (G[i][j]>0) {
G[i][j];
G[j][i];
vis[i]=vis[j]=1;
res.push_back(make_pair(i+1,j+1));
calc(res,j);
break;
}
}
int main( int argc, char* argv[] ) {
int ncasos, caso=1;
cin>>ncasos;
while(ncasos) {
int N;
cin>>N;
// limpando
memset(G,0,sizeof(G));
memset(grau,0,sizeof(grau));
memset(usado,0,sizeof(usado));
memset(vis,0,sizeof(vis));
// lendo
REP(i,N) {
int u,v;
cin>>u>>v;
u; v;
G[u][v]++;
G[v][u]++;
grau[u]++;
grau[v]++;
usado[u]=1;
usado[v]=1;
}
vector<pair<int,int> > res;
cout<<"Case #"<<caso++<<endl;
REP(i,51) if (grau[i]>0) {
calc(res, i);
break;
}
bool flag=true;
REP(i,51) REP(j,51) if (flag && G[i][j]>0) {
vector<pair<int,int> > novo;
calc(novo, i);
bool flag2=false;
REP(r,sz(res)) {
if (res[r].second == novo.front().first &&
res[(r+1)%sz(res)].first == novo.back().second) {
vector<pair<int,int> > novoRes;
REP(i,r+1)
novoRes.push_back(res[i]);
REP(i,sz(novo))
novoRes.push_back(novo[i]);
FOR(i,r+1,sz(res))
novoRes.push_back(res[i]);
res=novoRes;
flag2=true;
break;
}
}
if (!flag2) {
flag=false;
break;
}
}
if (!flag  sz(res)<N  res.back().second != res.front().first) {
cout<<"some beads may be lost"<<endl<<endl;
continue;
}
REP(i,sz(res)) {
cout<<res[i].first<<" "<<res[i].second<<endl;
}
cout<<endl;
}
return 0;
}
Yes I know a better way that uses a linked list and adjacency matrix to get O(n) running time. I do not take credit for the following code, it was not written by meJulien Cornebise wrote:Hi Deneb
I had much troubles with this part, and that's what makes my code so ugly and so slow
The algorithm is as follows :I hope this pseudo code is clear enough and not too much wrong (I've got the brain bottomup because of christmas parties AND working my final exams wich are in two weeks ).Code: Select all
/* I don't mention global variables used to mark the cycles and to store the eulerian cycle */ /* direct_cycle is the direct cycle you're processing */ construct_eulerian_cycle(direct_cycle) { Mark this cycle; For each vertex in the cycle { Add the vertex to the eulerian cycle: For all nonmarked cycles C containing this vertex { construct_eulerian_cycle(C); } }
I confess it's horribly slow and ugly, so if anybody has another algo, please tell !
Code: Select all
list< int > cyc;
void euler( list< int >::iterator i, int u ) {
for( int v = 0; v < n; v++ ) if( graph[u][v] ) {
graph[u][v] = graph[v][u] = false;
euler( cyc.insert( i, u ), v );
}
}
int main() {
// read graph into graph[][] and set n to the number of vertices
euler( cyc.begin(), 0 );
// cyc contains an euler cycle starting at 0
}
Enjoy
 Ndiyaa ndako
 New poster
 Posts: 21
 Joined: Sat Sep 25, 2004 3:35 am
 Location: Oaxaca de Ju
 Contact:
Test case.
One test case that might be useful:
1
4
1 1
1 2
1 2
2 2
I hope it helps.
1
4
1 1
1 2
1 2
2 2
I hope it helps.
I donts understand how the output can be printed...
hi,,,
"There may be many solutions, any one of which is acceptable" meaning that the output can be started on any edge...??
that's in advance...
"There may be many solutions, any one of which is acceptable" meaning that the output can be started on any edge...??
that's in advance...
Re: I donts understand how the output can be printed...
Yes.adelar wrote:"There may be many solutions, any one of which is acceptable" meaning that the output can be started on any edge...??
Ami ekhono shopno dekhi...
HomePage
HomePage
test case above
hi,
to input above
1 4 1 1 1 2 1 2 2 2
my algorithm have output:
1 1
1 2
2 2
which is the correct output?
thanks.
to input above
1 4 1 1 1 2 1 2 2 2
my algorithm have output:
1 1
1 2
2 2
which is the correct output?
thanks.
Ami ekhono shopno dekhi...
HomePage
HomePage
out
Hi,
which is the output to this input:
my code output to this case:
thanks in advance...
which is the output to this input:
Code: Select all
2
6
1 3
1 2
2 3
3 4
3 5
4 5
6
1 2
1 3
2 3
3 4
4 5
3 5
Code: Select all
Case #1
5 3
3 1
1 2
2 3
3 4
4 5
Case #2
5 3
3 1
1 2
2 3
3 4
4 5
Your output is correct. This problem has a special corrector. So, different but correct answers should be accepted.
Ami ekhono shopno dekhi...
HomePage
HomePage