657 - The die is cast

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

Moderator: Board moderators

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 657 - The die is cast

Post by sohel » Tue Apr 28, 2009 10:51 am

The quoted part of your post is pretty obvious! Which part are you having trouble with?

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 657 - The die is cast

Post by calicratis19 » Wed Apr 29, 2009 9:24 am

The quoted part of your post is pretty obvious! Which part are you having trouble with?
thnx. reading ur post i thought if its ovious why cant i understand.. :o :o :o :o :o . then i read carefully again and again and i understood. :D :D :D :D


but there r still some confusion :( :(
A set S of pixels is connected if for every pair (a,b) of pixels in S, there is a sequence a1, a2, ...., ak in S such that a = a1 and b = ak
does that mean if input is a 5X5 grid, then pixel (1,1) and pixel (1,5) are connected?? im confused with the statement a=a1 and b=ak. sorry for the trouble.
Heal The World

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 657 - The die is cast

Post by sohel » Wed Apr 29, 2009 11:00 am

Lets consider the case with a die:
For the 5x5 grid, (1,1) and (1,5) are connected if you can reach (1,5) from (1,1) by visiting only non-background pixels.

Example 1

Code: Select all

*.***
***..
.....
.....
.....
Example 2

Code: Select all

*.***
.....
.....
.....
.....
For the first case, (1,1) is connected to (1,5) but not for the 2nd case.
Hope it's clear.

Hints: Basically, we need to apply flood-fill to find connected components.

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 657 - The die is cast

Post by calicratis19 » Wed Apr 29, 2009 12:08 pm

i got it thnxs :lol: :lol: . but i think in the problem statement it is unnecessary to give that line.making the statement confusing. because before it was written that
. We consider two pixels connected if they share an edge - meeting at a corner is not enough
anyone can understand frm this line which pixels r connected. :evil: :evil:
thnxs again.
Heal The World

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 657 - The die is cast

Post by mf » Wed Apr 29, 2009 12:41 pm

sohel wrote:For the first case, (1,1) is connected to (1,5)
Actually, no. They are not connected, but instead they are part of a same connected set of pixels (i.e. indirectly connected)


calicratis19 wrote:i got it thnxs :lol: :lol: . but i think in the problem statement it is unnecessary to give that line.making the statement confusing. because before it was written that
. We consider two pixels connected if they share an edge - meeting at a corner is not enough
I don't see any problems with the problem statement at all, it's pretty clear.

Two pixels are connected iff they share an edge.

And the following is basically a textbook definition of a connectedness in a graph, where vertices are pixels and edges represent pairs of connected pixels:
A set $S$ of pixels is connected if for every pair $(a,b)$ of pixels in $S$, there is a sequence $a_1, a_2, \dots, a_k$ in $S$ such that $a = a_1$ and $b = a_k$, and $a_i$ and $a_{i+1}$ are connected for $1 \le i < k$.
There's another way to define connected components - via equivalence relations - but it's even more verbose.

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 657 - The die is cast

Post by calicratis19 » Wed Apr 29, 2009 1:27 pm

u misunderstood me.
We consider two pixels connected if they share an edge - meeting at a corner is not enough.
i understood this line pretty well. but i couldnt understood the line
A set S of pixels is connected if for every pair (a,b) of pixels in S, there is a sequence a1, a2, ...., ak in S such that a = a1 and b = ak ,
and i think this line is unncessary because the first line says it all.
Heal The World

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 657 - The die is cast

Post by mf » Wed Apr 29, 2009 2:41 pm

I don't see why it's unnecessary. It defines the concept of 'connected set of pixels', which is then used to define what 'dice' and 'dot' mean. And as counting these objects is the subject of this problem, you have to define them somehow... This problem's author chose to do a in a "mathy" way.
calicratis19 wrote:i understood this line pretty well. but i couldnt understood the line
A set S of pixels is connected if for every pair (a,b) of pixels in S, there is a sequence a1, a2, ...., ak in S such that a = a1 and b = ak ,
Read more math books, and you'd get used to a language like that :)

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 657 - The die is cast

Post by calicratis19 » Thu Apr 30, 2009 10:00 am

thanks to sohel bhai and mf for explaining the problem. i got ac without wa ..:D :D :D :D
Heal The World

asif_khan_ak_07
New poster
Posts: 25
Joined: Fri Apr 17, 2009 8:24 am

Re: 657 - The die is cast

Post by asif_khan_ak_07 » Sun Nov 08, 2009 4:21 pm

why WA??

Code: Select all

#include<stdio.h>
#include<queue>
#include<algorithm>
#define MAX 60
using namespace std;
queue<int>row;
queue<int>column;
queue<int>r;
queue<int>c;
char path[MAX][MAX];
int fg[MAX][MAX];
int n,m;
int rw[5]={0,-1,1,0,0};
int col[5]={0,0,0,-1,1};
int ans[MAX];

void play(int u,int v){
	int nr,nc,ro,co;
	row.push(u);
	column.push(v);
	fg[u][v]=1;
	while(!row.empty()){
		ro=row.front();
		co=column.front();
		row.pop();
		column.pop();
		for(int i=0;i<5;i++){
			nr=ro+rw[i];
			nc=co+col[i];
			if(path[nr][nc]=='X' && fg[nr][nc]==0 && nr<m && nc>=0 && nc<n){
				row.push(nr);
				column.push(nc);
				fg[nr][nc]=1;
			}
		
			else if(path[nr][nc]=='*' && fg[nr][nc]==0 && nr<m && nc>=0 && nc<n){
				r.push(nr);
				c.push(nc);
				fg[nr][nc]=1;
			}
		
		
		}
	}

}


int ffill(int u,int v){
	int nr,nc,ro,co,count;
	r.push(u);
	c.push(v);
	count=0;
	while(!r.empty()){
		ro=r.front();
		co=c.front();
		r.pop();
		c.pop();
		for(int i=0;i<5;i++){
			nr=ro+rw[i];
			nc=co+col[i];
			if(path[nr][nc]=='X' && fg[nr][nc]==0){
			//	printf("%d %d\n",nr,nc);
				play(nr,nc);
				count++;
				r.push(nr);
				c.push(nc);
			}
		
			else if(path[nr][nc]=='*' && fg[nr][nc]==0 && nr<m && nc>=0 && nc<n){
				r.push(nr);
				c.push(nc);
				fg[nr][nc]=1;
			}
		
		
		}
	}


	return count;	

}

void unvisit(){
	for(int i=0;i<MAX;i++){
		for(int j=0;j<MAX;j++){
			path[i][j]='$';
			fg[i][j]=0;
		}
	}
}

int main(){
//	freopen("a.txt","r",stdin);
	int ns,x=1,gap;
	while(scanf("%d %d\n",&n,&m)==2){
		if(n==0 && m==0)
			break;
		unvisit();
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++)
				scanf("%c",&path[i][j]);
			scanf("%*c");
		}

		ns=0;
		for(int k=0;k<m;k++){
			for(int z=0;z<n;z++)
				if((path[k][z]=='*' || path[k][z]=='X') && fg[k][z]==0 && k>=0 && k<m && z>=0 && z<n){
				//	printf("%d %d\n",k,z);
					ans[ns++]=ffill(k,z);
				
					
				}
		}
		

		sort(ans,ans+ns);
		gap=0;
		printf("Throw %d:\n",x++);
		for(int l=0;l<ns;l++){
			if(ans[l]==0)
				continue;
			if(gap++)
				printf(" ");
			printf("%d",ans[l]);
		}

		printf("\n\n");

	}
	return 0;
}

