10039 - Railroads

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

Moderator: Board moderators

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

10039 - Railroads

Post by Red Scorpion » Wed Jun 25, 2003 7:52 am

Hi, I try to solve this problem but I really dont understand the input.

2 ->number of scenario
3 ->number of city
Hamburg
Frankfurt
Darmstadt
3 ->number of train
2 ->number of city.
0949 Hamburg
1006 Frankfurt
2
1325 Hamburg
1550 Darmstadt
2
1205 Frankfurt
1411 Darmstadt
0800
Hamburg
Darmstadt

When number of city > 2, what happen ?
3
0949 Hamburg
1006 Frankfurt
0800 London
ti more lines with a time and a city name, meaning that passengers can get on or off the train at that time at that city.
Please help me...

:lol: :lol:

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Fri Jul 11, 2003 7:56 am

I still don't understand ... Can anyone help ... ?

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Re: 10039 - don't understand the input ...

Post by LittleJohn » Fri Jul 11, 2003 1:26 pm

Red Scorpion wrote:When number of city > 2, what happen ?
3
0949 Hamburg
1006 Frankfurt
0800 London
Hi, it's a schedule of train ti.
It means train ti will start at Hamburg at 9:49, and arrive Frankfurt at 10:06, and then London (8:00?!)...something like that..

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

Post by carneiro » Mon Oct 06, 2003 4:35 am

Does anybody have a NICE input for this problem ?

I'm tired of getting non-sense WAs :-)

I've tried everything I could think of .. but still WA
[]s
Mauricio Oliveira Carneiro

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

Hundreds of TLEs

Post by BiK » Wed Nov 12, 2003 6:35 pm

I keep on getting TLE for this problem. I use Dijkstra's algorithm. I even implemented it using binary heap and still TLE.

Am I wrong using Dijkstra? Or should I use Fibonacci Heap? Can somebody post some critical test input data?

Thanks

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

10039 Railroads TLE

Post by BiK » Wed Nov 12, 2003 11:38 pm

I keep on getting TLE for this problem. I use Dijkstra's algorithm. I even implemented it using binary heap and still TLE.

Am I wrong using Dijkstra? Or should I use Fibonacci Heap? Can somebody post some critical test input data?

Thanks

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Thu Nov 20, 2003 6:14 am

If you try to solve this problem with Dijkstra, You will have one instance of each city in each discrete time. So you can have at most 100 * 1000 = 100,000 vertices. Of course it is unlikely V can be that large, but it can be too critical.

So try modeling this problem as something other than a shortest path problem, since there are time flows in this problem...


To be specific, (and a bit spoiler) think about DP. :)
(Like the Spy problem in the Last World Finals..)
JongMan @ Yonsei

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

Post by Maniac » Thu Sep 16, 2004 5:30 pm

For the needy, here some input with tricky or non-tricky cases:

Code: Select all

14
3
A
B
C
3
2
1200 B
1300 C
2
0800 A
0900 B
2
1000 A
1100 B
0700
A
C
4
D
C
A
B
3
3
0800 A
1400 D
1500 C
2
0700 A
0800 B
3
0810 B
0850 C
1423 D
0600
A
D
4
A
B
C
D
2
2
1349 A
1423 B
2
1745 C
1857 D
0800
A
D
4
A
B
C
D
2
3
0859 A
1200 C
1300 D
3
0959 A
1100 B
1201 C
0700
A
D
2
A
U
1
2
0800 A
1000 U
0801
A
U
2
A
U
0
0800
A
U
3
A
U
R
2
2
0800 A
1001 U
2
1000 U
1100 R
0700
A
R
2
A
U
3
2
0700 A
1000 U
2
0800 A
1100 U
2
0900 A
1200 U
0901
A
U
3
Hamburg
Frankfurt
Darmstadt
3
2
0949 Hamburg
1006 Frankfurt
2
1325 Hamburg
1550 Darmstadt
2
1205 Frankfurt
1411 Darmstadt
0800
Hamburg
Darmstadt
2
Paris
Tokyo
1
2
0100 Paris
2300 Tokyo
0800
Paris
Tokyo
0
0
2359
Lutjebroek
Utrecht
3
Hamburg
Frankfurt
Darmstadt
3
2
0949 Hamburg
1006 Frankfurt
2
1325 Hamburg
1550 Darmstadt
2
1205 Frankfurt
1411 Darmstadt
0800
Hamburg
Darmstadt
2
Paris
Tokyo
1
2
0100 Paris
2300 Tokyo
0800
Paris
Tokyo
0
0
2359
Lutjebroek
Utrecht
output from AC solution:

Code: Select all

