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

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

### wa wa wa... 27... inf

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...
Last edited by adelar on Thu Jun 28, 2007 5:08 pm, edited 2 times in total.
leocm
New poster
Posts: 22
Joined: Fri Jul 21, 2006 9:44 am
Location: Brasil
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
New poster
Posts: 35
Joined: Wed May 02, 2007 11:48 pm
Location: Brasil

### wa, inf wa

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

### wawawa...

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
You should explain your algorithm first.
Ami ekhono shopno dekhi...
HomePage
adelar
New poster
Posts: 35
Joined: Wed May 02, 2007 11:48 pm
Location: Brasil

### AC, I dont belive...

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
New poster
Posts: 1
Joined: Sat Aug 25, 2007 7:49 pm
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
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
I get too many WR,more than 15 times.whats wrong help me.........

Code: Select all

``````Remove after Acc
``````
Thanks
Keep posting
Sapnil
puneetm84
New poster
Posts: 1
Joined: Wed Oct 31, 2007 6:35 am

### Time Limit Exceeded

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

### TLE

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
New poster
Posts: 1
Joined: Fri Apr 04, 2008 11:50 am

### Re: 10054 - The Necklace

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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

### Re: 10054 - The Necklace

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
New poster
Posts: 1
Joined: Thu Aug 28, 2008 8:50 am

### Re: 10054 - The Necklace

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
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

### Re: 10054 - The Necklace

remove after acc......
Last edited by MRH on Fri Mar 13, 2009 8:44 pm, edited 1 time in total.
Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

### Re: 10054 - The Necklace

Your program gives wrong answer for the input

Code: Select all

``````1

4
1 2
2 2
2 1
1 1
``````