11770 - Lighting Away

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

Moderator: Board moderators

mukit
New poster
Posts: 48
Joined: Wed Nov 21, 2007 10:09 am
Location: Dhaka , Bangladesh
Contact:

11770 - Lighting Away

Post by mukit » Sun Jan 24, 2010 10:25 am

Code: Select all

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>

using namespace std;

#define sz 10010
#define VI vector<int>

//DONE

I made dfs taking maximum out-degree node first.
Is my approach OK?
Last edited by mukit on Sun Jan 24, 2010 4:30 pm, edited 1 time in total.

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

Re: WA in problem 11770

Post by Igor9669 » Sun Jan 24, 2010 12:23 pm

It is like scc!
Make a topologic order and then dfs!
Last edited by Igor9669 on Sun Jan 24, 2010 9:48 pm, edited 1 time in total.

mukit
New poster
Posts: 48
Joined: Wed Nov 21, 2007 10:09 am
Location: Dhaka , Bangladesh
Contact:

Re: WA in problem 11770

Post by mukit » Sun Jan 24, 2010 4:34 pm

thanks, Igor9669 :)

aliahmed
New poster
Posts: 24
Joined: Fri Oct 24, 2008 8:37 pm
Location: CUET, Chittagong, Bangladesh
Contact:

Re: WA in problem 11770

Post by aliahmed » Tue Jan 26, 2010 9:01 pm

My code accepted after using topological sort & dfs
thanx robot
Last edited by aliahmed on Mon Apr 05, 2010 1:01 am, edited 1 time in total.

paaulocezar
New poster
Posts: 5
Joined: Thu May 14, 2009 4:14 pm

Re: WA in problem 11770

Post by paaulocezar » Fri Jan 29, 2010 2:26 pm

I've tried to solve this one using two different approaches,

first one, finding the number of strongly connected components that don't have in-arcs from other scc;
and the other making kind of a topological sort, adding the vertices in a list as they're discovered in a dfs, then, each root of a tree in a dfs make following the order the vertices appear in the list is said to be one that need to be turn on.

but the two approaches are gettin' WA. some help ?

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

Re: WA in problem 11770

Post by Igor9669 » Fri Jan 29, 2010 3:06 pm

in scc you need a reversed graph,but here you dont't need it!

paaulocezar
New poster
Posts: 5
Joined: Thu May 14, 2009 4:14 pm

Re: WA in problem 11770

Post by paaulocezar » Fri Jan 29, 2010 6:17 pm

so it's like the second way i've tried to solve,
makin a topological sort then a dfs where each spanning tree root is a light that must be turn on..
like this..

Code: Select all

REMOVED AFTER AC;

@edit..
can't believe this, I was making the worst mistake ¬¬'
my output was..
printf("%d\n", answer );
instead of
printf("Case %d: %d\n", caseNum, answer );

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

Re: WA in problem 11770

Post by calicratis19 » Sat Feb 06, 2010 10:23 pm

I am getting wa in this.I am not sure if my process is ok. I used BFS.I color every node with bfs except the nodes which were the starting node of the bfs'.And then last i checked how many uncolored node is there. is it ok??

Code: Select all

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

int i,st,head,node,edge,y,x,test,kase,cur,tail;
int que[1000010];
bool flag[10010];

vector<int>adj[10001];
void BFS(int st)
{
	int i;

	head = tail = 0;
	que[tail++]=st;

	flag[st]=1;	

	while(head!=tail)
	{
		cur = que[head++];
		int	l=adj[cur].size();
		for(i=0;i<l;i++)
		{
			if(!flag[adj[cur][i]])
			{
				que[tail++] = adj[cur][i];
				flag[adj[cur][i]]=1;
			}
		}
	}
	flag[st]=0;	
}

