10054 - The Necklace

[adelar]

Hi friends,,,
Can someone to see my code?
I take 27 WA Last with 6.133 seconds

Code: Select all

AC

what is the error? Can you help me?
thanks in advance...

[leocm]

I want some case tests.

For all the tests here and in other topics of this problem, my code get the correct answer.

Thank you!

[adelar]

Hi leocm,
I trying solve this problem too. I did test 4 codes and none take AC... but all algorithms is equals...
1. even?
2. conected?
3. euler and print.
thanks in advance...

[adelar]

Hi Jan,
If I send my code you analyse to me?
is some detail that I don't treat... but I don't know what!
thanks in advance.. .......

[Jan]

You should explain your algorithm first.

[adelar]

Hi Jan,
I take AC finally!!!!!! after 31 submitions!!!!!!
I was translating the coments to english to post for you and I saw the error... one of variables of control was with same value all time,,,
thank you, thanks a lot for the help...

then the sequence:
1. even?
2. conected?
3. euler and print.
work to this problem

next problem

[duykhang91]

Here is my pascal code. I hav WAs. Why? Please anyone can help me? Thanks a lot :X

Program Necklace;
Const
fi='10054.inp';
fo='10054.out';
Type arr=array[1..50,1..50] of integer;
Var
a:arr;
t,n,m:integer;
f:text;
{--------------------------------------------------------------------------}
Procedure euler;
var
b:array[1..51] of integer;
kt:boolean;
{-----------------------}
Procedure print;
var
i:integer;
begin
For i:=1 to n do
writeln(b,' ',b[i+1]);
end;
{-----------------------}
Procedure dw(i,d:integer);
var
j:integer;
begin
b[d]:=i;
If d=n+1 then
begin
print;
kt:=true;
end
else
begin
For j:=1 to m do
If a[i,j]=1 then
begin
a[i,j]:=0;
a[j,i]:=0;
dw(j,d+1);
If kt then exit;
a[i,j]:=1;
a[j,i]:=1;
end;
end;
end;
begin
kt:=false;
dw(1,1);
end;
{--------------------------------------------------------------------------}
Function even:boolean;
var
i,j,dem:integer;
begin
bac:=true;
For i:=1 to m do
begin
dem:=0;
For j:=1 to m do
If (a[i,j]=1) and (j<>i) then inc(dem);
If dem mod 2 <>0 then
begin
even:=false;
break;
end;
end;
end;
{--------------------------------------------------------------------------}
Function connect:boolean;
var
b:array[1..50] of boolean;
i:integer;
Procedure go(i:integer);
var
j:integer;
begin
b:=false;
For j:=1 to m do
If b[j] and (a[i,j]=1) then
begin
a[i,j]:=0;
go(j);
a[i,j]:=1;
end;
end;
begin
connect:=true;
fillchar(b,m,true);
go(1);
For i:=1 to m do
If b then
begin
connect:=false;
break;
end;
end;
{--------------------------------------------------------------------------}
Procedure nhap;
var
i,j,x,y:integer;
begin
Readln(t);
For i:=1 to t do
begin
writeln('Case #',t);
fillchar(a,sizeof(a),0);
m:=0;
readln(n);
For j:=1 to n do
begin
readln(x,y);
If x>m then m:=x;
If y>m then m:=y;
a[x,y]:=1;
a[y,x]:=1;
end;
If even and connect then
euler
else writeln('some beads may be lost');
If i<>t then writeln;
end;
end;
{--------------------------------------------------------------------------}
Begin
nhap;
End.

[sapnil]

I get too many WR,more than 15 times.whats wrong help me.........

Code: Select all

Remove after Acc

Thanks
Keep posting
Sapnil

[puneetm84]

Hi,

My code is giving time limit exceeded.I am first checking if euler cycle exists or not and then I find the euler cycle. Here is the code, can anyone help me with this ..Thanks in advance

#include<iostream>
#include<vector>
#include<string>
#include<list>
#include<set>

using namespace std;

void euler_cycle(list<int>euler,int **graph,list<int>::iterator i,int s)
{
for(int j=0;j<51;j++)
{
if(graph[s][j]>0)
{
graph[s][j]--;
graph[j][s]--;
list<int>::iterator it = euler.insert(i,s);
euler_cycle(euler,graph,it,j);
}
}


}

void dfs(int **graph,int color[51],int s)
{
color[s]=1;
for(int i=0;i<51;i++)
{
if(graph[s] && !color)
dfs(graph,color,i);

}
color[s]=2;
}



