"Work hard, play hard!" problem - some clarifications

"Work hard, play hard!" problem - some clarifications

Hello everyone,

I have 2 questions:

1. Can you give an upper bound for the number of lines in flights.txt?

2. How many vacation airports will be given?

Regards,

Mircea

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

Hi Mircea !

You must think your program to scale on all the configurations you can imagine. So for the moment there is no upper bound.

Hi everyone,

I think you have to calrify the discount. From my point of view the reference implementation differs from the description of the problem. In which cases can we get a discount? The description of the Problem assumes that all flights of a travel have to be from the same airine/alliance. But in the reference code only two flights are checked...

Regards

Hannes

hello

no limit on flights, no limit on vacation airports.
the sky is the limit !

paul
@intel

This is the reason why the reference code only checks the two last flights. It tries first to apply the company discount, then the alliance discount, otherwise, no discount.

Cita:

Hannes T. escribió:

Hi everyone,

I think you have to calrify the discount. From my point of view the reference implementation differs from the description of the problem. In which cases can we get a discount? The description of the Problem assumes that all flights of a travel have to be from the same airine/alliance. But in the reference code only two flights are checked...

Regards

Hannes

Hi Mircea,
For your question, I think there is no problem with the number of flight. The reason could be that, in the reality, new flights could be created as many time as necessary and you can not predict the final number of flight you will have.
If you watch the C++ vector (that exists in Java too) structure, you should not be lost because the vector structure does the work. You can even work with the "reserve" member function as described on the stl website to control your structure.
Link that could help you : http://www.cplusplus.com/reference/stl/vector/

With that, even the sky is not a limit ! ;)

Hope it will help you,
Regards,

Timothé Viot,
Engineer student, Insa Rennes 1
France

Hello everyone,

I have a question too, can a company be in more than one alliance?

Regards,

Michael.

Hello Michael,

In fact, this is given in the problem section of the document online. At the end of the page. I took a screenshot to show you ! :)

I hope it helps you.
Regards,

PS : I think that you do not have to hesitate to create a new topic for a new question. Then, if someone have the same question, it will be easier for him to find it ! :)
(But I'm not sure of that... !)

Timothé Viot,
Engineer student, Insa Rennes 1
France

Thanks a lot Timothe V.

Hi everyone!

Can somebody give me some extra explanation for the nerver_traveled_to function?

Thanks in advance!

Hi umbrella ! :)

The function is just here in order to test if, in a travel instance, the city is already in the trip. This make sure that you have only one city per travel, because you don't want to see a city two times and spend your money twice for the same city.
Mmmmh, you should maybe try to understand the compute_path function which seems to be one of the program core, maybe it will help you understand this "never_traveled_to" function.
If someone can give a better help to this question, do not hesitate to tell me if I am wrong or to give some more information about this function !

@Michael You welcome. ;)

Regards,

Timothé Viot,
Engineer student, Insa Rennes 1
France

Thank you Timothé V.!

I think that I understand.
For example (Play hard and we want to visit more places):
path1: H -> V1 -> C
path2: C -> V2 -> H
H - home
C - conference
V1, V2 - vacations
Then V1 != V2.
Am I right?

Hello again,
In fact no,
Let's take an example as you did :

- You have a travel (a simple vector of flights) that is the first parameter of the function :
> Example : travel1 : H -> V1 -> V2 -> V3 (under construction because it does not contain C)
- And you have a city that is the second parameter of the function :
> Example : "Rio".
==> If travel1 contains Rio (i.e. if H = Rio or V1 = Rio or V2 = Rio or V3 = Rio), the function returns false. Else, it returns true.
The function does not do anything else. :)

If I do not do any mistake (please correct me if I'm saying something wrong!!), the case you gave in example is not tested because your two travels are not the same (they are only merged at the end of the work) and the function only take one travel in parameter, not two.

I don't know if I helped you more this time... Do not hesitate to ask more question if not!

Sincerly,

Timothé Viot,
Engineer student, Insa Rennes 1
France

Hi there,

I have one doubt about company discounts.
Let's say if:
- Flights are F11, F12, F21 and F22
- Companies are C1 and C2
- Alliances are A1 and A2

and if:
- flights F11 and F12 belongs to C1 company
- flights F21 and F22 belongs to C2 company
- and if resulting trip is:
#1# F11
#2# F12
#3# F21
#4# F22

How are discounts distributed if:
- companies C1 and C2 are in A1 alliance?
- companies C1 is in alliance A1, and C2 is in alliance A2?

If I understood, it doesn't matter, even all flights in first case are from same alliance?

Thanks.

Also, I have three questions more:

#1
If vacations of interest are three different towns (T1, T2, T3), does it mean that I can, during my vacaton, visit all three towns? I know that I can go through them "unintentionally", but are they in criteria for better combination?
If that is the case, then, what are allowed times for flights, because it doesn't make sense to visit two towns in period assigned for flights_to_vacation, and to spend all vacation on third town?

#2
Why it is forbidden to visit one town two times? It doesn't mean that it would be more expensive, and that extra flight can (not necessarily, but in some cases can) provide that you doesn't wait on airport more than max_layover time?

#3
Do we have an infinite amount of memory on Intel testing machine?

Hi,
#1
If you take a look at the source code we gave, we iterate over each vacation city. Let say that we are in the iteration working on T1. The algorithm will only try ton let you spend some vacation time in T1. It doesn't matter if you travel through T2 and T3 on this single iteration because you wont spend more time in T2 and T3 than the overlay allows you.

#2
Actually, we check that a segment of flights never goes through the same city twice to avoid stupid flights. But as we said in the problem explanation, you are free to modify the source code and optimize it. The only important thing is the output which must be the same than the code we gave you.

#3
Infinite ? For sure, the answer is no :)

