157 - Route Finding

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

Moderator: Board moderators

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:

Post by ftomi »

Hello!

Can anybody tell me the output for this input? Thanks

Code: Select all

4
A:a=Ba=Ca
B:ab
C:ab
D:ab=Cb
AaCa
AaAa
AaCb
AaDb
BbCb
#

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev »

Output:
3: Aa=Ca
0: Aa
4: Aa=Cab
7: Aa=Cab=Db
5: Bba=Cab

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:

Post by ftomi »

I thought, "Connecting stations will have more than one designation" means I should not change line If I start at a 'connecting station', but not that line, what should I use. It would be closer to the real life...
Thanks!

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum »

My program gives the correct answers for all of the examples and the cases quoted here and yet I still get a WA. I have tried all of the test cases I can think of, along similar lines to those here and can't find anything wrong. Does anyone have a more complete/complex test case I can try ?

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

still no nearer

Post by Caesum »

I am still no nearer solving this. I really can't see where this is going wrong, here is my code:

[c]
deleted..... doesnt need to be here now :)
[/c]
Last edited by Caesum on Sun Jun 09, 2002 6:15 pm, edited 1 time in total.

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

to caesum

Post by xenon »

I have no C-compiler at hand, so I did a little 'mind-debugging'.

Consider the input:
3
A:a=Cabcdefg=Bb
B:a=Cbb=Ag
C:a=Aab=Ca
BbAa
#

The correct answer is:
8:Bba=Cba=Aa
but I think your program produces:
8:Bb=Agfedcba

Your floodfill fills mtime['Ag'] with 6 and mtime['Ba'] with 7. Both values are correct, but the correct route is via the higher mtime['Ba'], while your routefinder selects the lower mtime['Ag'].

I hope I have made no mistakes. I haven't solved the problem yet, so I have no way of checking my assumptions...

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

just ran this and

Post by Caesum »

it gives
8: Bba=Cba=Aa

btw, hi xenon :P

oh, and it does say:
Note that there will always be only one fastest route for any given pair of stations.
in the question.

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

ok

Post by xenon »

hi yourself!
't was just a thought.
Sure, there is only one shortest route in the input I made up, the route via 'Ag' is longer (9) then via 'Ba' (8). I just didn't see your routefinder rule out traveling from 'Bb' (mtime=8) to 'Ag' (mtime=6), since conn['Bb']['Ag']==1 (it's a station), while the actual time is 3 seconds.
Nevermind.
Thx for putting a link to this contest on your site. I'm completely hooked eversince... :)

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum »

thanks xenon,
you saved me :)
your idea was right in principle, when i was backtracing the route it was possible for one to have lower time but not be part of the final route since it had to be either 3 less or 1 less and in the same major section to be on the route. solved :) now i just need to get rid of a few more wa's.......

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

good!

Post by xenon »

Guess it's enough either to save an extra predecessor field while floodfilling, then backtracking always gives the correct route, or recheck the moves while stepping back, and then your code will work. I'll take the liberty to leech your program (is to leech an english verb?), of which I saved a copy :D , and translate your ideas into pascal, and submit it as my own :oops:
Happy hunting!

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum »

Actually, i just made two checks: either the step back reduces the cost by 3, or it reduces the cost by 1 and is on the same major route. No, I dont mind, it helps save time :)

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

Post by xenon »

In the end i decided to start anew and try something Dijkstra-ish. Took me 3 hours to implement it :cry: . But it got accepted and runs twice as fast using twice as much memory. Still wonder how the other guys can do it in zero CPU-time with 64k memory.
TTYL - xenon

pokute
New poster
Posts: 4
Joined: Tue Jan 07, 2003 10:58 am
Location: KOREA

157 - Route Finding

Post by pokute »

1
A:fgmpnxzabjdf
AaAa
#



What is the correct answer?

0: Aa
or
0: Aaa
or
2: Aaba


This is my code..

[cpp]
#include <iostream>
#include <iomanip>

using namespace std;

struct edge
{
int w;
char prevRoute, prevStation;
} graph[26][26][26][26];

bool route[26], station[26][26];
char buff[256], *pBuff, *p2Buff, *p3Buff;

void prnPath(int i, int j, int k, int l);

