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

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

### Re: 10054 - The Necklace

now i got ACC................
thanks " Chirag Chheda"

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### Re:

-------------------------------------------------------------------
Last edited by Angeh on Wed Sep 02, 2009 2:57 am, edited 1 time in total.
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### Re:

drewsome wrote:
Julien Cornebise wrote: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
First How can this be O(n) if you use a nxn matrix ? ? ? ? ? ?
Will it work for
1
6
10 20
10 30
20 30
30 40
40 50
30 50
???????????????????????????
It seems to be a simple DFS !!!
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### Re: 10054 - The Necklace

Think For a Simple Version of DFS !!! No Cycles No Merge !!

Code: Select all

`` AC 0.292 .... ``
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

free
New poster
Posts: 6
Joined: Fri Aug 13, 2010 8:35 am
Location: China

### 10054 The Necklace

hi, i have tested a lot of testcases, and i got the right answer.
but when i submit i got TLE, could someone help me? thx
this is my code:

Code: Select all

``````#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<ctype.h>
#include<iostream>
using namespace std;
#define MAX1 50+5
int tc;
int n;
int x, y;
int map[MAX1][MAX1];
bool vis[MAX1];
int goin[MAX1];
int cnt, node;
int stack[2000][2];
int top;
bool flag;

void dfs(int u)         //look for liangtong
{
vis[u]=true;
cnt++;
if (cnt==node) {flag=true; return; }
for (int v=1;v<=50;v++) if (map[u][v] && !vis[v])
{
dfs(v);
if (flag) return;
}
}

void euler(int u)
{
if (top==n && stack[top][1]!=stack[1][0])           //mo wei bu tong jiu tui chu
{
return;
}
else if (top==n && stack[top][1]==stack[1][0])      //ruguo chengli jiu shezhi biaozhi bianliang flag
{
flag=true;
return;
}
for (int v=1;v<=50;v++) if (map[u][v])
{
top++;
stack[top][0]=u; stack[top][1]=v;
map[u][v]--; map[v][u]--;
euler(v);
if (flag) return;                               //look for
map[u][v]++; map[v][u]++;
top--;
}
}

void work()
{
for (int i=1;i<=50;i++) if (goin[i]%2 != 0)
{
cout<<"some beads may be lost"<<endl;
return;
}
cnt=0;
flag=false;
dfs(x);
if (cnt < node)
{
cout<<"some beads may be lost"<<endl;
return;
}
top=0;
flag=false;
euler(x);
for (int i=1;i<=n;i++) cout<<stack[i][0]<<' '<<stack[i][1]<<endl;
}

int main()
{
freopen("10054.in","r",stdin);
freopen("10054.out","w",stdout);
cin>>tc;
for (int ii=1;ii<=tc;ii++)
{
cin>>n;
memset(map,0,sizeof(map));
memset(vis,false,sizeof(vis));
memset(goin,0,sizeof(goin));
node=0;
for (int i=1;i<=n;i++)
{
cin>>x>>y;
map[x][y]++; map[y][x]++;
if (!goin[x]) node++;
goin[x]++;          //look for
if (!goin[y]) node++;
goin[y]++;
}
printf("Case #%d\n",ii);
work();
if (ii<tc) cout<<endl;
}
return 0;
}
``````

cka7749
New poster
Posts: 1
Joined: Sat Nov 20, 2010 8:04 am

### Re: 10054 - The Necklace

I got WA.
But, I don't know what's wrong.
Could you help me??
Thx.

Code: Select all

``````
#include <stdio.h>
#define NUM 51
int v[NUM][NUM];

void eulercycle(int x){
int i;
for( i=1; i<NUM; i++){
if(v[x][i]!=0){

--v[x][i];
--v[i][x];
printf("%d %d\n", x, i);
eulercycle(i);
}
}
}
int main(){
int casenum, n, degree[NUM], i, j, k, c1, c2;
int iseuler;
scanf("%d", &casenum);
for( i=1; i<=casenum; ++i){
scanf("%d", &n);
iseuler=1;

for( j=0; j<NUM; ++j) degree[j]=0;
for( j=0; j<NUM; ++j)
for( k=0; k<NUM; ++k) v[j][k]=0;

for( j=0; j<n; ++j){
scanf("%d %d", &c1, &c2);

++v[c1][c2];
++v[c2][c1];
++degree[c1];
++degree[c2];
}
printf("Case #%d\n", i);

for( j=1; j<NUM; ++j){
if( degree[j]%2!=0){
iseuler=0;
break;
}
}

if(iseuler){
eulercycle(c1);
}
else{
printf("some beads may be lost\n");
}
}
return 0;
}
``````

multisystem
New poster
Posts: 4
Joined: Fri Oct 02, 2009 4:06 pm

