10054 - The Necklace

[GeorgeBusch]

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.

[liux0229]

He is right. Your cv should have size 1001
By the way, when I submit your code, it gets TLE
And I see no point to use Floyd. You can solve the problem in O(E) time

[GeorgeBusch]

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

[Eduard]

Thanks everybody.Now I got AC.Yes The Bug was on My Cv array length.
I cut my code too.
Thanks once again.
Eduard

[wanderley2k]

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:

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=(n-1),_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;
}

Thanks.

[drewsome]

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 :

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 non-marked cycles C containing this vertex {
           construct_eulerian_cycle(C);
     }
}

I hope this pseudo code is clear enough and not too much wrong (I've got the brain bottom-up because of christmas parties AND working my final exams wich are in two weeks ).

I confess it's horribly slow and ugly, so if anybody has another algo, please tell !

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 me

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]

One test case that might be useful:

1
4
1 1
1 2
1 2
2 2

I hope it helps.

[indyman]

Another test case that could help debug WA is:
1
9
2 4
1 1
1 2
1 2
2 2
3 3
4 4
3 2
4 3

Hope it helps all!

[adelar]

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...

[Jan]

"There may be many solutions, any one of which is acceptable" meaning that the output can be started on any edge...??

Yes.

[adelar]

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.

[Jan]

My accepted code returns...

Output:

Code: Select all

Case #1
1 1
1 2
2 2
2 1

Hope it helps.

[adelar]

Hi,
someone have other input case... to all input test that I have my code output correct answer... but have WA in 5.115 s ...
thanks in advance..

[adelar]

Hi,
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

my code output to this case:

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

thanks in advance...

[Jan]

Your output is correct. This problem has a special corrector. So, different but correct answers should be accepted.