void main()
{
int i, j, k, l, m, n;

for(i = 0; i < 26; i++)
{
route = false;
for(j = 0; j < 26; j++)
{
station[j] = false;
for(k = 0; k < 26; k++)
{
for(l = 0; l < 26; l++)
{
graph[j][k][l].w = 0;
graph[j][k][l].prevRoute = -1;
graph[j][k][l].prevStation = -1;
}
}
}
}

for(cin >> i; i > 0; i--)
{
for(cin.getline(buff, 256); buff[0] == '\0'; cin.getline(buff, 256));
pBuff = buff + 2;
route[(j = buff[0] - 'A')] = true;

for(pBuff = buff + 3, k = buff[2] - 'a', station[j][k] = true; *pBuff != '\0'; pBuff++)
{
if(*pBuff == '=')
{
p2Buff = pBuff + 1;
do
{
route[(l = *(++pBuff) - 'A')] = true;
station[l][(m = *(++pBuff) - 'a')] = true;
graph[j][k][l][m].w = graph[l][m][j][k].w = 3;

for(p3Buff = p2Buff; p3Buff < pBuff - 1; p3Buff += 3)
graph[p3Buff[0] - 'A'][p3Buff[1] - 'a'][l][m].w = graph[l][m][p3Buff[0] - 'A'][p3Buff[1] - 'a'].w = 3;
} while(*(++pBuff) == '=');

if(*pBuff == '\0')
break;
}

if('a' <= *pBuff && *pBuff <= 'z')
{
station[j][(l = *pBuff - 'a')] = true;
graph[j][k][j][l].w = graph[j][l][j][k].w = 1;
k = l;
}
}
}

for(i = 0; i < 26; i++)
{
if(route)
{
for(j = 0; j < 26; j++)
{
if(station[j])
{
for(k = 0; k < 26; k++)
{
if(route[k])
{
for(l = 0; l < 26; l++)
{
if(/*!(i == k && j == l) && */station[k][l] && graph[k][l][j].w)
{
for(m = 0; m < 26; m++)
{
if(route[m])
{
for(n = 0; n < 26; n++)
{
if(/*!(k == m && l == n) && !(i == m && j == n) && */station[m][n] && graph[j][m][n].w)
{
if(graph[k][l][m][n].w == 0 || graph[k][l][m][n].w > graph[k][l][j].w + graph[i][j][m][n].w)
{
graph[k][l][m][n].w = graph[k][l][i][j].w + graph[i][j][m][n].w;
graph[k][l][m][n].prevRoute = i;
graph[k][l][m][n].prevStation = j;
}
}
}
}
}
}
}
}
}
}
}
}
}

while(cin.getline(buff, 256))
{
if(buff[0] == '#')
break;

i = buff[0] - 'A';
j = buff[1] - 'a';
k = buff[2] - 'A';
l = buff[3] - 'a';

cout << setw(3) << graph[i][j][k][l].w << ": ";
pBuff = buff;
prnPath(i, j, k, l);
*(pBuff++) = k +'A';
*(pBuff++) = l +'a';
*pBuff = '\0';

cout << buff[0] << buff[1];
for(pBuff = buff + 2; *pBuff != '\0'; pBuff += 2)
{
if(*pBuff == *(pBuff - 2))
cout << *(pBuff + 1);
else
cout << '=' << *pBuff << *(pBuff + 1);
}
cout << endl;
}
}

void prnPath(int i, int j, int k, int l)
{
if(graph[i][j][k][l].prevRoute == -1)
{
*(pBuff++) = i +'A';
*(pBuff++) = j +'a';
}
else
{
prnPath(i, j, graph[i][j][k][l].prevRoute, graph[i][j][k][l].prevStation);
prnPath(graph[i][j][k][l].prevRoute, graph[i][j][k][l].prevStation, k, l);
}
}
[/cpp]

Pedrinho UFPE
New poster
Posts: 15
Joined: Tue Sep 10, 2002 1:56 am
Location: Brasil
Contact:

Post by Pedrinho UFPE »

Still WA :(
Last edited by Pedrinho UFPE on Sat Apr 19, 2003 5:10 am, edited 1 time in total.
Interested

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

Post by little joey »

My accepted program gives a different answer for ftomi's example:

Code: Select all

  3: Aa=Ca
  6: Aa
  4: Aa=Cab
  7: Aa=Cab=Db
  5: Bba=Cab
while your program reproduces the (wrong) output of Ivan Golubev.

Post Reply

Return to “Volume 1 (100-199)”