10054 - The Necklace

All about problems in Volume C. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Re: 10054 - The Necklace

Postby MRH » Fri Mar 13, 2009 8:42 pm

now i got ACC................
thanks " Chirag Chheda"
MRH
Learning poster
 
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

Re:

Postby Angeh » Wed Sep 02, 2009 12:22 am

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

Postby Angeh » Wed Sep 02, 2009 2:56 am

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


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

Postby Angeh » Sun Sep 06, 2009 3:22 pm

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

Postby free » Sun Sep 12, 2010 1:05 pm

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;
}
free
New poster
 
Posts: 6
Joined: Fri Aug 13, 2010 8:35 am
Location: China

Re: 10054 - The Necklace

Postby cka7749 » Sat Nov 20, 2010 8:07 am

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;
}
cka7749
New poster
 
Posts: 1
Joined: Sat Nov 20, 2010 8:04 am

Re: 10054 - The Necklace

Postby multisystem » Tue Mar 29, 2011 8:37 pm

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
multisystem
New poster
 
Posts: 4
Joined: Fri Oct 02, 2009 4:06 pm

10054 Necklace TLE issue

Postby zuzumumba » Sun May 29, 2011 2:18 am

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.LinkedList;
import java.util.HashMap;
import java.util.Scanner;

public class Main
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
HashMap<Integer, LinkedList<Integer>> map;
LinkedList<Integer> path;
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))
map.put(color1, new LinkedList<Integer>());
if (!map.containsKey(color2))
map.put(color2, new LinkedList<Integer>());
map.get(color2).add(color1);
map.get(color1).add(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));
path.add(prev);
path.add(next);
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;
}
}
zuzumumba
New poster
 
Posts: 1
Joined: Sun May 29, 2011 2:06 am

Re: 10054 - The Necklace

Postby SamCratsby » Tue Nov 08, 2011 10:48 am

multisystem, fine suggestion! got it clearly.
SamCratsby
New poster
 
Posts: 1
Joined: Tue Nov 08, 2011 10:42 am

Re: 10054 - The Necklace

Postby brianfry713 » Mon Jan 14, 2013 9:42 pm

Code: Select all
1
5
1 2
2 2
2 2
2 1
1 1
Check input and AC output for hundreds of problems on uDebug!
brianfry713
Guru
 
Posts: 3864
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10054 - The Necklace

Postby rafikamal » Thu Jan 31, 2013 11:07 am

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

Postby brianfry713 » Thu Jan 31, 2013 9:25 pm

Post your full code with the includes.
Check input and AC output for hundreds of problems on uDebug!
brianfry713
Guru
 
Posts: 3864
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10054 - The Necklace

Postby laberle » Wed Apr 03, 2013 7:14 pm

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

Postby brianfry713 » Fri Apr 05, 2013 12:03 am

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 hundreds of problems on uDebug!
brianfry713
Guru
 
Posts: 3864
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10054 - The Necklace

Postby terry646623 » Wed Feb 26, 2014 3:45 am

Wrong answer. Why?
#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--){
if(bead[j]<bead[j-1]){
temp=bead[j-1];
bead[j-1]=bead[j];
bead[j]=temp; }
}
}
}
int necklace(int bead[3000],int number){
int i;
for(i=0;i<number;i=i+2){
if(bead[i]!=bead[i+1])
return 0; }
return 1; }
int main(){
int count;
int i;
int pair;
int number;
int j;
int complete;
int bead[3000];
scanf("%d",&count);
for(i=1;i<=count;i++){
scanf("%d",&pair);
number=pair*2;
for(j=0;j<number;j++)
scanf("%d",&bead[j]);
sort(bead,number);
complete=necklace(bead,number);
if(complete==0){
printf("Case #%d\n",i);
printf("some beads may be lost\n\n");}
else{
printf("Case #%d\n",i);
for(j=1;j<number;j=j+2){
if(j+1==number)
printf("%d %d\n\n",bead[j],bead[0]);
else
printf("%d %d\n",bead[j],bead[j+1]); }
}
}
}
terry646623
New poster
 
Posts: 8
Joined: Fri Jan 17, 2014 3:35 pm

PreviousNext

Return to Volume C

Who is online

Users browsing this forum: No registered users and 1 guest