988 - Many Paths, One Destination

All about problems in Volume 9. 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
..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

988 - Many Paths, One Destination

Post by .. » Sun Nov 26, 2006 5:59 pm

Could anyone tell me what this means??

This number will always be less than 2 to the 30th.


By the way, the answer will always >= 1, right?
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

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

Post by sohel » Sun Nov 26, 2006 6:26 pm

This number will always be less than 2 to the 30th.

I interpreted, "this number will be less than 2^30", not sure though... :-?

Yes, answer will always be atleast 1, since we all have to die some day :( , so there is atleast one path.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sun Nov 26, 2006 6:57 pm

Thanks :D
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sun Nov 26, 2006 8:19 pm

This number will always be less than 2 to the 30th.
That sentece is a direct translation, and its meaning is 2^30. ALthough i think that translation is not correct.

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

getting WA

Post by shihabrc » Tue May 22, 2007 10:25 pm

a simple graph problem. but getting wa. i don no why. plz somebody provide some suggetions, i/o.

Code: Select all

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

using namespace std;

#define MAXN 1000

vector <int> adj[MAXN];
int path[MAXN];
bool visited[MAXN];
int v;

int BFS()
{
	int i,u,next,ret = 0;
	queue <int> Q;

	Q.push(0);
	memset(visited,false,sizeof(visited));
	memset(path,0,sizeof(path));
	visited[0] = true;
	path[0] = 1;

	while(!Q.empty())
	{
		for( u = Q.front(),Q.pop(),i = 0; i < adj[u].size(); i++ )
		{
			next = adj[u][i];
			if( !visited[next] )
			{
				visited[next] = true;
				path[next] = path[u];
				Q.push(next);
			}
			else path[next] += path[u];
		}
	}

	for( i = 0; i < v; i++ ) if( adj[i].size() == 0 ) ret += path[i];
	return ret;
}


int main()
{
	int i,j,n,kase = 0,u;

	while(scanf("%d",&v) == 1)
	{
		kase++;
		if( kase > 1 ) putchar('\n');

		for( i = 0; i < v; i++ )
		{
			adj[i].clear();

			scanf("%d",&n);

			for( j = 0; j < n; j++ ) 
			{
				scanf("%d",&u);
				adj[i].push_back(u);
			}
		}

		printf("%d\n",BFS());
	}

	return 0;
}

Shihab
CSE,BUET

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Thu Jul 05, 2007 6:04 pm

Can anybody tell me what is the limit of n ? And I think it is a dp problem, am I right ?

EDIT : ACC... :) The one for sure is that n < 15000. And yes, it is kind of a dp problem ( at least I solved it that way).

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Problem explanation...

Post by nymo » Mon Aug 06, 2007 11:00 am

Can somebody please explain what this problem asks for? I can not get the sample I/O... any explatation is welcome.
regards,
nymo

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 988 - Many paths, one destination

Post by Shafaet_du » Mon Jun 06, 2011 9:52 pm

Explanation to sample input:
6
3 1 2 5
3 2 3 4
2 3 4
0
1 5
0
This means from event 0 you can go to event 1,2,5. from event 1 you can go to event 2,3,4. You need to determine the number of ways you can go to event of death(event that have no choices).

You can see it becomes an DAG if you draw the choices on paper. Just count the number of all possible paths using dp.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Re: 988 - Many paths, one destination

Post by nymo » Thu Jun 30, 2011 2:39 pm

Thanks, Shafaet...
I thought last event is the event of death... that's why I couldn't get 7 as the ans :) Now, I read the problem statement again and got the idea that more than one event can be counted as death... will try to solve it soon.
regards,
nymo

anando_du
New poster
Posts: 10
Joined: Sun Mar 01, 2015 3:11 pm

Re: 988 - Many Paths, One Destination

Post by anando_du » Mon Jan 11, 2016 7:18 am

I think Input provided by SADIQ(AIUB) in udebug is not in correct form . Please remove that kind of incorrect input.

Code: Select all

3
2 1 2
0
0
4
2 1 2
0
0
3 2
3
5
2 1 2
1 3
1 4
0
0
0
5
2 1 2
1 3
1 4
3 4
0
take a look carefully .. The last 3 inputs are incorrect .

Post Reply

Return to “Volume 9 (900-999)”