11504 - Dominos

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

Moderator: Board moderators

MarioYC
New poster
Posts: 2
Joined: Thu Aug 07, 2008 2:54 am

Re: 11504 - Dominos

Post by MarioYC » Sun Oct 05, 2008 6:16 pm

Hi. I've been trying to solve this problem, but when I try the test cases in Waterloo's web page http://plg1.cs.uwaterloo.ca/~acm00/080927/data/D.6.dat, my code gives an answer only for the two firt cases.

First, I find all the connected components and then I see if a connected component affects another one, then I only take the connected components which aren't affected by any other connceceted component.

Code: Select all

#include<iostream>
#include<vector>

using namespace std;

vector< vector<int> > L1;
vector< vector<int> > L2;
vector<int> v;
bool visited[100000];
int component[100000];
int num_components;
bool in_component[100000];

void dfs1(int start){
    visited[start]=true;
    
    for(int i=0;i<L1[start].size();i++)
        if(!visited[L1[start][i]])
            dfs1(L1[start][i]);
    
    v.push_back(start);
}

void dfs2(int start){
    visited[start]=true;
    component[start]=num_components;
    
    for(int i=0;i<L2[start].size();i++)
        if(!visited[L2[start][i]])
            dfs2(L2[start][i]);
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    
    int T,n,m,a,b,cont;
    
    scanf("%d",&T);
    
    for(int caso=0;caso<T;caso++){
        scanf("%d %d",&n,&m);
        
        L1.clear();
        L1.resize(n);
        L2.clear();
        L2.resize(n);
        
        for(int i=0;i<m;i++){
            scanf("%d %d",&a,&b);
            
            L1[a-1].push_back(b-1);
            L2[b-1].push_back(a-1);
        }
        
        fill(visited,visited+n,false);
        v.clear();
        
        for(int i=0;i<n;i++){
            if(!visited[i]){
                dfs1(i);
            }
        }
        
        fill(visited,visited+n,false);
        
        num_components=0;
        
        for(int i=v.size()-1;i>=0;i--){
            if(!visited[v[i]]){
                dfs2(v[i]);
                num_components++;
            }
        }
        
        fill(in_component,in_component+num_components,false);
        
        for(int i=0;i<n;i++)
            for(int j=0;j<L1[i].size();j++)
                if(component[i]!=component[L1[i][j]])
                    in_component[component[L1[i][j]]]=true;
        
        cont=0;
        
        for(int i=0;i<num_components;i++)
            if(!in_component[i]) cont++;
        
        cout<<cont<<endl;
    }
    
    return 0;
}

gba356
New poster
Posts: 15
Joined: Sat Apr 28, 2007 10:12 am
Location: Taiwan

Re: 11504 - Dominos

Post by gba356 » Fri Oct 17, 2008 3:01 pm

Hi, I have been given constant WAs for the problem.

First of all, I consider the dominos a directed graph.

And I tried to approach the problem by DFS-ing through the nodes with no in-edge, and then DFS the nodes that are not visited , and then print the numbers of dominos knocked down by hand.

I passed the official test cases University of Waterloo provides:

http://plg1.cs.uwaterloo.ca/~acm00/080927/data/D.6.dat
http://plg1.cs.uwaterloo.ca/~acm00/080927/data/D.6.diff

But the judge keeps giving me WA, and the program halts in 0.400 second. I don't know where's the problem, is my algorithm

correct?

P.S. I chose adjacency lists with dynamic memory allocation as my graph data structure, maybe I have some small error on handling the dynamic memory allocation. I'll post my code if needed :)

Best regards

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11504 - Dominos

Post by andmej » Sun Oct 19, 2008 12:46 am

It may fail in some cases. For example, if you have the following graph:

3 nodes and these directed edges: <1, 2> <2, 1> and <3, 2>

If you start the DFS at node 1 you will visit nodes 1 and 2. Then you will also knockdown tile 3, with total score 2 (Tiles 1 and 3). But the best solution is to just knock tile 3.

First you have to reduce the graph to its directed components graph, which is acyclic and works with your algorithm.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

gba356
New poster
Posts: 15
Joined: Sat Apr 28, 2007 10:12 am
Location: Taiwan

Re: 11504 - Dominos

Post by gba356 » Mon Oct 20, 2008 2:12 pm

andmej wrote:It may fail in some cases. For example, if you have the following graph:

