## 10054 - The Necklace

Moderator: Board moderators

### Re: 10054 - The Necklace

now i got ACC................
thanks " Chirag Chheda"
MRH
Learning poster

Posts: 51
Joined: Mon Aug 11, 2008 9:09 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;)
Angeh
Experienced poster

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

### 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+5int 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;}`
free
New poster

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

### 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 51int 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;}`
cka7749
New poster

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

### Re: 10054 - The Necklace

AC

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

Code: Select all
`231 22 22 132 22 11 2`
multisystem
New poster

Posts: 4
Joined: Fri Oct 02, 2009 4:06 pm

### 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++)
{
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
}
else
if (t != runs)
System.out.println();
}
}
public static boolean isEuler(HashMap<Integer, LinkedList<Integer>> map)
{
if (map.isEmpty())
return false;
if (list.size() % 2 != 0)
return false;
return true;
}
}
zuzumumba
New poster

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

### Re: 10054 - The Necklace

multisystem, fine suggestion! got it clearly.
SamCratsby
New poster

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

### Re: 10054 - The Necklace

Code: Select all
`151 22 22 22 11 1`
Check input and AC output for thousands of problems on uDebug!
brianfry713
Guru

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

### 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];list<int> beads;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();         beads.push_back(nextNode);         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();      beads.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)      {         beads.push_back(y);         tour(y);                  if(beads.size() == n + 1)         {            list<int>::iterator it = beads.begin();            while(true)            {               x = *it++;               if(it != beads.end())               {                  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;}`
rafikamal
New poster

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

### Re: 10054 - The Necklace

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

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

### 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(){   int n, numBeads;   cin >> n;   for (int i=0; i < n; i++) {      cout << "Case #" << i + 1 << endl;      cin >> numBeads;      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;            lostBeads = true;            break;         }         //cout << endl;      }      if (!lostBeads) {         euler();         if (connected) {            print_path();         }         else {            cout << "some beads may be lost" << endl;         }      }      reset();      if (!(i == n-1)) {         cout << endl;      }   }}`
laberle
New poster

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

### Re: 10054 - The Necklace

Input:
Code: Select all
`1551 4020 1527 161 2228 246 4916 914 1046 2540 1225 3740 2436 118 2420 59 1224 3510 1946 1523 816 2018 112 3244 309 3519 2416 1222 2740 231 2015 131 2240 4744 4030 4618 1032 3730 2537 401 731 2227 278 2718 146 640 2440 3747 510 89 4927 1540 1436 257 308 28`
AC output:
Code: Select all
`Case #149 99 3535 2424 4040 3737 4040 2424 1919 1010 1818 2424 2828 88 2323 4040 4444 3030 4646 2525 3737 3232 1212 1616 2727 2727 1515 2020 1616 99 1212 4040 1414 1010 88 2727 2222 3131 2222 11 4040 4747 55 2020 11 1818 11 3636 2525 3030 77 11 1515 4646 66 49`
Check input and AC output for thousands of problems on uDebug!
brianfry713
Guru

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

### Re: 10054 - The Necklace

#include <stdio.h>
#include<stdlib.h>
int i;
int j;
int temp;
for(i=1;i<number;i++){
for(j=i;j>0;j--){
}
}
}
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++)
if(complete==0){
printf("Case #%d\n",i);
else{
printf("Case #%d\n",i);
for(j=1;j<number;j=j+2){
if(j+1==number)
else
}
}
}
terry646623
New poster

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

PreviousNext