Moderator: Board moderators

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 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
3 ->number of train
2 ->number of city.
0949 Hamburg
1006 Frankfurt
2
1325 Hamburg
2
1205 Frankfurt
0800
Hamburg

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.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 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 ...

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:
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

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

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:
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
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
3
2
0949 Hamburg
1006 Frankfurt
2
1325 Hamburg
2
1205 Frankfurt
0800
Hamburg
2
Paris
Tokyo
1
2
0100 Paris
2300 Tokyo
0800
Paris
Tokyo
0
0
2359
Lutjebroek
Utrecht
3
Hamburg
Frankfurt
3
2
0949 Hamburg
1006 Frankfurt
2
1325 Hamburg
2
1205 Frankfurt
0800
Hamburg
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

Scenario 10
No connection

Scenario 11
No connection

Scenario 12
Departure 0949 Hamburg

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??

Help me.
Thx.

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

### Re: 10039 How to solve it with DP??

coderaka wrote:Help me.
Thx.
Yes, did someone solve this problem by DP?

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
Contact:
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

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

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

I think BFS should solve this.
But I am very much confused with the problem description.
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

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?