3 nodes and these directed edges: <1, 2> <2, 1> and <3, 2>

If you start the DFS at node 1 you will visit nodes 1 and 2. Then you will also knockdown tile 3, with total score 2 (Tiles 1 and 3). But the best solution is to just knock tile 3.

First you have to reduce the graph to its directed components graph, which is acyclic and works with your algorithm.
Hi, first of all, thank you for your reply.

For the instance above you mentioned, my algorithm will DFS from vertex 3 first, which is the only vertex without in-edges. No error occurs when I test on my computer as desired.

Here's my algorithm, I wonder if my greedy is correct:

1. Find the vertices without in-edges.
2. DFS by taking the vertices with indegree zero as start points; mark the vertices "visited" so as not to be visited second time.
3. DFS through the remains, for cycle detection.
4. Output the answer.

And the following is my commented code, I chose adjacency lists as my graph data structure:

Code: Select all

#include<iostream>
#define N 100001
using namespace std;

struct Node{                        /* adjacency list */
    int now;
    Node* next;
} root[N];                          

    bool visited[N],indegree[N];    /* if indegree[i]==true, then node i has inedges */

void MakeArc( int I,int J )         /* Create directed Edge(I,J) */
{
    Node* newnode = new Node;
    newnode->now = J;
    newnode->next = root[I].next;
    root[I].next = newnode;
}
void DFS( int n )
{
    Node* ptr = root[n].next;
    while( ptr )
    {
        if( !visited[ ptr->now ] )
        {
            visited[ ptr->now ] = 1;
            DFS( ptr->now );
        }
        ptr = ptr->next;
    }
}
void Release( Node* ptr )           /* release memory */
{
    if( ptr->next )
        Release( ptr->next );
    delete ptr;
}
int main()
{
//    freopen("D.6.dat","r",stdin);
//    freopen("out.txt","w",stdout);
    int V,E,caseN;
    int I,J;
    int count;
    ios_base::sync_with_stdio( false );
    cin>>caseN;
    while( caseN-- )
    {
        cin>>V>>E;
        memset( visited,0,sizeof(bool)*N );
        memset( indegree,0,sizeof(bool)*N );
        memset( root,0,sizeof(Node)*N );
        count = 0;
        for( int i=0;i<E;i++ )      /* graph input */
        {
            cin>>I>>J;
            MakeArc( I,J );
            indegree[J] = true;
        }
        for( int i=1;i<=V;i++ )     /* DFS through nodes with indegree zero */
            if( !indegree[i] && !visited[i] )
            {
                visited[i] = 1;
//                cout<<"Node:"<<i<<endl;
                DFS( i );
                count++;
            }
        for( int i=1;i<=V;i++ )     /* cycle detection */
            if( !visited[i] )
            {
//                cout<<"Node:"<<i<<endl;
                visited[i] = 1;
                DFS( i );
                count++;
            }
        cout<<count<<endl;
        for( int i=1;i<=V;i++ )if( root[i].next )   /* memory relaese */
            Release( root[i].next );
    }
}
Any comments are appreciated!

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11504 - Dominos

Post by andmej » Tue Oct 21, 2008 6:05 am

Try this case:

Code: Select all