mostafa_angel
New poster
Posts: 23
Joined: Sun Oct 04, 2009 12:03 pm

Re: 657 - The die is cast

Post by mostafa_angel » Wed Nov 18, 2009 1:30 pm

please help me !!
I really confused and I dont know why i got WA !?
my code :

Code: Select all

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector <string> inp;
vector <int> res;
int cnt;
int n , m;
bool mark[60][60];
void dfsx(int r , int c);

void dfs(int r , int c)
{
	if(inp[r][c] == '*')
		mark[r][c] = true;
	for(int i = r-1 ; i <= r+1 ; i++)
		for(int j = c-1 ; j <= c+1 ; j++)
			if(i >= 0 && j >= 0 && i < m && j < n )
			{
				if(inp[i][j] == '*' && mark[i][j] == false)
					dfs(i , j);
				else if(inp[i][j] == 'X' && mark[i][j] == false)
				{
					//cout << "x = " << i  << " " << j << endl; 
					cnt++;
					dfsx(i , j);
				}
			}
}

void dfsx(int r , int c)
{
	vector <pair <int , int> > d;
	pair <int , int> tmp;
	//cout << "x = " << r  << " " << c << endl; 
	mark[r][c] = true;
	bool xx = false;
	for(int i = r-1 ; i <= r+1 ; i++)
		for(int j = c-1 ; j <= c+1 ; j++)
	//for(int j = c-1 ; j <= c+1 ; j++)
	//	for(int i = r-1 ; i <= r+1 ; i++)
			if(i >= 0 && j >= 0 && i < m && j < n )
				if(i == r || j == c)
				{
					if(inp[i][j] == 'X' && mark[i][j] == false)
					{
						xx = true;
						//cnt--;
						dfsx(i , j);
					}
					if(inp[i][j] == '*' && mark[i][j] == false)
					{
						tmp.first = i;
						tmp.second = j;
						d.push_back(tmp);
					}
				}
	//if(!xx)
	//{
		for(int i = 0 ; i < d.size() ; i++)
			if(mark[d[i].first][d[i].second] == false)
			{
				dfs(d[i].first , d[i].second);
			}
	//}
}  

