10054 - The Necklace

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

GeorgeBusch
New poster
Posts: 10
Joined: Fri Jun 10, 2005 5:30 pm

Post by GeorgeBusch »

Hello Eduard, this is my first post in board, so you should be very proud, that it trys to help you :wink:

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
New poster
Posts: 8
Joined: Thu May 20, 2004 1:30 pm
Location: China

Post by 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
New poster
Posts: 10
Joined: Fri Jun 10, 2005 5:30 pm

Post by 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
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by 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
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

wanderley2k
New poster
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm

Post by 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
New poster
Posts: 16
Joined: Mon Dec 01, 2003 1:20 am
Contact:

Post by drewsome »

Julien Cornebise wrote:Hi Deneb

I had much troubles with this part, and that's what makes my code so ugly and so slow :oops:
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
New poster
Posts: 21
Joined: Sat Sep 25, 2004 3:35 am
Location: Oaxaca de Ju
Contact:

Test case.

Post by Ndiyaa ndako »

One test case that might be useful:

1
4
1 1
1 2
1 2
2 2

I hope it helps.

indyman
New poster
Posts: 7
Joined: Thu Nov 30, 2006 12:36 pm

Post by 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
New poster
Posts: 35
Joined: Wed May 02, 2007 11:48 pm
Location: Brasil

I donts understand how the output can be printed...

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: I donts understand how the output can be printed...

Post by Jan »

adelar wrote:"There may be many solutions, any one of which is acceptable" meaning that the output can be started on any edge...??
Yes.
Ami ekhono shopno dekhi...
HomePage

adelar
New poster
Posts: 35
Joined: Wed May 02, 2007 11:48 pm
Location: Brasil

test case above

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

My accepted code returns...

Output:

Code: Select all

Case #1
1 1
1 2
2 2
2 1
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

adelar
New poster
Posts: 35
Joined: Wed May 02, 2007 11:48 pm
Location: Brasil

INPUTS

Post by 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
New poster
Posts: 35
Joined: Wed May 02, 2007 11:48 pm
Location: Brasil

out

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Your output is correct. This problem has a special corrector. So, different but correct answers should be accepted.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 100 (10000-10099)”