1
4 5
1 2
2 1
3 2
3 4
4 3
Correct output is 1 (Tile #4), but your code outputs 2.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

gba356
New poster
Posts: 15
Joined: Sat Apr 28, 2007 10:12 am
Location: Taiwan

Re: 11504 - Dominos

Post by gba356 » Wed Oct 22, 2008 2:46 pm

I changed and changed my algorithm for several times, but none of them succeeded to solve the problem :cry:

Can I have some hints?

This is driving me crazy!!

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11504 - Dominos

Post by andmej » Wed Oct 22, 2008 4:03 pm

Reduce the original graph to a DAG where each new node corresponds to a strongly connected component of the old graph.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

wjomlex
New poster
Posts: 13
Joined: Fri Dec 19, 2008 1:56 am

Re: 11504 - Dominos

Post by wjomlex » Tue Jan 27, 2009 8:46 pm

I'm getting RE, and I really don't see where that would be except in input formatting:

Code: Select all

import java.util.*;
import java.io.*;

public class Main
{
	static Node[] a;
	static StringTokenizer st;
	static BufferedReader scan;

	public static void main(String args[]) throws IOException
	{
		scan = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(scan.readLine());

		int t = get();

		for(int ca=0;ca < t;ca++)
		{
			int n = get();
			int k = get();

			a = new Node[n];

			for(int i=0;i < n;i++)
				a[i] = new Node();

			for(int i=0;i < k;i++)
			{
				int x = get() - 1;
				int y = get() - 1;
				
				a[x].s.push(y);
				a[y].start = false;
			}


			//process
			int rtn = 0;

			//scan for start
			for(int i=0;i < n;i++)
			{
				if(a[i].start)
				{
					rtn++;
					topple(i);
				}
			}

			//scan for cycles
			for(int i=0;i < n;i++)
			{
				if(!a[i].down)
				{
					rtn++;
					topple(i);
				}
			}

			System.out.println(rtn);
		}
	}

	public static void topple(int i)
	{
		if(a[i].down)
			return;

		a[i].down = true;

		while(!a[i].s.empty())
			topple(a[i].s.pop());
	}

	public static int get() throws IOException
	{
		while(!st.hasMoreTokens())
			st = new StringTokenizer(scan.readLine());

		return Integer.parseInt(st.nextToken());
	}
}



class Node
{
	public boolean start;
	public boolean down;
	public Stack<Integer> s;

	public Node()
	{
		start = true;
		down = false;
		s = new Stack<Integer>();
	}
}
I'm also getting RE for 11503... is there something funny with the input data formatting for these problems? I even changed my input function to skip blank lines and such.

wjomlex
New poster
Posts: 13
Joined: Fri Dec 19, 2008 1:56 am

Re: 11504 - Dominos

Post by wjomlex » Tue Jan 27, 2009 10:36 pm

I see I was just using too much stack space for the topple(i) method. I've changed it to a Stack implementation, and now I've improved from RE to WA. I'll have to redo my algorithm because it doesn't work on one of the Waterloo cases and I see why...

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11504 - Dominos

Post by Igor9669 » Sun May 17, 2009 2:18 pm

First I try to find scc(strongly connected components),with such algo:
1) Topologic sort(with dfs)
2) make graph inverse
3) dfs2 with inverse graph, this algo was written in Knuth's book, but it gived me wrang answer.
Then I don't inverse a graph and work with initial graph, this idea was right, and I got accepted!
Could somebody explain me why this was right idea????

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11504 - Dominos

Post by Obaida » Tue Feb 23, 2010 7:08 am

I got compile error for this problem...

Code: Select all