int main()
{
int N;
cin>>N;
int **graph;
graph = new int*[51];
for(int j=0;j<51;j++)
graph[j]=new int[51];

for(int i=0;i<N;i++)
{
list<int> euler;
int beads;
cin>>beads;
int s;

for(int j=0;j<51;j++)
for(int k=0;k<51;k++)
graph[j][k]=0;

set<int> nodes;
for(int j=0;j<beads;j++)
{
int x,y;
s=x;
cin>>x>>y;
graph[x][y]++;
graph[y][x]++;
nodes.insert(x);
nodes.insert(y);

}
// Check for connectivity
int flag=0;
int color[51];
for(int j=0;j<51;j++)
color[j]=0;

dfs(graph,color,s);

for(set<int>::iterator it=nodes.begin();it!=nodes.end();it++)
{
if(!color[*it])
{
flag=1;
break;
}
}

// Check for degree
for(int j=0;j<51;j++)
{
int degree=0;
for(int k=0;k<51;k++)
{
if(graph[j][k] && j!=k)
degree+=graph[j][k];
}

if(degree%2)
{
flag=1;
break;
}
}

cout<<"Case #"<<i+1<<endl;
if(flag)
cout<<"some beads may be lost";
else
{
euler_cycle(euler,graph,euler.begin(),1);
int ans[euler.size()];
int count=0;
list<int>::iterator it;
for(it = euler.begin(); it != euler.end() ; it++)
ans[count++]=*it;

for(int j=0;j<count;j++)
cout<<ans[j]<<" "<<ans[(j+1)%count]<<endl;
}
if((i+1)!=N)
cout<<endl;
}
}

[adelar]

Thanks Jan,
only to confer...
again was AC in 5.??? seconds, and now show TLE.
this algorithm is correct?

Code: Select all

  if(even(graph) || !conected(graph))
     "some beads may be lost"
  else
      print euler path;

thanks in advance...

[Batu]

Hi all.

I'm having Runtime Error in this problem.
I think it's very strange because i do not use pointers.

Code: Select all

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int grafo[51][51];
int grado[51];
int grado_aux[51];
bool activo[51];
int visitado[51];
queue<int> colita;
queue<int> cola;
int vtrue;
int primero;
int abalorios;

void borrar() {
  for(int i = 0; i <= 50; i++) {
    for(int j = 0; j <= 50; j++) { 
      grafo[i][j] = 0;
     }
    grado[i] = 0;
    grado_aux[i] = 0;
    activo[i] = false;
    visitado[i] = 0;
  }
  while(!cola.empty()) cola.pop();
}

void leer() {
  int n, m;
  
  scanf("%d", &abalorios);
  
  scanf("%d%d", &n, &m);
  grafo[n][m]++;
  grafo[m][n]++;
  grado[n]++;
  grado[m]++;
  grado_aux[n]++;
  grado_aux[m]++;
  primero = n;
  activo[n] = true;
  activo[m] = true;

  for(int i = 1; i < abalorios; i++) {
    scanf("%d%d", &n, &m);
    activo[n] = true;
    activo[m] = true;
    grafo[n][m]++;
    grafo[m][n]++;
    grado[n]++;
    grado[m]++;
    grado_aux[n]++;
    grado_aux[m]++;
  }
}

void bfs(int vertice) {
  int aux;

  while(!colita.empty()) colita.pop();

  vtrue++;
  colita.push(vertice);
  visitado[vertice] = vtrue;
  while(!colita.empty()) {
    aux = colita.front();
    colita.pop();
    for(int i = 1; i <= 50; i++) {
      if(grafo[aux][i] > 0 && visitado[i] != vtrue) {
	colita.push(i);
	visitado[i] = vtrue;
      }
    }
  }
}

bool euleriano() {

  sort(grado_aux, grado_aux+51);

  for(int i = 50; i > 0 && grado_aux[i] > 0; i--)
    if(grado_aux[i] % 2) return false;

  return true;
}

bool conectado(int vertice) {

  bfs(vertice);

  for(int i = 1; i <= 50; i++)
    if(activo[i] && visitado[i] != vtrue)
      return false;
  
  return true;
}

void imprime_sol() {

  int aux;
  int aux2;
  while(!cola.empty()) {
    aux = cola.front();
    cola.pop();
    aux2 = cola.front();
    cola.pop();
    printf("%d %d\n",aux, aux2);
  }
}

int busca_siguiente(int vertice) {

  int i;
  int candidato;

  if(grafo[vertice][vertice] > 0) {
    grafo[vertice][vertice] -= 2;
    return vertice;
  }

  for(i = 1; i <= 50; i++){
    if(grafo[vertice][i] > 0) {
      candidato = i;
      grafo[vertice][i]--;
      grafo[i][vertice]--;
      grado[i]--;
      grado[vertice]--;
      if(grado[i] <= 0) activo[i] = false;
      if(grado[vertice] <= 0) activo[i] = false;
      if(conectado(i)) 
	return i;
      else {
	grafo[vertice][i]++;
	grafo[i][vertice]++;
	grado[i]++;
	grado[vertice]++;
	activo[i] = true;
	activo[vertice] = true;
      }
    }
  }
  return -1;
}

bool calcula_sol() {
  int v1 = primero;
  int v2;

  while(abalorios) {
    v2 = busca_siguiente(v1);
    if(v1 < 0) return false;
    abalorios--;
    grado[v1]--;
    grado[v2]--;
    if(grado[v1] <= 0) activo[v1] = false;
    if(grado[v2] <= 0) activo[v2] = false;
    cola.push(v1);
    cola.push(v2);
    v1 = v2;
  }
  return true;
}