### Re: 10054 - The Necklace

AC

The lesson I've learned: push the node after back from DFS

Code: Select all

``````2
3
1 2
2 2
2 1
3
2 2
2 1
1 2
``````

zuzumumba
New poster
Posts: 1
Joined: Sun May 29, 2011 2:06 am

### 10054 Necklace TLE issue

I've gotten the correct output under various test cases I've given it but it's apparently too slow.
Here's my java solution:

import java.util.HashMap;
import java.util.Scanner;

public class Main
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int runs = in.nextInt();
for (int t = 1; t < runs + 1; t++)
{
path = new LinkedList<Integer>();
int beads = in.nextInt();
map = new HashMap<Integer, LinkedList<Integer>>(beads + 5);
int start = -1;
for (int n = 0; n < beads; n++)
{
int color1 = in.nextInt();
int color2 = in.nextInt();
if (n == 0)
start = color1;
if (!map.containsKey(color1))
if (!map.containsKey(color2))
}
System.out.println("Case #" + t);
if (isEuler(map))
{
int prev = start;
int next;
while (map.containsKey(prev))
{
next = map.get(prev).removeFirst();
map.get(next).remove(new Integer(prev));
if (map.get(next).size() == 0)
map.remove(next);
if (map.containsKey(prev))
{
if (map.get(prev).size() == 0)
map.remove(prev);
}
else
break;
prev = next;
}
if (map.isEmpty())
while (!path.isEmpty())
System.out.println(path.removeFirst() + " "
+ path.removeFirst());
else
System.out.println("some beads may be lost");
}
else
System.out.println("some beads may be lost");
if (t != runs)
System.out.println();
}
}
public static boolean isEuler(HashMap<Integer, LinkedList<Integer>> map)
{
if (map.isEmpty())
return false;
for (LinkedList<Integer> list : map.values())
if (list.size() % 2 != 0)
return false;
return true;
}
}

SamCratsby
New poster
Posts: 1
Joined: Tue Nov 08, 2011 10:42 am

### Re: 10054 - The Necklace

multisystem, fine suggestion! got it clearly.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10054 - The Necklace

Code: Select all

``````1
5
1 2
2 2
2 2
2 1
1 1``````
Check input and AC output for thousands of problems on uDebug!

rafikamal
New poster
Posts: 2
Joined: Sat Nov 26, 2011 11:06 am

### Re: 10054 - The Necklace

My program passes the sample test cases and all the test cases from this forum, but I'm continuously getting WA.

Code: Select all

``````list<int> edges[SIZE];

void tour(int node)
{
stack<int> nodesToBeVisited;
nodesToBeVisited.push(node);

while(!nodesToBeVisited.empty())
{
node = nodesToBeVisited.top();
nodesToBeVisited.pop();
while(!edges[node].empty())
{
int nextNode = *edges[node].begin();
edges[node].erase(edges[node].begin());
edges[nextNode].erase(find(edges[nextNode].begin(), edges[nextNode].end(), node));
nodesToBeVisited.push(nextNode);
}
}
}

int main()
{
//freopen("input.txt", "r", stdin);
//freopen("out.txt", "w", stdout);

int i, j, k, l, sum = 0;
int tc, t, d, x, y, a, b, r, n, current, first;
char ch;
int mx;
bool flag;
unsigned long long ln;

scanf("%d", &tc);

for(t = 1; t <= tc; t++)
{
scanf("%d", &n);
printf("Case #%d\n", t);

for(i = 1; i <= 50; i++)
edges[i].clear();

for(i = 1; i <= n; i++)
{
scanf("%d %d", &x, &y);
edges[x].push_back(y);
edges[y].push_back(x);
}

flag = false;
for(i = 1; i <= 50; i++)
if(edges[i].size() % 2) {flag = true; break;}
if(!flag)
{
tour(y);

if(beads.size() == n + 1)
{
list<int>::iterator it = beads.begin();
while(true)
{
x = *it++;
{
y = *it;
printf("%d %d\n", x, y);
}
else break;
}
}
else printf("some beads may be lost\n");
}
else printf("some beads may be lost\n");

if(t != tc) cout << endl;
}

return 0;
}``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10054 - The Necklace

Post your full code with the includes.
Check input and AC output for thousands of problems on uDebug!

laberle
New poster
Posts: 5
Joined: Mon Mar 25, 2013 1:19 am

### Re: 10054 - The Necklace

I'm getting correct outputs for all the inputs specified on this forum, but I'm still getting WA. Can someone help me please?

The only place I can see being an issue is how I'm figuring out if it's connected or not, so I tried a BFS to determine that instead, but then I got TLE.

Here's my code:

Code: Select all

``````#include <iostream>
#include <list>
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

