# Questions

## Questions

1. What should we do if answer isn't unique (i.e. there are not valid paths or there are multiple the cheapest paths)?

2. You use "double" for flights' cost. How many digits after decimal point must we output? How do you decide to check participants' answers?

3. Please, explain formal rules of discounts.

36 posts / novo 0
Para obter mais informações sobre otimizações de compiladores, consulte Aviso sobre otimizações.

Hi Nikolay,

I'm not from Intel but I can answer to several of your question and I will do my best for that ! :)

1.
Cédric already said that we have to stick to the initial code and the initials output,
It answers to question 1. :
Answer is unique because in the "find_cheapest(...)" function, you have the following test :

```
if(compute_cost(temp, alliances) < compute_cost(result, alliances))

{

result = temp;

}

```

If you stick to the code, it tells you that the you will take the fisrt answer you find, i.e. if two travels have the same cost, the second one will not be chosen by the test. So for you, the goal is to find the cheapest travel between A - B (or A - B via an airport of interest) and the same idea from A to B.
So, as a conclusion, if you stick to the code, the first cheapest flight you find is the good one.

2.
Here, is the same, in real life, you won't pay something like 104.1234567890123 \$ but you will only pay 104.12 \$ or, at worst 104.13 \$, and the difference is pretty tiny. So as usual, in my opinion, you should maybe stick to the code and not be afraid by the ten digits after decimal in the last scenario flights.

3.
I will try to make a formal answer :
We have at least 2 flights in a travel (because A -> B -> A is the shortest path).
Whether x, y are consecutive flights, "f" and "discount" functions and S, T are sets of segments and P a segment.
S are all the segments where all the flights are from the same company,
T are all the segments where all the flights are from companies both in a same alliance,
P is the travel from A to A via B (and an other city for play_hard) represented by a segment.
S is included in T.

Then we have this :
discount(x) = f(x,y)
Where :