For the alliance/company problem, you should try to understand the source code. To sum up the idea, we try to apply the company discount first, the alliance discount and then no discount.

I hope this answers to your questions.

Good luck.

Cita:

Cédric ANDREOLLI (Intel) escribió:

Hi,
#1
If you take a look at the source code we gave, we iterate over each vacation city. Let say that we are in the iteration working on T1. The algorithm will only try ton let you spend some vacation time in T1. It doesn't matter if you travel through T2 and T3 on this single iteration because you wont spend more time in T2 and T3 than the overlay allows you.

#2
Actually, we check that a segment of flights never goes through the same city twice to avoid stupid flights. But as we said in the problem explanation, you are free to modify the source code and optimize it. The only important thing is the output which must be the same than the code we gave you.

#3
Infinite ? For sure, the answer is no :)

For the alliance/company problem, you should try to understand the source code. To sum up the idea, we try to apply the company discount first, the alliance discount and then no discount.

I hope this answers to your questions.

Good luck.

Hi Cédric,

logicaly observed, it is pointless to travel twice through same town, but it is equally pointless to not stay longer than the max_layover_time, but in the text of the problem isn't stated that we can't travel twice through same town, and is stated restriction about max_layover_time.

For example (if max_layover_time is 2h), and for trip from London to Berlin:
***********************************
#1# London->Lisabon
wait 10h
#2# Lisabon->Berlin
****** wrong combination ******

***********************************
#1# London->Lisabon
wait 1h
#2# Lisabon->Amsterdam
wait 1h
#3# Amsterdam->Lisabon
wait 1h
#4# Lisabon->Berlin
****** good combination ******

This is even pretty prominent if these are only possibilities. From the reference source code, it means that I would not go to the conference/vacation (pretty bad).

So, let's seperate specified criteria of optimal trip, from human point of view what is pointless in real world, can we travel through same city twice or more, or can't (there is no reference in text that we can't)?

And for memory, i didn't thought to don't care about memory leaks :) , but do we have to care about memory usage?

Thanks, Dusan.

It's to avoid this kind of trip that the source code is checking you don't take off from the same city twice. The second example you give is just a trick to play with the overlay. In real life, you would accept to increase the overlay :)

So as I said, you can do whatever you want as long as your output is the same as the program we gave you.

You should care about memory usage but lets say that the testing environment should have more memory than you personal computer.

Two more questions:
$ - costs, V - vacations, C - conference, H - home, F - flight, Cm - company, A - alliance:
1)
if I want to visit V1 and V2, which one is better:
1. H -> V1 -> V2 -> C -> H $: 1500
or
2. H -> V1 -> C -> H $: 1200

2) "If you take ALL the segments of a flights from a single company, it’s 30% cheaper.
Plus, companies are forming “alliances” to offer cheaper flights to the customers booking
only inside the alliance. If you take ALL the segments of a flight from a single alliance, it’s 20%
cheaper. "
If I have this situation:
F1 (Cm1) -> F2 (Cm1) -> F3(Cm2), according to this, I shouldn't get no discount, but the code says that I get discount for first two flights...
and I won't get no discount for this:
F1 (Cm1) -> F2 (Cm2) -> F3(Cm1)
It doesn't match the description...

You can travel through V1 and v2 on a single trip (if it's cheaper) but you can't spend your holidays in V1 and in V2. We only consider 1 vacation destination at a time.
The output clearly gives a whole set of flights for each destination you would like to spend your vacations.

For the second point, I think you should understand the word "segment" as two or more flights in a row. To give you a example :
Let say that :
- C1 and C2 are in alliance 1
- C3 and C4 are in alliance 2

The following set of flights C1 - C1 - C3 - C4 - C3 - C2 - C1 - C1 could be decomposed into :
-A segment C1 - C1 because we can apply the "same company" discount
-A segment C3 - C4 - C3 because they are in the same alliance
-Then it's getting a little bit more complicated we can see that C2 - C1 - C1 re in the same alliance but C1 - C1 are also flights from the same company. In this case you must apply the best discount you can for each flight. It means that C2 will have the "same alliance" discount. C1 - C1 will have the "same company" discount.

I hope the description made the problem more clear for you.

Cita:

hela_umbrella escribió:

Two more questions:
$ - costs, V - vacations, C - conference, H - home, F - flight, Cm - company, A - alliance:
1)
if I want to visit V1 and V2, which one is better:
1. H -> V1 -> V2 -> C -> H $: 1500
or
2. H -> V1 -> C -> H $: 1200