code.o: In function `DFS(int)':
code.cpp:(.text+0x47): relocation truncated to fit: R_X86_64_32S against symbol `visit' defined in .bss section in code.o
code.cpp:(.text+0x50): relocation truncated to fit: R_X86_64_32S against symbol `visit' defined in .bss section in code.o
code.o: In function `__tcf_1':
code.cpp:(.text+0x83): relocation truncated to fit: R_X86_64_PC32 against symbol `node' defined in .bss section in code.o
code.o: In function `__tcf_0':
code.cpp:(.text+0xa1): relocation truncated to fit: R_X86_64_32 against `.bss'
code.o: In function `__static_initialization_and_destruction_0(int, int)':
code.cpp:(.text+0xc9): relocation truncated to fit: R_X86_64_32 against `.bss'
code.cpp:(.text+0xe6): relocation truncated to fit: R_X86_64_PC32 against symbol `node' defined in .bss section in code.o
code.cpp:(.text+0xf1): relocation truncated to fit: R_X86_64_PC32 against symbol `node' defined in .bss section in code.o
code.cpp:(.text+0x101): relocation truncated to fit: R_X86_64_PC32 against symbol `node' defined in .bss section in code.o
code.o: In function `Topo_Sort(int)':
code.cpp:(.text+0x181): relocation truncated to fit: R_X86_64_32S against symbol `visit' defined in .bss section in code.o
code.cpp:(.text+0x18a): relocation truncated to fit: R_X86_64_32S against symbol `visit' defined in .bss section in code.o
code.cpp:(.text+0x1a3): additional relocation overflows omitted from the output
collect2: ld returned 1 exit status
someone please help me out. Here is my code:-

Code: Select all

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

struct pair{
	int l[100002],size;
}list[100002];

bool visit[100002];vector<int>node;

void Topo_Sort(int i){
	for(int j=0;j<list[i].size;j++){
		if(!visit[list[i].l[j]]){
			visit[list[i].l[j]]=1;
			Topo_Sort(list[i].l[j]);
		}
	}node.push_back(i);
}

void DFS(int i){
	for(int j=0;j<list[i].size;j++){
		if(!visit[list[i].l[j]]){
			visit[list[i].l[j]]=1;
			DFS(list[i].l[j]);
		}
	}
}

int main(){
	int t,i,a,b,m,n;scanf("%d",&t);
	while(t--){
		scanf("%d %d",&m,&n);int count=0;
		for(i=1;i<=m;i++){visit[i]=0;list[i].size=0;}
		for(i=0;i<n;i++){scanf("%d %d",&a,&b);list[a].l[list[a].size++]=b;}
		for(i=1;i<=m;i++){if(!visit[i]){visit[i]=1;Topo_Sort(i);}}
		for(i=1;i<=m;i++)visit[i]=0;
		for(i=node.size()-1;i>=0;i--){
			if(!visit[node[i]]){visit[node[i]]=1;DFS(node[i]);count++;}
		}printf("%d\n",count);node.erase(node.begin(),node.end());
	}
	return 0;
}
try_try_try_try_&&&_try@try.com
This may be the address of success.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 11504 - Dominos

Post by helloneo » Tue Feb 23, 2010 5:58 pm

I tried compiling your code and got this message.. :-)

Code: Select all

$ g++ 1.cpp -Wall
1.cpp:13: error: size of array 'list' is too large
1.cpp: In function 'void Topo_Sort(int)':
1.cpp:18: error: 'list' was not declared in this scope
1.cpp: In function 'void DFS(int)':
1.cpp:27: error: 'list' was not declared in this scope
1.cpp: In function 'int main()':
1.cpp:39: error: 'list' was not declared in this scope
1.cpp:40: error: 'list' was not declared in this scope
$ g++ --version
g++ (GCC) 4.2.4 (Ubuntu 4.2.4-1ubuntu3)
...

jimmyholand88
New poster
Posts: 1
Joined: Wed Nov 02, 2011 11:06 am

Re: 11504 - Dominos

Post by jimmyholand88 » Wed Nov 02, 2011 11:08 am

the dominos is very good hmmm this is a very nice info. :o

vpanait
New poster
Posts: 17
Joined: Sun Apr 01, 2012 11:01 am

Re: 11504 - Dominos

Post by vpanait » Thu Jul 19, 2012 3:55 pm

Some advice for solving this - use STL as rarely as possible, I lost some time just profiling and replacing stl to C functions, here is some profile for the main stages of the code (the values are taken with clock() function, and represent the difference between the indication of clock() at the beginning and the end of the stage):
1. initial profile (TLE) - using std::cin, std::stack, std::list
init time is 1981
top-sort time is 8066
conn-comp time is 1638

2. code that gotAC -
replaced std::cin -> scanf()
replaced std::stack, std::list -> used vectors
init time is 94
top-sort time is 47
conn-comp time is 15

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 11504 - Dominos

Post by mahade hasan » Wed Oct 10, 2012 7:34 pm

getting wrong ans help me plz.......

Code: Select all

#include<stdio.h>
#include<iostream>
#include<vector>
#include<stack>
#include<string.h>
using namespace std;
bool Visit[100009];
vector<long>V[100009];

int main()
{
   long I,K,L,M,N,Node,Relation,Test;
   scanf("%ld",&Test);
   
   while(Test--)
   {
      N=0;
      memset(Visit,0,sizeof(Visit));
      scanf("%ld %ld",&Node,&Relation);
      M=Node;
      while(M--) V[M].clear();
      while(Relation--)
      {
         scanf("%ld %ld",&I,&K);
         V[I].push_back(K);
         V[K].push_back(I);
      }
      stack<long>S;
      for(K=1;K<=Node;K++)
      if(Visit[K]==0)
      {
        S.push(K);
        Visit[K]=1;
        ++N;
        while(!S.empty())
        {
          M=S.top();
          S.pop();
          for(I=0;I<V[M].size();I++)
          {
          if(Visit[V[M][I]]==0)
          {
            Visit[V[M][I]]=1;
            S.push(V[M][I]);
            //break;
          }
         }
       }
      }
      printf("%d\n",N);
   }
   return 0;
}

[/color]
we r surrounded by happiness
need eyes to feel it!

Post Reply

Return to “Volume 115 (11500-11599)”