int main()
{
	//freopen("data.in" , "r" , stdin);
	string line;
	int cn = 1;
	while(cin >> n >> m && n || m)
	{
		getline(cin , line);
		memset(mark , false , sizeof mark);
		inp.clear();
		res.clear();
		for(int i = 0 ; i < m ; i++)
		{
			getline(cin , line);
			inp.push_back(line);
		}

		for(int i = 0 ; i < inp.size() ;i++)
			for(int j = 0 ; j < inp[i].size() ; j++)
			{
				if((inp[i][j] == '*' || inp[i][j] == 'X') && mark[i][j] == false)
				{
					//cout << "start = " << i << " " << j << endl;
					dfs(i , j);
					res.push_back(cnt);
					cnt = 0;
				}
			}

			sort(res.begin() , res.end());
			cout << "Throw " << cn++ << endl;
			for(int i = 0 ; i < res.size() ; i++)
			{
				if(i > 0)
					cout << " ";
				cout << res[i];
			}
			cout << endl << endl;
	}

	return 0;
}

prasanjit barua
New poster
Posts: 2
Joined: Sat Oct 03, 2009 3:03 pm

Re: 657 - The die is cast

Post by prasanjit barua » Wed Nov 18, 2009 4:56 pm

Though the description says "The picture will contain at least one die, and the numbers of dots per die is between 1 and 6, inclusive. ",bt thre is a case like this:
4 4
****
****
****
****
fr which ur code says
throw#
0
bt ans will be
throw#

just a blank line .try this..

mostafa_angel
New poster
Posts: 23
Joined: Sun Oct 04, 2009 12:03 pm

Re: 657 - The die is cast

Post by mostafa_angel » Wed Nov 18, 2009 6:01 pm

prasanjit barua wrote:Though the description says "The picture will contain at least one die, and the numbers of dots per die is between 1 and 6, inclusive. ",bt thre is a case like this:
4 4
****
****
****
****
fr which ur code says
throw#
0
bt ans will be
throw#