Scenario 1
Departure 1000 A
Arrival   1300 C

Scenario 2
Departure 0800 A
Arrival   1400 D

Scenario 3
No connection

Scenario 4
Departure 0859 A
Arrival   1300 D

Scenario 5
No connection

Scenario 6
No connection

Scenario 7
No connection

Scenario 8
No connection

Scenario 9
Departure 0949 Hamburg
Arrival   1411 Darmstadt

Scenario 10
No connection

Scenario 11
No connection

Scenario 12
Departure 0949 Hamburg
Arrival   1411 Darmstadt

Scenario 13
No connection

Scenario 14
No connection

Good luck! Erik

coderaka
New poster
Posts: 1
Joined: Fri May 20, 2005 2:21 pm

10039 How to solve it with DP??

Post by coderaka » Mon Aug 01, 2005 5:05 am

Help me.
Thx.

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Re: 10039 How to solve it with DP??

Post by lonelyone » Thu Jan 05, 2006 11:40 pm

coderaka wrote:Help me.
Thx.
Yes, did someone solve this problem by DP?
Please give us some hint.

Or may you use Dijkstra, please teach us how to model this problem.
I have no idea completely, so please descrip your ideas in detail.

Thanks a million.

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Sat Mar 25, 2006 8:16 pm

Hi all,

I have been gettin TLE in this problem for quite a long time now.
My solution is as follows:

1. I have created a graph with Cities as Vertices and Train Routes as edges.

2. I maintain an array bestDepTime[][]
bestDepTime[j] contains "If city(i) can be reached in time(j) then the best i.e. the latest Departure Time possible"