f (x, y) = { 0.7 if x and y belongs to a segment included in S
{ 0.8 if x and y belongs to a segment included in S minus T
{ else, it's 1.

It is possible that I did some mistake because I created this formal rule by checking the code.
Do not hesitate to read this !

4. Okay, I can't answer to that. :D

Cédric, if you want me to stop answering in your place, do not hesitate to tell me.

I hope it helps you Nikolay and have a nice week-end.

Do not hesitate to read clarifications from this post : http://software.intel.com/fr-fr/forums/topic/333430

Regards,

Timothé Viot,
Engineer student, Insa Rennes 1
France

Hi Tim,

I have understood that you are a participant like me, but I should like to get official answers from judges.

But nevertheless let's discuss these items :)

1. I think, if you must output answer which is absolutely byte-to-byte equal judges' answer - it's very strange condition. Because our task to find the cheapest path (and we must do it very fast), and if we have found the another cheapest path - it's normal situation. This condition restricts our possibilities.

2. If judges will be use byte-to-byte comparing of files then they must decide how many digits we should output. It's obviously.

3. Thank you

4. I hope Russian judges will spend time for answering.

Citação:

Nikolay Kuznetsov escreveu:

1. What should we do if answer isn't unique (i.e. there are not valid paths or there are multiple the cheapest paths)?

2. You use "double" for flights' cost. How many digits after decimal point must we output? How do you decide to check participants' answers?

3. Please, explain formal rules of discounts.

I am also interested in the answer to the first question.

Hi,

The goal of this contest is not to get you on tricky scenarios. We just want you to optimize the given problem. So :
1 - We will not give you problems with two possible answers. There will only be one valid solution.
2 - You should use doubles too
3 - The discount has already been explained several times on this forum, just take a look at the other topics.
4 - I can try to send the information to the Russian team but I can't guaranty that they will answer. I don't speak Russian so I can't answer on the Russian forum. If Russian contestants want a quick "official" answer, the best way is to post on this forum or to send me an email.

I hope that my answers helped you.

I would suggest to think your algorythm with only one answer possible. this should probably make it more simple/optimized.

How do we provide description of our program? Is description.txt file in submission archive sufficient?

Yes, a .txt file is sufficient.

On the compute_path function, we can see that : "if we have a flight between the origin city and the target city, we add this to the list". It suggests that there will not have treaky input like : " there is not enought time to travel between this 2 cities"?

Hi pierrick,

The algorithm does not make a difference on which test the flight doesn't succeed.
For example, if you add a City that is not concerned by the flights, the algorithm will just return an empty list of flights. Then for the output, you will get a null price and no flights.
I already tested that with a city where times were not good and it returned that.
Then if you want to stick to the output, do not return anything and write a null price in the outputs.

But as you can see there[...] We don't want to get you on tricky test files, we just want you to be able to write a program able to scale on different inputs.[/quote]
We won't have tricky inputs ! :)

Regards,

Timothé Viot,
Engineer student, Insa Rennes 1
France

Is it true what departure_time_max < arrival_time_min for all tests?

I would consider such a thing as "tricky input" and I am not going to spend time making my program bullet proof for invalid inputs. The goal is to have a correct algorithm for correct inputs, so they probably wouldn't do that. I can't give an official answer, but for now I wouldn't worry about it.

Rock the bits!

We will not test this special case

i.e. you guarantee that departure_time_max < arrival_time_min for all your tests?

In fact it would be nice to have some assurances:

I assume that there is no doubt about these:
All numeric parameters are positive (in files as well as program arguments)
departure_time_min < departure_time_max < arrival_time_min < arrival_time_max
vacation_time_min < vacation_time_max
vacation_airports is a set
from != to
from ∉ vacation_airports
conference ∉ vacation_airports
take_off_time < arrival_time
max_layover < arrival_time_min - departure_time_max
max_layover < vacation_time_min
Every flight is unique (at least with its ID)
There are not two flights with the same take_off_time, land_time and price, that are getting the same discount that are on the shortest path.
The parameters, the flights.txt and the alliances.txt are syntactically sound.

But, is it possible that...
...airlines in the alliance.txt file have no entry in fligths.txt?
...there are two flights with the same take_off_time, land_time and price, that are getting the same discount that are NOT on the shortest path?

Cities where flights take off are not reachable, including home or conference (I haven't seen it for vacation destinations yet, but it would probably be the same as for the work_hard problem)

That's all I can think of right now...

Rock the bits!

Once again, we will not provide tricky inputs. The kind of input that we will use to evaluate the solutions will be pretty much the same we are currently using on the cluster (but with different ratio on the alliances.txt and flights.txt)

How much hardware threads benchmark machine have?

I think I read that the machine will have 40 cores (so 80 threads I guess?)

About the output, you said we should have the same output than the reference. I did a modification in my code and instead of 4010.79\$, I have 4010.78\$. The real value is : 4010.785\$. Did my output will be valid or not? (other lines are corrects)

Cedric said that for now outputs are checked via diff with reference output, thus your output won't be valid. But he also said (if I remember right) that if there'll be significant difficulties with output, they might use different compare technique (some kind of parser I suppose).
So try to correct your program, if it's very hard, ask Cedric for new validation.

That is correct.

If you can't succeed the benchmark because of output errors, please let me know. I will check on the cluster to see if this pretty bad case appears.

I try to check by myself and contact students when I detect some recurrent output errors but with all the student registered, I probably miss a lot of things.

Thanks for you answer. To avoid this kind of issue, I compute another time total price using your function but only for output travels. It doesn't take a lot of time (except if we do computation with a lot of vacation city for play_hard).

Even with this look like fixed, I doesn't succeed tests on cluster but I succeed tests on my computer. Can you check result for me please? (you can use my email ;-) )

I think you shouldn't overuse help from Intel engineers. Try to find out and fix problem by yourself, and only in the worst case ask organizers for a help.

It seems that when the work_hard has no solution, you output a price equal to -1.97374e+34 instead of 0 :)

I know I shouldn't overuse help from cedric but it is really hard when output are good on you computer but not on the cluster. May be you can show result for : diff play_hard* && diff work_hard*?
It can be very usefull.

Thanks you very much for your feed back

Showing the diff between your result and our result would be pretty much the same thing that letting you access the output.

So unfortunately, I can't do that.

Hi pierrick,

Citação:

Cédric ANDREOLLI (Intel) escreveu:

It seems that when the work_hard has no solution, you output a price equal to -1.97374e+34 instead of 0 :)

I think that this should be enough. You simply didn't initialize the price of the travel. You should have a good result if you initialize it to 0 before trying to find a travel. But maybe you deduced that before I posted that (so my answer would be useless...) ! :)

Regards,

Timothé Viot,
Engineer student, Insa Rennes 1
France

Most of the time, indication are enought for me but thanks for your help tim. Sadly, it seems to have another issue in my code because it doesn't work well now.

Why don't you want to show output for tests on the cluster? I thought you wouldn't use these tests to give the final mark for user?

Regards,

Citação:

pierrick.brunet.tb escreveu:

Most of the time, indication are enought for me but thanks for your help tim. Sadly, it seems to have another issue in my code because it doesn't work well now.

Why don't you want to show output for tests on the cluster? I thought you wouldn't use these tests to give the final mark for user?

Regards,

Hi,

because someone could upload any program and use benchmark machine for own uses.

Regards, Dusan

Hey Nikolay,

You should probably ask to Cédric by mail which submission but I'm not sure because it would say that all our submissions are stored on the cluster and I think that it is a bit "big" for the cluster to do that. They may have been deleted.

If you ask this question, maybe it is because you lost your sources or you want to compare your new program with an older version of it. For that, I recommend you to take a look at something like SVN or GIT (I prefer this last one personally). To keep it in a safe place, you can use sourceforge. (This website have the interest to keep your project private if you want to, and for this contest... you know what I mean... :p)
I know that it is not useful for your answer because what is lost, is lost, but I think this is a very nice tool for further things (easy to "install" and quite easy to use). With that, you will NEVER have a problem with old sources (or with a "cp old" you deleted or disk problems or data loses like that...) because you can always return to an old version and... well... many things that VCS are made for...

I hope it could help more that one person in the future,
Regards

Edit : Sorry for the advertisement for the VCSes, but it's just cool. :x

Timothé Viot,
Engineer student, Insa Rennes 1
France

We want to make a description in pdf in Russian. Will it be accepted?

language accepted : Russian, French, English

One last time - what if our program will find optimal solution with repeating cities?
Right now we have 2 options - to write validation and when such path is found, run non-optimal algorithm to find path without repeating, or to hope that there won't be any such paths, or organizers will fix it if there're some.
I prefer second way, but I can't be sure about tests...

In this case, it won't be the optimal solution regarding the rules because your implementation must stick to the reference program output.

This topic has been explained several times on the forum and I the answer has always been the same : Not the same city twice on the same segment.

So even if you find a solution in 1 second when other need 2 minutes, the solution won't be valid.

I have a similar problem, usually my algorithm works fine with discounts, but in very rare cases it doesn't find the optimal solution (402\$ instead of 401.2\$) so I have to accept that pretty close is not the same as exact. And therefore need to use more ram and time to get the right solution, just in case this rare case is coming up. The submissions are only comparable if all solutions have to have the same output...

Rock the bits!

Heye, I have opposite problem =) Our code may find cheaper solutions (or find solutions when reference code doesn't find any), but these solutions have repeating cities in segments.