int main()
{
	//freopen("in.txt","r",stdin);
//	freopen("b.txt","w",stdout);
	scanf("%d",&test);

	while(test--)
	{

		scanf("%d %d",&node,&edge);
		for(i=0;i<=node;i++)
		{
			adj[i].clear();flag[i]=0;
		}

		for(i=1;i<=edge;i++)
		{
			scanf("%d %d",&x,&y);
			adj[x].push_back(y);
		}

		for(i=1;i<=node;i++)
			if(!flag[i])
				BFS(i);

		st = 0;
		for(i=1;i<=node;i++)if(!flag[i])st++;

		printf("Case %d: %d\n",++kase,st);
		
	}
	return 0;
}
Last edited by calicratis19 on Sun Feb 07, 2010 9:11 pm, edited 1 time in total.
Heal The World

robot
New poster
Posts: 29
Joined: Sun May 24, 2009 8:39 pm

Re: WA in problem 11770

Post by robot » Sun Feb 07, 2010 8:29 am

calicratis19 wrote:I am getting wa in this.I am not sure if my process is ok. I used BFS.I color every node with bfs except the nodes which were the starting node of the bfs'.And then last i checked how many uncolored node is there. is it ok??

Code: Select all

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

int i,st,head,node,edge,y,x,test,kase,cur,tail;
int que[1000010];
bool flag[10010];

vector<int>adj[10001];
void BFS(int st)
{
	int i;
	head = tail = 0;

	que[tail++]=st;
	while(head!=tail)
	{
		cur = que[head++];
		int	l=adj[cur].size();
		for(i=0;i<l;i++)
		{
			if(!flag[adj[cur][i]] && adj[cur][i]!=st)
			{
				que[tail++] = adj[cur][i];
				flag[adj[cur][i]]=1;
			}
		}
	}
	
}

int main()
{
	scanf("%d",&test);
	while(test--)
	{

		scanf("%d %d",&node,&edge);
		for(i=0;i<=node;i++)
		{
			adj[i].clear();flag[i]=0;
		}

		for(i=1;i<=edge;i++)
		{
			scanf("%d %d",&x,&y);
			adj[x].push_back(y);
		}

		for(i=1;i<=node;i++)
			if(!flag[i])
				BFS(i);

		st = 0;
		for(i=1;i<=node;i++)if(!flag[i])st++;

		printf("Case %d: %d\n",++kase,st);
		
	}
	return 0;
}

Hi, calica...
try this input
1
7 8
1 4
4 3
3 1
2 1
2 5
5 2
6 5
7 3
output: 2

i think that u do topological sort concept, Ist u lighting the all zero indegree, then lighting the maxi outdegree, if outdegree and indegree are same u give priority the outdegree, then indegree or u can use vertex cover tecnique(SCC).
Last edited by robot on Sun Feb 07, 2010 9:39 pm, edited 1 time in total.

robot
New poster
Posts: 29
Joined: Sun May 24, 2009 8:39 pm

Re: WA in problem 11770

Post by robot » Sun Feb 07, 2010 8:38 am

aliahmed wrote:Getting WA?

#include<stdio.h>

long front,rear,f[10000],grid[10000][10000],ind[10000],q[100000],m,n,t,l,p[11000],a,b,visit[10000],c=0,cas=1;

void dfs(long k)
{
long u,l;
u=k;
for(l=1; l<p; l++)
{
if(!visit[grid[l]])
{
visit[grid[l]]=1;
//printf("%ld ",grid[l]);
dfs(grid[l]);
}
}
}

void t_sort()
{
long i,j;
front=1; rear=1;
for(i=1; i<=m; i++)
{

if(ind==0 && f==1)
{
q[rear++]=i;
visit=1;
}
}
l=rear;
for(i=1; i<=rear; i++)
{
for(j=1; j<=p[q[front]]; j++)
{
if(f[j]==1)
{
ind[grid[q[front]][j]]--;
if(ind[grid[q[front]][j]]==0)
q[rear++]=grid[q[front]][j];

}
}
front++;
}
c=0;
for(i=1; i<rear; i++)
{
if(visit[q]==0)
{
dfs(q);
c++;
}
}
printf("Case %ld: %ld\n",cas++,c);
}


int main()
{
long i,j;
scanf("%ld",&t);
while(t--)
{
scanf("%ld%ld",&m,&n);

for(i=1; i<=m; i++) {ind=0; p=1; f=0; visit=0;}

for(i=1; i<=n; i++)
{
scanf("%ld%ld",&a,&b);
grid[a][p[a]++]=b;
f[a]=1;
f=1;
ind++;
}
t_sort();
}

return 0;
}