To me the complexity can be at best the size of the array bestDepTime .. I absolutely have no idea why I should get TLE :( I am ready to get WA though.

Hope someone can provide with an IO or reason for my TLE... thnx in advance

Code: Select all

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>

const int cmax = 105;
const int tmax = 24 * 60 + 5;

using namespace std;

struct Route
{
	int arrTime;	//Arrival Time in dest city
	int depTime;	//Departure from the current city
	int dest;		//Destination

	bool operator<(const Route &ob) const
	{
		if(depTime != ob.depTime)
			return depTime > ob.depTime;
		
		return arrTime < ob.arrTime;
	}
};

vector<Route> tList[cmax];
int nRoute[cmax];

int cVisit[cmax];
int bestDepTime[cmax][tmax];

int nCity, nTrain;
int src, dest, startTime;


void generateRoute(int currCity, int arrTime, int depTime)
{
	int i;

	//If the current city was reached with an EARLIER i.e. BETTER arrival time
	//Then the departure time for that arrival also is >= current depTime
	//Hence we can ignore this case
	if(cVisit[currCity] <= arrTime)
		return;

	cVisit[currCity] = arrTime;

	//If the current city is reached with this arrival time
	//then it is guaranteed that it was reached with a LATER i.e. BETTER depTime
	//As we are calling the functions with a decreasing order of departure time
	if(bestDepTime[currCity][arrTime] != -1)
		return;

	bestDepTime[currCity][arrTime] = depTime;

	for(i=0; i<nRoute[currCity]; i++)
	{
		if(tList[currCity][i].depTime >= arrTime)
			generateRoute(tList[currCity][i].dest, tList[currCity][i].arrTime, depTime);
		else
			break;
	}
}


int main(void)
{
	int i, j;

	int nTest, tst;

	map<string, int> cityNum;

	string currCity, prevCity;
	char cityName[100];

	Route rt;

	int frm, to, arrTime, depTime;


#ifndef ONLINE_JUDGE
	freopen("d:/programs/input/10039.txt", "r", stdin);
#endif

	scanf("%d", &nTest);

	for(tst=1; tst<=nTest; tst++)
	{
		scanf("%d", &nCity);

		for(i=0; i<nCity; i++)
		{
			scanf("%s", cityName);
			cityNum[cityName] = i;
		}

		scanf("%d", &nTrain);

		memset(nRoute, 0, sizeof(nRoute));

		for(i=0; i<nTrain; i++)
		{
			scanf("%d", &j);

			scanf("%d %s", &depTime, cityName);
			prevCity = cityName;
			frm = cityNum.find(prevCity)->second;

			j--;

			while(j--)
			{
				scanf("%d %s", &arrTime, cityName);
				currCity = cityName;

				to = cityNum.find(currCity)->second;

				rt.arrTime = arrTime / 100 * 60 + arrTime % 100;
				rt.depTime = depTime / 100 * 60 + depTime % 100;
				rt.dest = to;

				tList[frm].push_back(rt);
				nRoute[frm]++;

				prevCity = currCity;
				depTime = arrTime;
				frm = to;
			}
		}


		scanf("%d", &startTime);
		startTime = startTime / 100 * 60 + startTime % 100;

		src = dest = -1;

		scanf("%s", cityName);
		prevCity = cityName;
		src = cityNum.find(prevCity)->second;

		scanf("%s", cityName);
		currCity = cityName;
		dest = cityNum.find(currCity)->second;

		if(src < 0 || dest < 0)
		{
			printf("Scenario %d\n", tst);
			printf("No connection\n\n");
			continue;
		}
		
		for(i=0; i<nCity; i++)
			sort(tList[i].begin(), tList[i].end());


		//Initialization
		memset(bestDepTime, -1, sizeof(bestDepTime));
		memset(cVisit, 127, sizeof(cVisit));
		cVisit[src] = -1;
		
		for(i=0; i<nRoute[src]; i++)
		{
			if(tList[src][i].depTime >= startTime)
				generateRoute(tList[src][i].dest, tList[src][i].arrTime, tList[src][i].depTime);
			else
				break;
		}

		for(i=0; i<tmax; i++)
		{
			if(bestDepTime[dest][i] != -1)
			{
				arrTime = i;
				depTime = bestDepTime[dest][i];
				break;
			}
		}
		
		//Output
		printf("Scenario %d\n", tst);

		if(i >= tmax)
			printf("No connection\n\n");
		else
		{
			depTime = depTime / 60 * 100 + depTime % 60;
			arrTime = arrTime / 60 * 100 + arrTime % 60;

			printf("Departure %04d %s\n", depTime, prevCity.c_str());
			printf("Arrival   %04d %s\n\n", arrTime, currCity.c_str());
		}

		cityNum.clear();

		for(i=0; i<nCity; i++)
			tList[i].clear();
	}
	
	return 0;
}


Where's the "Any" key?

ashutoshmehra
New poster
Posts: 1
Joined: Mon Jun 23, 2008 1:39 pm

Re: 10039 - Railroads

Post by ashutoshmehra » Thu Jun 26, 2008 12:56 pm

Hello everyone,

After many WAs and reworking my code many times, I am still unable to see where the bug lies in my code. I've tested my program with all the various test-cases in this thread (and some of my own), and I get correct result.

So, finally, I decided to request some clarification regarding the nature of the input -- in particular the train schedules.
1. Are the train stop times guaranteed to be in ascending order? If not, I think I'll need to sort them.
2. Can the times in the train schedules "wrap around" -- that is, something like:
2300 A
0000 B
0100 C
If so, how are we supposed to handle such an input?
3. Whatever, the "earliest start time" specified in the input, Jill must reach the destination by 2359 latest. Is that right? Thus, Jill can never take a train that "wraps around" midnight (like a train from A to C in the schedule above)?
4. The times are all in HHMM format and that 0 <= HH < 24 and 0 <= MM < 60. Is that right?

People who have got AC on this one, could you please confirm my understanding, or correct it?
Also, if some one can share any edge/tricky cases aside from the ones already posted, it might help me figure out the bug in my program.

Thanks!

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 10039 - Railroads

Post by Articuno » Wed Dec 09, 2009 12:58 pm

I am not sure how to solve this problem. Can anyone tell me about a general approach? Is it possible to solve this problem with bfs or dijkstra? Someone reply please... thanks in advance
May be tomorrow is a better day............ :)

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10039 - Railroads

Post by Obaida » Tue Mar 02, 2010 7:39 am

I think BFS should solve this.
But I am very much confused with the problem description. :(
Any one please help me :-?
try_try_try_try_&&&_try@try.com
This may be the address of success.

Neil
New poster
Posts: 8
Joined: Fri Jun 22, 2012 7:04 am

Re: 10039 - Railroads

Post by Neil » Fri Jul 27, 2012 5:21 am

This problem makes no sense. I was testing random cases with the UVA toolkit, and I learned that it's wrong to assume that Jill can't go back in time.
For this case

Code: Select all

1
10
A
B
C
D
E
F
G
H
I
J
5
6
0072 B
1233 E
1975 F
0531 G
1223 I
0494 J
3
0661 B
1477 I
1602 J
4
1034 F
0567 G
1618 I
1218 J
8
0582 C
0667 D
1563 E
0870 F
1419 G
0840 H
1406 I
1200 J
8
0176 B
1939 C
1032 E
0461 F
0773 G
0895 H
1299 I
0868 J
389
C
G
the output is
Scenario 1
Departure 1939 C
Arrival 0531 G

Is this correct? Can Jill really arrive before she departs?

Post Reply

Return to “Volume 100 (10000-10099)”