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 .. »

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.

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

Post by sohel »

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 .. »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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)”