Hi, aliahmed
try this input:
2
7 8
1 4
4 3
3 1
2 1
2 5
5 2
6 5
7 3
5 1
1 2
output:
Case 1: 2
Case 2: 4
u can do topological sort concept...
Last edited by robot on Sun Feb 07, 2010 9:42 pm, edited 1 time in total.

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

Re: WA in problem 11770

Post by calicratis19 » Sun Feb 07, 2010 8:59 am

@ robot My code works for your case.
and your case's output which you have given aliahmed is wrong.
Last edited by calicratis19 on Sun Feb 07, 2010 9:10 pm, edited 2 times in total.
Heal The World

robot
New poster
Posts: 29
Joined: Sun May 24, 2009 8:39 pm

Re: WA in problem 11770

Post by robot » Sun Feb 07, 2010 8:33 pm

robot wrote:
aliahmed wrote:Getting WA?

#include<stdio.h>

long front,rear,f[10000],grid[10000][10000],ind[10000],q[100000],m,n,t,l,p[11000],a,b,visit[10000],c=0,cas=1;

void dfs(long k)
{
long u,l;
u=k;
for(l=1; l<p; l++)
{
if(!visit[grid[l]])
{
visit[grid[l]]=1;
//printf("%ld ",grid[l]);
dfs(grid[l]);
}
}
}

void t_sort()
{
long i,j;
front=1; rear=1;
for(i=1; i<=m; i++)
{

if(ind==0 && f==1)
{
q[rear++]=i;
visit=1;
}
}
l=rear;
for(i=1; i<=rear; i++)
{
for(j=1; j<=p[q[front]]; j++)
{
if(f[j]==1)
{
ind[grid[q[front]][j]]--;
if(ind[grid[q[front]][j]]==0)
q[rear++]=grid[q[front]][j];

}
}
front++;
}
c=0;
for(i=1; i<rear; i++)
{
if(visit[q]==0)
{
dfs(q);
c++;
}
}
printf("Case %ld: %ld\n",cas++,c);
}


int main()
{
long i,j;
scanf("%ld",&t);
while(t--)
{
scanf("%ld%ld",&m,&n);

for(i=1; i<=m; i++) {ind=0; p=1; f=0; visit=0;}

for(i=1; i<=n; i++)
{
scanf("%ld%ld",&a,&b);
grid[a][p[a]++]=b;
f[a]=1;
f=1;
ind++;
}
t_sort();
}

return 0;
}


Hi, aliahmed
try this input:
1
5 1
1 2
output: 4
u can do topological sort concept...

Taman
New poster
Posts: 32
Joined: Sun Oct 11, 2009 8:59 pm
Location: Southeast University

Re: WA in problem 11770

Post by Taman » Tue Feb 16, 2010 11:34 pm

@calicratis19:
Well, you should try this case,
1
4 5
1 2
2 1
2 3
3 2
4 2

The output should be 1, where your code prints 2. . .
Hope it helps :)

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: WA in problem 11770

Post by arifcsecu » Sat Feb 20, 2010 12:45 pm

My approach is something as like as Robot.

Algorithm:
1. run dfs for every zero in-degree vertex
and count all zero in-degree vertex.
2. run dfs for maximum out-degree vertex ( if it has not visited yet and increase the counter)

3. run dfs for all vertices which has not visited yet and increase the counter.

Test Case:
1
8 6
2 8
8 7
7 2
3 6
6 4
4 3

Output:
Case 1: 4
Try to catch fish rather than asking for some fishes.

shaon3343
New poster
Posts: 2
Joined: Wed Nov 04, 2009 7:27 am
Location: CSE-CU
Contact:

Re: WA in problem 11770

Post by shaon3343 » Sat Feb 27, 2010 6:45 am

I got accepted!! :D :D
can anyone find me same type of problem from other volume?
An eye for an eye makes the whole world blind !!

Post Reply

Return to “Volume 117 (11700-11799)”