Visiting same city twice

Visiting same city twice

Hello!

There is no mention about visiting the same city twice in problem statement. However, reference solution checks for it with never_traveled_to() function. So I can imagine test, which doesn't conradict rules, but reference solution fails on it. Here it is:

3 cities: A, B, C. Start from A, goal is C. (no need to go back) 

Available flights:

A -> B, begin: hour 0, land: hour 3, cost $1

B -> C, begin: hour 3, land: hour 4, cost $1000

B -> A, begin: hour 3, land: hour 6, cost $1

A -> B, begin: hour 6, land: hour 10,  cost $1

B -> C, begin: hour 10, land: hour 11, cost $1

dep_time_min = 0, dep_time_max = 12

So optimal path is A-B-A-B-C with cost $4, but reference solution will find path A-B-C with cost $1002, since we can't wait for cheap flight more than 4 hours. 

Can I get some clarifications about it?

publicaciones de 8 / 0 nuevos
Último envío
Para obtener más información sobre las optimizaciones del compilador, consulte el aviso sobre la optimización.

Hello,
This is working. You have two flights from B to C... And you can do A -> B -> C with the first and the last flight. x)

It could not work if you take max_layover_time > 12,
But as said Cédric, we won't have any scenarios like that (you can see it in "Some clarifications" post) and you can keep this condition because it's not that so long to check it and it can even be accelerated. Don't worry about pathological cases because this won't happen in scenarios we have ! ;)
It's hope to you to remove this function but :
- You won't have the same input as we have,
- You algorithm without a pathological case like that will be slower because it will create stupid loops.

I hope it answers to you,

Regards,

Timothé Viot,
Engineer student, Insa Rennes 1
France

You can't take first and last flights, because of layover time limit (I forgot to specify it, let it be 4 hours).
Yes, I've seen post that there won't be any tricky scenarios, but it's not always clear what is tricky and what is not.

Anyway, it's interesting moment, and i wanted to show it to others =)

Don't worry, the algorithm is maybe not perfect for this very complicated problem ! =)
But Cédric will repeat what I said :
The scenarios that they give us will not have this kind of pathological cases, the goal of the contest is to make us accelerating the algorithm ;
Not correct it but only make it as fast as possible !

Regards,

Timothé Viot,
Engineer student, Insa Rennes 1
France

As we already said on an other topic, you are free to implement your algorithm the way you want, but you must stick to the output that our reference code would give.

You have to admit that in real life, you would not flight through the same city twice just to get a discount.

Anyway, this is important for your result to check that from A to B (if A and B are your points of interest), you never fly twice to the same city.

EDIT :

I didn't really watched your solution, but the best flight seems to be :

A -> B, begin: hour 6, land: hour 10, cost $1

B -> C, begin: hour 10, land: hour 11, cost $1

With a cost = 2$. And as the min_time is 0 and max_time is 12, the default program should find this solution.

Ok, if we can wait in A for 6 hours, just add one city (make A not starting) before it, so we can't wait there.
But I've already got answers for my questions, so it doesn't matter.

You don't need to wait for 6 hours in A, you just have to start your trip on the flight A -> B, begin: hour 6, land: hour 10, cost $1 since your travel is from A to B.

But anyway, you seem to have your answer.

That was the reason why I suggested to add another city to start at. More formally: add city X, now start at X (not at A), and add only one flight: X->A, start: -1 hour, land: 0 hour, cost 1$. So now, in order to reach C, we have to use this new flight. And as we can't wait for hour 6, we'll use first flight to B (at hour 0), and than first ($1000) flight to C.
I've found another "bad" test (for "visit once" problem) in another forum thread. There another idea (reducing cost with company's discount) is used. It looks like the easiest way to deal with such questions is to add "not visiting twice" rule in problem statement (IMHO).
Thanks for your answers anyway.

Deje un comentario

Por favor inicie sesión para agregar un comentario. ¿No es socio? Únase ya