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 » Fri Jun 10, 2005 5:37 pm

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 » Fri Jun 10, 2005 6:07 pm

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 » Fri Jun 10, 2005 6:45 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

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Sat Jun 11, 2005 9:54 am

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 » Mon Jul 11, 2005 5:03 am

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 » Sat Jul 30, 2005 10:07 am

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 :)

User avatar
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 » Mon Oct 17, 2005 7:50 pm

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 » Sat Dec 02, 2006 6:15 am

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 » Fri Jun 08, 2007 5:21 pm

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 » Sat Jun 09, 2007 12:36 am

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 » Mon Jun 11, 2007 4:11 pm

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 » Mon Jun 11, 2007 7:49 pm

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 » Thu Jun 14, 2007 11:17 pm

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 » Mon Jun 25, 2007 9:05 pm

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 » Mon Jun 25, 2007 9:11 pm

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)”