238 - Jill's Bike

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

Moderator: Board moderators

dpitts
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

238 - Jill's Bike

Post by dpitts » Thu Mar 11, 2004 12:26 pm

I wrote a solution that works for the given sample data, but I get memory exceeded for the judges data (at 9.986 seconds).

I use a simple minimum path algorithm that uses bredth first traversal. Any idea's what the problem might be?
Here is my search algorithm. I assume I've read in heights/directions correctly, because it works for the sample data.

Is there perhaps a different way to find the path? Depth first would take less memory, but I think more time since you'd have to do an exhaustive search.
[cpp]
struct Grid
{
int streets;
int aves;
int heights[20][20];
bool visited[20][20];
direction directions[20][20];

bool shortestPath(Pos from, Pos to, vector<Pos> &route)
{
for (int i = 0; i < streets; i++)
for (int j = 0; j < aves; j++)
visited[j] = false;
deque<vector<Pos> > routes;
vector<Pos> cur;
cur.push_back(from);
routes.push_back(cur);
while (routes.size())
{
cur = routes.front();
/*debug##cout << "Considering: " << cur << endl;/**/
routes.pop_front();
Pos p = cur.back();
p[visited] = true;
/*debug##cout << "From " << p << ", ";/**/
if (p[directions] & north && !p.north()[visited])
{
/*debug##cout << "n";/**/
vector<Pos> next = cur;
next.push_back(p.north());
routes.push_back(next);
if (next.back() == to)
{
route = next;
return true;
}
}
if (p[directions] & south && !p.south()[visited])
{
/*debug##cout << "s";/**/
vector<Pos> next = cur;
next.push_back(p.south());
routes.push_back(next);
if (next.back() == to)
{
route = next;
return true;
}
}
if (p[directions] & west && !p.west()[visited])
{
/*debug##cout << "w";/**/
vector<Pos> next = cur;
next.push_back(p.west());
routes.push_back(next);
if (next.back() == to)
{
route = next;
return true;
}
}
if (p[directions] & east && !p.east()[visited])
{
/*debug##cout << "e";/**/
vector<Pos> next = cur;
next.push_back(p.east());
routes.push_back(next);
if (next.back() == to)
{
route = next;
return true;
}
}
/*debug##cout << endl;/**/
}
return false;
}
};

[/cpp]

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Mar 11, 2004 1:56 pm

Hm, I don't know C++ good enough to see your 'memory leak'.
I wrote a BFS in C and it consume about half a meg of memory and finishes under .5 seconds. Alas it's WA.

I'm most worried about the sentence:
Jill rides a bicycle everywhere she goes, but she always wants to go the easiest and shortest way possible.
Do we have to find only the shortest route? Or also the easiest of the shortest? Or the shortest of the easiest? And how is the 'easiness' of a route defined?
Maybe Farid can enlighten us here.

I also tried dijkstra, defining easiness as the sum of the climbs during the route, trying both shortest of the easiest and easiest of the shortest, but no success.

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Thu Mar 11, 2004 3:21 pm

Yes.. I agree.. this question is very ambiguous.. can someone please clarify:

1) What does it mean by "Avoid any climb of more than 10 meters between adjacent grid points." ? Does it mean that the height difference should be < 10 (when climbing) or <= 10 < sqrt( 99 ) or <= sqrt( 99 ) ?

(99 is from 10*10 - 1*1 , ie: the distance between two grid points)

2) When it says "Always travel the shortest possible route.", how do we measure the length of a route? Is it length 1 to move from (1,1) to (1,2) or is the length = sqrt( 1 + (height(1,1) - height(1,2))^2) ?

3) What does it mean by "easiest and shortest way possible" ? Does it mean as much downhill as possible, or as little uphilll as little or what?

dpitts
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

Double check certain things...

Post by dpitts » Thu Mar 11, 2004 7:54 pm

Do you put a blank line between each output?
That would probably get you a WA if you forgot to.
Also, make sure you have punctuation where its needed, and not where it isn't.

Anyway, I've changed my algorithm slightly. So instead of keeping track of every route seperatly (which has a lot of duplication), I keep track of the routes in a sort of linked list, based on my queue. I used this technique once for extra credit in a homework problem. The teacher hadn't ever seen it before, and didn't understand it. LOL.

I'll post the result after I finish.

dpitts
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

Hmm.

Post by dpitts » Thu Mar 11, 2004 7:56 pm

Hmm, even though it should be taking less memory now. I get MLE twice as fast, and by almost twice as much. I'll have to rethink this problem at a later date.

Well, let me know if my suggestions about the blank spaces helps.

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Fri Mar 12, 2004 12:20 am

I have a blank line between teach output.. but even if there isn't, +- blank lines should just give PE.. not WA..

Also, I don't keep track of routes.. just their final results since I'm using Dijkstra, so there's no memory problems for me.

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Fri Mar 12, 2004 7:44 pm

