10054 - The Necklace

[MRH]

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

[Angeh]

-------------------------------------------------------------------

[Angeh]

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

[Angeh]

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

Code: Select all

 AC 0.292 .... 

[free]

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]

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]

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]

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;
}
}

[SamCratsby]

multisystem, fine suggestion! got it clearly.

[brianfry713]

Code: Select all

1
5
1 2
2 2
2 2
2 1
1 1

[rafikamal]

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;
}

[brianfry713]

Post your full code with the includes.

[laberle]

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;
		}
	}

}

[brianfry713]

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

[terry646623]

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!=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]); }
}
}
}