int main() {
  int casos;

  scanf("%d", &casos);  
  for(int caso = 1; caso <= casos; caso++){
    vtrue = 0;
    borrar();
    leer();
    printf("Case #%d\n", caso);
    if(euleriano() && conectado(primero)) {
      if(!calcula_sol()) 
	printf("some beads may be lost\n");
      else
	imprime_sol();
    }else{
      printf("some beads may be lost\n");
    }    

    if(caso < casos)     
      printf("\n");
  }

  return 0;
}

Anyone could help me?
Thanks in advance.

PS. Sorry for my English

[Robert Gerbicz]

One easy input (contains two tests), but your program may fail these if you don't use multiple edges in your code.
You can form a necklace from both beads tests.

Code: Select all

2
5
50 50
50 50
50 50
50 50
50 50
6
1 50
1 50
1 50
1 50
1 50
1 50

One possible output:

Code: Select all

Case #1
50 50
50 50
50 50
50 50
50 50

Case #2
1 50
50 1
1 50
50 1
1 50
50 1

[Piova]

I got runtime error in this problem. I can't find the mistake.
Please help me. Thinks.

Code: Select all

#include <iostream>
#include <vector>
using namespace std;

struct node
{
	short num;
	node *next;
};

struct color
{
	short co;
	node *now,*head,*last;
}c[51];

short in[50],w;

bool DFS(short a,short &dest,bool v[])
{
	v[a]=false;
	c[a].now=c[a].head;
	do
	{
		if(c[a].now->num==dest)	return true;
		if(v[c[a].now->num]&&DFS(c[a].now->num,dest,v))	return true;
		c[a].now=c[a].now->next;
	}while(c[a].now);
	return false;
}

void DFS(short a,bool v[])
{
	v[a]=false;
	c[a].now=c[a].head;
	do
	{
		if(v[c[a].now->num])
		{
			DFS(c[a].now->num,v);
		}
		c[a].now=c[a].now->next;
	}while(c[a].now);
}

void run(short &s,bool v[])
{
	short i,a=s,b,t=0;
	while(t<c[s].co)
	{
		while(1)
		{
			node *n,*m;
			n=c[a].head;
			b=n->num;
			c[a].head=n->next;
			m=c[b].head;
			if(m->num==a)	c[b].head=m->next;
			else
			{
				while(m->next->num!=a)	m=m->next;
				c[b].now=m;
				m=c[b].now->next;
				if(m==c[b].last)	c[b].last=c[b].now;
				c[b].now->next=m->next;
			}
			for(i=0;i<w;i++)	v[in[i]]=true;
			if(a==b||n->next==NULL||DFS(a,b,v))
			{
				delete n,m;
				break;
			}
			c[a].last->next=n;
			c[a].last=n;
			c[a].last->next=NULL;
			c[b].last->next=m;
			c[b].last=m;
			c[b].last->next=NULL;
		}
		if(a==s)	t++;
		if(b==s)	t++;
		cout<<a<<' '<<b<<endl;
		a=b;
	}
}

void create(short &a,short &b)
{
	short i;
	for(i=0;i<w;i++)
		if(a==in[i])	break;
	if(i==w)	in[w++]=a;
	node *newnode=new node;
	c[a].co++;
	newnode->num=b;
	newnode->next=NULL;
	if(c[a].head==NULL)
	{
		c[a].now=c[a].head=newnode;
	}
	c[a].now->next=newnode;
	c[a].now=newnode;
}

bool even()
{
	for(short j=0;j<w;j++)
	{
		if(c[in[j]].co&1)	return false;
		c[in[j]].last=c[in[j]].now;
	}
	return true;
}

bool connect(short &a,bool v[])
{
	short j;
	for(j=0;j<w;j++)	v[in[j]]=true;
	DFS(a,v);
	for(j=0;j<w;j++)
		if(v[in[j]])	return false;
	return true;
}

int main()
{
	short n,m,a,b,i,j;
	bool isStart=false,v[51];
	cin>>n;
	in[0]=0;
	for(i=1;i<=n;i++)
	{
		w=0;
		if(isStart)	cout<<endl;
		else	isStart=true;
		cin>>m;
		for(j=1;j<51;j++)
		{
			c[j].co=0;
			c[j].head=NULL;
		}
		cin>>a>>b;
		in[w++]=a;
		create(a,b);
		create(b,a);
		for(j=1;j<m;j++)
		{
			cin>>a>>b;
			create(a,b);
			create(b,a);
		}
		cout<<"Case #"<<i<<endl;
		if(even()&&connect(a,v))
		{
			run(a,v);
		}
		else	cout<<"some beads may be lost\n";
	}
	return 0;
}

[MRH]

remove after acc......

[Chirag Chheda]

Your program gives wrong answer for the input

Code: Select all

1

4
1 2
2 2
2 1
1 1