just a blank line .try this..
I fix that problem dude...
but again I got WA... :(

Code: Select all

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector <string> inp;
vector <int> res;
int cnt;
int n , m;
bool mark[60][60];
void dfsx(int r , int c);

void dfs(int r , int c)
{
	if(inp[r][c] == '*')
		mark[r][c] = true;
	for(int i = r-1 ; i <= r+1 ; i++)
		for(int j = c-1 ; j <= c+1 ; j++)
			if(i >= 0 && j >= 0 && i < m && j < n )
			{
				if(inp[i][j] == '*' && mark[i][j] == false)
					dfs(i , j);
				else if(inp[i][j] == 'X' && mark[i][j] == false)
				{
					//cout << "x = " << i  << " " << j << endl; 
					cnt++;
					dfsx(i , j);
				}
			}
}

void dfsx(int r , int c)
{
	vector <pair <int , int> > d;
	pair <int , int> tmp;
	//cout << "x = " << r  << " " << c << endl; 
	mark[r][c] = true;
	bool xx = false;
	for(int i = r-1 ; i <= r+1 ; i++)
		for(int j = c-1 ; j <= c+1 ; j++)
	//for(int j = c-1 ; j <= c+1 ; j++)
	//	for(int i = r-1 ; i <= r+1 ; i++)
			if(i >= 0 && j >= 0 && i < m && j < n )
				if(i == r || j == c)
				{
					if(inp[i][j] == 'X' && mark[i][j] == false)
					{
						xx = true;
						//cnt--;
						dfsx(i , j);
					}
					if(inp[i][j] == '*' && mark[i][j] == false)
					{
						tmp.first = i;
						tmp.second = j;
						d.push_back(tmp);
					}
				}
	//if(!xx)
	//{
		for(int i = 0 ; i < d.size() ; i++)
			if(mark[d[i].first][d[i].second] == false)
			{
				dfs(d[i].first , d[i].second);
			}
	//}
}  

int main()
{
	//freopen("data.in" , "r" , stdin);
	string line;
	int cn = 1;
	while(cin >> n >> m && n || m)
	{
		getline(cin , line);
		memset(mark , false , sizeof mark);
		inp.clear();
		res.clear();
		for(int i = 0 ; i < m ; i++)
		{
			getline(cin , line);
			inp.push_back(line);
		}

		for(int i = 0 ; i < inp.size() ;i++)
			for(int j = 0 ; j < inp[i].size() ; j++)
			{
				if((inp[i][j] == '*' || inp[i][j] == 'X') && mark[i][j] == false)
				{
					//cout << "start = " << i << " " << j << endl;
					dfs(i , j);
					if(cnt > 0)
					{
						res.push_back(cnt);
						cnt = 0;
					}
				}
			}

			sort(res.begin() , res.end());
			cout << "Throw " << cn++ << endl;
			for(int i = 0 ; i < res.size() ; i++)
			{
				if(i > 0)
					cout << " ";
				cout << res[i];
			}
			cout << endl << endl;
	}

	return 0;
}

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 657 - The die is cast

Post by zobayer » Mon Jan 31, 2011 12:30 am

prasanjit barua wrote:Though the description says "The picture will contain at least one die, and the numbers of dots per die is between 1 and 6, inclusive. ",bt thre is a case like this:
4 4
****
****
****
****
fr which ur code says
throw#
0
bt ans will be
throw#

just a blank line .try this..
Actually you are wrong, there is no such cases.
Also the first test case in this thread is wrong.
You should not always say what you know, but you should always know what you say.

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 657 - The die is cast

Post by zobayer » Mon Jan 31, 2011 12:39 am

mostafa_angel wrote:
prasanjit barua wrote:Though the description says "The picture will contain at least one die, and the numbers of dots per die is between 1 and 6, inclusive. ",bt thre is a case like this:
4 4
****
****
****
****
fr which ur code says
throw#
0
bt ans will be
throw#

just a blank line .try this..
I fix that problem dude...
but again I got WA... :(
Try these cases:
[Note: there is no such case where you don't print anything, still I added that to show my AC output]

Code: Select all

5 5
*.***
***..
.....
.....
.....
5 5
XXX*X
XXX*X
.....
X***X
XX***
10 5
..........
..X**.*X..
..........
...*X*X...
..........
10 5
..........
..X....X..
..........
...*X*X...
..........
10 5
..........
..X....X..
..X....X..
..XXXXXX..
..........
10 5
..........
..X*X.....
..*X*.....
..X*X.....
..........
10 5
..........
..X*X.....
..*X**....
..X*X*....
..........
5 5
XXXXX
XXXXX
XXXXX
XXXXX
XXXXX
30 15
..............................
..............................
...............*..............
...*****......****............
...*X***.....**X***...........
...*****....***X**............
...***X*.....****.............
...*****.......*..............
..............................
........***........******.....
.......**X****.....*X**X*.....
......*******......******.....
.....****X**.......*X**X*.....
........***........******.....
..............................
10 6
..........
.XXX......
....XXX...
.......XXX
....XXX...
*X*X......
6 6
XXXXX*
.....X
.....X
.....X
.....X
.....X
6 6
XXXXX.
.....X
.....X
.....X
.....X
.....X
6 6
XXXXX.
....*X
.....X
.....X
.....X
.....X
30 15
.....X*X*X*X*X*X***...........
.X......................X.....
...............*.........X....
...X****......****........X...
...*X*.*.....**X***X..........
...*.X......***X**.....XXX....
...*.*X*.....****........X....
...***.X.......*.........X....
..............................
.......X***.............*..***
......******X****.....*X**X*..
..***********......**.*.*.....
.....****X**.......*X**X*.....
........***........*....*.....
........***.********..........
0 0

Code: Select all

Throw 1
0

Throw 2
2 2

Throw 3
1 1 2

Throw 4
1 1 2

Throw 5
1

Throw 6
5

Throw 7
5

Throw 8
1

Throw 9
1 2 2 4

Throw 10
1 1 1 1 2

Throw 11
2

Throw 12
1 1

Throw 13
2

Throw 14
1 1 1 1 1 2 3 4 5 6


[Note: There is a blank line after each case]

Hope these help.... :)
You should not always say what you know, but you should always know what you say.

Ratul Ahmed
New poster
Posts: 4
Joined: Mon Aug 30, 2010 3:40 am

WA 657 why?

Post by Ratul Ahmed » Fri Feb 11, 2011 8:57 am

i use 2 simple DFSs for '*' and 'X'.I've passed all the inputs of board.can anybody give me more critical inputs?
Here is my code....

Code: Select all


#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

#define MAX 60
char a[MAX][MAX];


bool print(long M,long N)
        {long I,J;
            for(I=0;I<=M+1;I++)
            {
                for(J=0;J<=N+1;J++)
                    printf("%c",a[I][J]);
                printf("\n");
            }
            printf("\n");
            return 1;
        }


class DFS
{
        long count;

    public:

        vector<long> V;

        bool DFS_cross(long I,long J)
        {
            a[I][J]='.';
        //UP
            if( a[I-1][J]=='X' )
            {
                DFS_cross(I-1,J);
                //count++;
            }
            else if( a[I-1][J]=='*' )
            {
                DFS_star(I-1,J);
            }
        //DOWN
            if( a[I+1][J]=='X' )
            {
                DFS_cross(I+1,J);
                //count++;
            }
            else if( a[I+1][J]=='*' )
            {
                DFS_star(I+1,J);
            }
        //LEFT
            if( a[I][J-1]=='X' )
            {
                DFS_cross(I,J-1);
                //count++;
            }
            else if( a[I][J-1]=='*' )
            {
                DFS_star(I,J-1);
            }
        //RIGHT
            if( a[I][J+1]=='X' )
            {
                DFS_cross(I,J+1);
                //count++;
            }
            else if( a[I][J+1]=='*' )
            {
                DFS_star(I,J+1);
            }

            return 1;
        }

        bool DFS_star(long I,long J)
        {
            a[I][J]='.';
        //UP
            if( a[I-1][J]=='X' )
            {
                DFS_cross(I-1,J);
                count++;
            }
            else if( a[I-1][J]=='*' )
            {
                DFS_star(I-1,J);
            }
        //DOWN
            if( a[I+1][J]=='X' )
            {
                DFS_cross(I+1,J);
                count++;
            }
            else if( a[I+1][J]=='*' )
            {
                DFS_star(I+1,J);
            }
        //LEFT
            if( a[I][J-1]=='X' )
            {
                DFS_cross(I,J-1);
                count++;
            }
            else if( a[I][J-1]=='*' )
            {
                DFS_star(I,J-1);
            }
        //RIGHT
            if( a[I][J+1]=='X' )
            {
                DFS_cross(I,J+1);
                count++;
            }
            else if( a[I][J+1]=='*' )
            {
                DFS_star(I,J+1);
            }

            return 1;
        }

        DFS(long M,long N)
        {
            long I,J;

            for(I=1;I<=M;I++)
            {
                for(J=1;J<=N;J++)
                {
                    if( a[I][J]=='*' )
                    {
                        count=0;
                        DFS_star(I,J);
                        V.push_back(count);
                        //print(M,N);
                        //printf("%ld *> %ld\n",V.size(),count);
                    }
                    else if( a[I][J]=='X' )
                    {
                        count=1;
                        DFS_cross(I,J);
                        V.push_back(count);
                        //print(M,N);
                        //printf("%ld X> %ld\n",V.size(),count);
                    }

                }
            }
        }
};

class INPUT
{
        long I,J;

    public:

        INPUT(long M,long N)
        {
            for(I=1;I<=M;I++)
            {
                J=1;
                while( (a[I][J]=getchar())!='\n' )
                {
                    J++;
                }
                a[I][J]='.';
                //printf("%ld_%ld\n",I,J);
            }
            for(J=0;J<=N+1;J++)
                a[I][J]='.';

            //print(M,N);
        }
};


class TEST
{
        long I,row,col,T,size;

    public:

        TEST()
        {
            for(I=0;I<MAX;I++)
            {
                a[I][0]='.';
                a[0][I]='.';
            }

            T=0;
            while( scanf("%ld %ld",&col,&row)==2 && row && col )
            {
                getchar();
                //printf("%ld_%ld\n",M,N);
                INPUT B(row,col);
                DFS C(row,col);

                T++;
                size=C.V.size();
                sort(C.V.begin(), C.V.end());
                printf("Throw %ld\n",T);
                for(I=0; I<size-1 ;I++)
                {
                    //printf("->%ld %ld ",I,C.V.size()-1);
                    if( C.V[I] )
                        printf("%ld ",C.V[I]);
                }
                if( size )
                {
                    if( C.V[I] )
                        printf("%ld\n\n",C.V[I]);
                    else
                        printf("\n\n");
                }
                else
                {
                    printf("\n\n");
                }
            }
        }
};


int main()
{
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
*/
    TEST A;

    return 0;
}


Post Reply

Return to “Volume 6 (600-699)”