const int GRAPH_SIZE = 50;
int graph[GRAPH_SIZE][GRAPH_SIZE];
int n, x, y;
bool connected;
list<int> path;

void print_path() {
int printFlag = 0;
while(!path.empty()){
int front = path.front();
if (printFlag == 0) {
cout << front << ' ';
printFlag++;
}
else if (printFlag == 1) {
cout << front << endl;
printFlag = 0;
}
path.pop_front();
}
}

void find_cycle(int pos, list<int>::iterator iter){

for(int i = 0; i < GRAPH_SIZE; i++){
if(graph[pos][i] > 0){
graph[pos][i]--;
graph[i][pos]--;
iter = path.insert(iter, pos+1);
iter = path.insert(iter, i+1);
find_cycle(i, iter);
break;
}
}

}

void reset() {
for(int i = 0; i < GRAPH_SIZE; i++){
for(int j = 0; j < GRAPH_SIZE; j++){
graph[i][j] = 0;
}
}
}

bool edgesLeft() {
int count = 0;
for(int i = 0; i < GRAPH_SIZE; i++){
for(int j = 0; j < GRAPH_SIZE; j++){
count += graph[i][j];
}
}
if (count > 0) {
return true;
}
else {
return false;
}
}

int findNextEdge() {
for(int i = 0; i < GRAPH_SIZE; i++){
for(int j = 0; j < GRAPH_SIZE; j++){
if (graph[i][j] > 0) {
return i;
}
}
}
return -1;
}

void euler() {
find_cycle(0, path.begin());
while (edgesLeft()) {
int edge = findNextEdge();
list<int>::iterator iter = std::find(path.begin(), path.end(), edge+1);
if (iter == path.end() && !path.empty() && path.back() != edge+1) {
connected = false;
return;
}
if (path.empty()) {
find_cycle(edge, path.begin());
}
else {
find_cycle(edge, ++iter);
}
}
}

int main(){

cin >> n;
for (int i=0; i < n; i++) {
cout << "Case #" << i + 1 << endl;
for (int j = 0; j < numBeads; j++) {
cin >> x >> y;
graph[x-1][y-1]++;
graph[y-1][x-1]++;
}

bool lostBeads = false;
connected = true;
//Check for not enough beads
for (int j=0; j < GRAPH_SIZE; j++) {
int vertexDegree = 0;
for (int k=0; k < GRAPH_SIZE; k++) {
if (graph[j][k] > 0) {
vertexDegree += graph[j][k];
}
//cout << "[" << graph[j][k] << "] ";
}
if (vertexDegree % 2 != 0) {
cout << "some beads may be lost" << endl;
break;
}
//cout << endl;
}
euler();
if (connected) {
print_path();
}
else {
cout << "some beads may be lost" << endl;
}
}
reset();
if (!(i == n-1)) {
cout << endl;
}
}

}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10054 - The Necklace

Input:

Code: Select all

``````1
55
1 40
20 15
27 16
1 22
28 24
6 49
16 9
14 10
46 25
40 12
25 37
40 24
36 1
18 24
20 5
9 12
24 35
10 19
46 15
23 8
16 20
18 1
12 32
44 30
9 35
19 24
16 12
22 27
40 23
1 20
15 1
31 22
40 47
44 40
30 46
18 10
32 37
30 25
37 40
1 7
31 22
27 27
8 27
18 1
46 6
40 24
40 37
47 5
10 8
9 49
27 15
40 14
36 25
7 30
8 28
``````
AC output:

Code: Select all

``````Case #1
49 9
9 35
35 24
24 40
40 37
37 40
40 24
24 19
19 10
10 18
18 24
24 28
28 8
8 23
23 40
40 44
44 30
30 46
46 25
25 37
37 32
32 12
12 16
16 27
27 27
27 15
15 20
20 16
16 9
9 12
12 40
40 14
14 10
10 8
8 27
27 22
22 31
31 22
22 1
1 40
40 47
47 5
5 20
20 1
1 18
18 1
1 36
36 25
25 30
30 7
7 1
1 15
15 46
46 6
6 49
``````
Check input and AC output for thousands of problems on uDebug!

terry646623
New poster
Posts: 8
Joined: Fri Jan 17, 2014 3:35 pm

### Re: 10054 - The Necklace

#include <stdio.h>
#include<stdlib.h>
void sort(int bead[3000],int number){
int i;
int j;
int temp;
for(i=1;i<number;i++){
for(j=i;j>0;j--){
}
}
}
int necklace(int bead[3000],int number){
int i;
for(i=0;i<number;i=i+2){
return 0; }
return 1; }
int main(){
int count;
int i;
int pair;
int number;
int j;
int complete;
scanf("%d",&count);
for(i=1;i<=count;i++){
scanf("%d",&pair);
number=pair*2;
for(j=0;j<number;j++)