1) What does it mean by "Avoid any climb of more than 10 meters between adjacent grid points." ? Does it mean that the height difference should be < 10 (when climbing) or <= 10 < sqrt( 99 ) or <= sqrt( 99 ) ?
This means that if height absolute difference >10 there is not way.
2) When it says "Always travel the shortest possible route.", how do we measure the length of a route? Is it length 1 to move from (1,1) to (1,2) or is the length = sqrt( 1 + (height(1,1) - height(1,2))^2) ?
This means that the length of the path must be the shortest.

You must put blank lines between two output lines, otherwise you will get WA - not PE.[/quote]
_____________
NO sigNature

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Mar 12, 2004 8:03 pm

I just read this problem, and for me it is clear: You can regard the distance between two adjacent points as 1, because it is said, that the distance between any two adjacent grid points is equal. So bfs should solve the problem. And for the maximum climb: it is said, that between two grid points it should be <= 10, so you just calculate the difference between altitude of destination grid point and starting grid point for each pair of adjacent grid points on your road, and it has to be <= 10.
I think the term easiest way is just this condition, so all paths that don't have a climb of more than 10 are easy, and among those you are looking for one of the shortest paths.

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Fri Mar 12, 2004 8:40 pm

The good news is that she lives in Greenhills, which has all its roads laid out in a strictly rectangular grid - east-west roads are streets; north-south roads are avenues and the distance between any two adjacent grid points is the same.
You see it's said that the distance between any two adjacent grid points is the same. So you can assume that distance between two grid points is 1.
The shortest way means that any existing path of shortest length will be accepted. You must also consider negative heights and roads which have two directions. Maybe negative heights are not correct and does not suit with the word hilly, but any correct approach can also consider this case and get accepted. You can use BFS and also Dijkstra.

If you want PE you can add unnecessary blank lines to the end of the output.
_____________
NO sigNature

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Mar 12, 2004 9:09 pm

This means that if height absolute difference >10 there is not way.
Do you really mean absolute difference? so if I go from a to b and a has height 11, and b height 0, you say, there is no way?
I doubt that this is correct. For me "climb" means, it goes up. So going down has no restriction. Some native speaker please correct me if I am wrong.

And about output format: I just want to clarifiy:
is it always one line data, one blank line, ... until last data line, so for two times the sample input, the output would be:

Code: Select all

1-1 to 1-2 to 1-3 to 1-4 to 2-4 to 2-3 to 2-2

To get from 2-3 to 2-3, stay put!

There is no acceptable route from 2-2 to 1-1.

1-1 to 1-2 to 1-3 to 1-4 to 2-4 to 2-3 to 2-2

To get from 2-3 to 2-3, stay put!

There is no acceptable route from 2-2 to 1-1.
and roads which have two directions
I hope I understand it right, that initially there are no roads, so roads with two directions are given in the input as one way roads for these 2 directions. My understanding is also based on the image of the problem description: you can see, there are no roads there for the grid points that don't occur in the one-way roads section.

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Fri Mar 12, 2004 9:21 pm

Sorry for confusing description, but "climb" here means travel on hills. So you can't go up or down if the absolute difference >10. Consider this case as abs(difference)<=10. I'll fix it to avoid confusion.
Please try this variation.
Thanks.
_____________
NO sigNature

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Fri Mar 12, 2004 9:23 pm

Sorry for confusing description, but "climb" here means travel on hills. So you can't go up or down if the absolute difference >10. Consider this case as abs(difference)<=10. I'll fix it to avoid confusion.
Please try this variation.

And about output:
Only one blank line between any two non-blank lines and no blank at the end of output if you want AC.

For two times sample output your output is correct.

Thanks.
_____________
NO sigNature

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Fri Mar 12, 2004 10:05 pm

Hi people.
Sorry but there is a mistake in the sample output.
There must be
1-1 to 1-2 to 1-3 to 1-4 to 2-4 to 2-3 to 2-2

To get from 2-3 to 2-3 stay put!

There is no acceptable route from 2-2 to 1-1.
Instead of
1-1 to 1-2 to 1-3 to 1-4 to 2-4 to 2-3 to 2-2

To get from 2-3 to 2-3, stay put!

There is no acceptable route from 2-2 to 1-1.
It will soon be fixed.

Thanks.
_____________
NO sigNature

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Mar 13, 2004 9:42 am

Hm, that figures. The redundant comma was about the only thing I didn't try. I would vote for the interpretation in Adrians' first posting as being the most natural. It was also mine, until I got WA after WA.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sat Mar 13, 2004 12:54 pm

Farid: Could you perhaps change your program and the special corrector, because a lot of submissions was based on the sample output and had this ",". And this is also like the original output for this problem was (World Finals 1995 Problem A http://icpc.baylor.edu/past/icpc95/finals/Problems.html ).
And about the word "climb": could someone who speaks english as mother language please check the understanding of Farid? Because for me my understanding is far more logical. Jill wants to use easy roads, and if a road goes down, it is very easy to travel on it on bike. Only if it goes up, it becomes difficult.

Post Reply

Return to “Volume 2 (200-299)”