2) "If you take ALL the segments of a flights from a single company, it’s 30% cheaper.
Plus, companies are forming “alliances” to offer cheaper flights to the customers booking
only inside the alliance. If you take ALL the segments of a flight from a single alliance, it’s 20%
cheaper. "
If I have this situation:
F1 (Cm1) -> F2 (Cm1) -> F3(Cm2), according to this, I shouldn't get no discount, but the code says that I get discount for first two flights...
and I won't get no discount for this:
F1 (Cm1) -> F2 (Cm2) -> F3(Cm1)
It doesn't match the description...

Hi,

1) this question is already answered, maybe you didn't see it, or recognized it as same question.

Q: If vacations of interest are three different towns (T1, T2, T3), does it mean that I can, during my vacaton, visit all three towns? I know that I can go through them "unintentionally", but are they in criteria for better combination?
If that is the case, then, what are allowed times for flights, because it doesn't make sense to visit two towns in period assigned for flights_to_vacation, and to spend all vacation on third town?
A: If you take a look at the source code we gave, we iterate over each vacation city. Let say that we are in the iteration working on T1. The algorithm will only try ton let you spend some vacation time in T1. It doesn't matter if you travel through T2 and T3 on this single iteration because you wont spend more time in T2 and T3 than the overlay allows you.

So, the answer would be second combination (1200$)

2) actually it should be:
if previous flight is from same company => 30% discount for this and previous flight
if previous flight is from same alliance => 20% discount for this flight (and previous flight if it wasn't already 30%?)
else no discount

EDIT: Already answered :p

To mention for others (correct me if I'm wrong), do not relay on problem description in pdf, it is not specification of the problem, it is just a guide.
Specification of the problem is in given source. Our program / optimised program should for the same inputs to generate same outputs.

Hi there,
In the problem description it doesn't say anything about the architecture of the environment(or I wasn't able to find anything). Should the program be able to run on multiple machines, or just multiple cores?

The program must be able to run on a multi-core machine, not on multiple machines.

Hi skyel,
Your program have to run on the Intel machine.
If you want to test it, do not hesitate to put it there : http://www.intel-software-academic-program.com/contests/ayc/2012-11/upload/
You'll probably receive an answer saying if your program is running (correct me if I'm wrong !).
Remember that : http://puu.sh/1mpwn

By the way isn't it better to create a new thread for each question ? Just asking! :)

Sincerly,

Timothé Viot,
Engineer student, Insa Rennes 1
France

Hi Tim,
I thought about this, but this thread subject is *-some clarifications, so basically it is on topic, and it saves clicks :) (you don't have to enter each thread to see what's new).
The reason why I asked is because some parallel programming paradigms don't work for multi-machine (OpenMP) while some work for both (MPI).

Cita:

Cédric ANDREOLLI (Intel) escribió:

So as I said, you can do whatever you want as long as your output is the same as the program we gave you.

Even if the program you gave us is non optimal ?

Correct me if I'm wrong, but it could actually be cheaper to go through the same city twice, if the discount compensate for the flights.
Here is an example:

We want to go from A to B.
A => B cost 500$
B => C cost 50$
C => B cost 50$ (all those flights are from the same companies)
It is cheaper to do A => B => C => B (600 * 0.7 = 420$) than to do A => B (500$)

What are we suppose to do in that case ?

As we already said, stick to the output given by the reference code.

This case would probably not happen in real life and as we already said, it would be a time loss to travel through a same city twice. So just don't go twice to the same city from A to B.

Hello everyone,

I have a question. The PDF document explaining the problem says that the input times will be given in epoch format. According to my understanding (please correct me if I'm wrong), the epoch time format is presented as a number of seconds elapsed since midnight, January 1st, 1970. If I understood the reference code and the example inputs correctly, the input times are given as MMDDYYYYhhmmss. So my question is, did I misunderstand something and what should we expect as the input for time based data?
Thanks in advance.

My epoch format reference:
http://www.epochconverter.com/

Best regards,
Nenad

You are right, we should have changed this part in the PDF. It's more clear to use MMDDYYYY.... instead of epoch time in the program call.

So as always, stick to the code :)

You are right, we should have changed this part in the PDF. It's more clear to use MMDDYYYY.... instead of epoch time in the program call.

So as always, stick to the code :)

Are all cities always reachable from home, respectively from conference? Or might there be partitions?

Rock the bits!

Maybe, maybe not, it will depend on the scenario.

Deje un comentario

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