11550 - Demanding Dilemma

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

Post Reply
rij
New poster
Posts: 5
Joined: Mon Nov 03, 2008 3:59 am
Location: BD
Contact:

11550 - Demanding Dilemma

Post by rij » Mon Nov 03, 2008 4:05 am

pls give me some test cases.i m getting wa.
heres my code

Code: Select all


Last edited by rij on Tue Nov 04, 2008 11:48 am, edited 1 time in total.

zhouerjin
New poster
Posts: 5
Joined: Wed Oct 01, 2008 4:52 pm

Re: 11550 - Demanding Dilemma

Post by zhouerjin » Mon Nov 03, 2008 2:27 pm

I WA too...-_-!
but I can't understand your code on:if(arr[j]=='1'&& i!=j)count++;
why do you check if i!=j? I think it doesn't need...

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Re: 11550 - Demanding Dilemma

Post by mmonish » Mon Nov 03, 2008 2:54 pm

try this case
Input:

Code: Select all

1
3 2
1 1
1 0
0 1
My AC output:

Code: Select all

Yes
hope this helps..

rij
New poster
Posts: 5
Joined: Mon Nov 03, 2008 3:59 am
Location: BD
Contact:

Re: 11550 - Demanding Dilemma

Post by rij » Mon Nov 03, 2008 7:39 pm

corrected but still wa

Code: Select all

void call(int n,int m){
		int count=0,fc=0;
		for(int j=0;j<m;j++){
			count=0;
			for(int i=0;i<n;i++){
				if(arr[i][j]=='1')count++;
			}
			if(count==2)
				fc++;
		}
		if(fc==m)
			cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
		return;
}

Vytenis
New poster
Posts: 7
Joined: Mon Aug 04, 2008 8:16 pm

Re: 11550 - Demanding Dilemma

Post by Vytenis » Mon Nov 03, 2008 7:45 pm

You must also check if there are no two identical edges defined by the incidence matrix. If there are, you should return "No".

rij
New poster
Posts: 5
Joined: Mon Nov 03, 2008 3:59 am
Location: BD
Contact:

Re: 11550 - Demanding Dilemma

Post by rij » Tue Nov 04, 2008 11:49 am

thanks got ac after a number of tries.

zhouerjin
New poster
Posts: 5
Joined: Wed Oct 01, 2008 4:52 pm

Re: 11550 - Demanding Dilemma

Post by zhouerjin » Wed Nov 05, 2008 6:34 am

rij wrote:thanks got ac after a number of tries.
can you say more detail?
I still WA...

SerailHydra
New poster
Posts: 20
Joined: Mon Oct 20, 2008 6:26 am

Re: 11550 - Demanding Dilemma

Post by SerailHydra » Wed Nov 05, 2008 8:12 am

The graph should be a simple indirected one.

Pay attention to the word 'simple'.

zhouerjin
New poster
Posts: 5
Joined: Wed Oct 01, 2008 4:52 pm

Re: 11550 - Demanding Dilemma

Post by zhouerjin » Thu Nov 06, 2008 6:23 am

I still WA....I need help...

Code: Select all

void prepare()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++)
		flag[i][j]=false;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
		scanf("%d",&map[i][j]);
}

bool work()
{
	for (int i=1;i<=m;i++)
	{
		int u=-1,v=-1;
		for (int j=1;j<=n;j++)
		if (map[j][i])
		{
			if (u==-1) u=j;else 
			if (v!=-1) return false;else v=j;
		}
		if (u*v<0) return false;
		if (flag[u][v]) return false;
		flag[u][v]=flag[v][u]=true;
	}
	return true;
}

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

Re: 11550 - Demanding Dilemma

Post by shakil » Thu Jan 14, 2010 6:21 pm

To : zhouerjin
Change only one line & i hope that will make you AC.

Code: Select all

if (u*v<0) return false;
change to ->

Code: Select all

if (u==-1||v==-1) return false;
Because if u & v two are -1 then u*v>0
SHAKIL

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm
Location: Chittagong, Bangladesh

Re: 11550 - Demanding Dilemma

Post by @li_kuet » Fri Aug 17, 2012 4:31 am

This is a very simple problem.
Just check if every column(edge) has exactly two vertex and no two columns(edges) has same vertexes(Because multiple edges are not allowed) :)
You can try this Cases :-?
Input :

Code: Select all

3

3 3
1 1 0
1 1 1
1 0 0

2 2
1 1
1 1

3 3
1 0 0
1 1 1
0 1 1
Output :

Code: Select all

No
No
No
In 1st case first column(edge) has three vertex which is not possible
In 2nd case 1st and 2nd edges have the same vertexes (1,2) and (1,2) so again No
In 3rd case same thing occurs like 2nd case.Here 2nd and 3rd edges have the same vertexes (2,3) and (2,3)

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

Re: 11550 - Demanding Dilemma

Post by brianfry713 » Tue Dec 11, 2012 9:26 am

input

Code: Select all

1
4 3
1 1 1
1 0 0
0 1 0
0 0 0
output No
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 11550 - Demanding Dilemma

Post by uDebug » Thu Apr 16, 2015 1:01 pm

Added some input to help with testing / debugging here:

http://www.udebug.com/UVa/11550
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 115 (11500-11599)”