New input files

New input files

Ritratto di Cédric ANDREOLLI (Intel)

Here is a new scenario that you can use to test your program's scalability.

This file is bigger than the previous ones. You should be able to have an idea on the efficiency of your implementation.

We will give you bigger files soon.

I also want to notice that you maybe noticed  some troubles yesterday on the benchmark server results. We were working on the cluster so some of your valid tests failed. Everything should be back to normal right now. Remember that you can test your program on our servers and get a feedback with the URL we gave you by email.

Have a lot of fun.

edit : newinput2.zip added

AllegatoDimensione
Scarica newinput.zip817.82 KB
Scarica newinput3.zip12.01 MB
Scarica newinput4.zip33.3 MB
Scarica newinput2.zip3.22 MB
112 post / 0 new
Ultimo contenuto
Per informazioni complete sulle ottimizzazioni del compilatore, consultare l'Avviso sull'ottimizzazione
Ritratto di Vlad D.

Hello,

My benchmark page has been unresponsive for almost a day. The most recent line in the table says "Running ..." in the Result section, however the Run time section displays an actual time in seconds. All subsequent submissions have had no effect.
Could someone in the staff please take a look at this issue?

Thank you very much!

Ritratto di Tim

Hello,

Thank you very much Cédric for this input file ! It will be very useful !

I have a question about the other upcoming inputs and about the inputs you use in order to test our algorithms.

Will all these inputs contain more alliances ? Because until now, only some of the scenarios have one or two alliances, and it could be interesting to know if the performances will depend on this point too. (Because there is some work on the alliances).

Thank you again for this new example and for all the bigger ones you will send us !

Regards,

Timothé Viot, Engineer student, Insa Rennes 1 France
Ritratto di dan.lincan

Could you please provide the command line arguments with which the work_hard.txt and play_hard.txt files were obtained?

Thank you!

Ritratto di Tim

Hello,

Strange, I thought there was the script.sh in the .zip
I give it to you.

Good luck,

Regards,

Allegati: 

AllegatoDimensione
Scarica script.zip399 byte
Timothé Viot, Engineer student, Insa Rennes 1 France
Ritratto di dan.lincan

The original script.sh is not valid for the test above. This test has the params:
from=CHICAGO, to=SEATTLE for work hard, and vacation_airports = DENVER for play_hard

Ritratto di Tim

I know, it is not the original one. (given with the 9 scenarios)
The script I gave you has the good params... (from CHICAGO to SEATTLE, passing by "DENVER" only). Well if I could have wrong but it works with the input files I have recovered...
It does not work for you ?

Regards,

Timothé Viot, Engineer student, Insa Rennes 1 France
Ritratto di Cédric ANDREOLLI (Intel)

Sorry, I changed the input file and forgot to give the script back.

It's ok now :)

Ritratto di dan.lincan

Quote:

Cédric ANDREOLLI (Intel) wrote:

Sorry, I changed the input file and forgot to give the script back.

It's ok now :)

Thank you!

Ritratto di Cédric ANDREOLLI (Intel)

Hi,

A new file has been added. It is way bigger than the old one.

We also give possible parameters to call the program with the expected outputs. As the file "flights.txt" is bigger, some of you may encounter memory usage problems. This is one of the point that your algorithm should be able to handle.
You can try to run the script with the program we gave you, but during the execution time, you will probably have enough time to make and drink some coffee (It needs about 30 minute to complete).

You will also notice that a new benchmark has been added. You are encourage to re-submit your solution on our servers if you want to have an idea of the running time (the limit is currently set to 200 second maximum).

Finally, I just want to remind you that you will have no idea about the files we will use to evaluate your solution. So don't try to adapt your output to the specific test files we give you.

Have a lot of fun trying to reduce the time on this file :)

edit : I also added the CPU usage so you can see if your solution scale well. CompileScale1 runs on 2 threads, CompileScale2 runs on 2 threads, CompileScale3 runs on 4 threads.

Ritratto di Tim

I have a question that, in my mind, is not that easy to answer, but I ask it anyway :
Could you give us an idea (an interval of time, in seconds) of what "good performances" means for you on the example you updated on the brenchmark ? Not exactly, but an order of idea ?

Thank you very much for those precious examples !

Regards,

Timothé Viot, Engineer student, Insa Rennes 1 France
Ritratto di Cédric ANDREOLLI (Intel)

Execution time is always a hard topic on this contest. I know that some teams prefer to keep their running time secret.

What you can eventually do is :
Open a new topic on this specific inputs and ask people to share their times. Some will do, some won't. This will maybe give you an idea of what contestants have already accomplished.

Ritratto di Heye (aka. slevin7)

Quote:

Tim wrote:

Hello,

Will all these inputs contain more alliances ? Because until now, only some of the scenarios have one or two alliances, and it could be interesting to know if the performances will depend on this point too. (Because there is some work on the alliances).

Hey Tim,

here are two generated scenarios, one with 5 alliances, 2 cities, 1000 flights and one with 22 alliances, 22 cities, 10000 flights. I would like to share the generator, but it is not solely my work, so for now I can only provide the files. Expected outputs are also in the archive.
I can't tell how good the distribution of the flights is since the generator is pretty much random.

Good luck ;)

Allegati: 

AllegatoDimensione
Scarica scenario10.zip15.04 KB
Scarica scenario11.zip139.59 KB
Rock the bits!
Ritratto di Tim

Hey slevin7,
I will try to test our algorithm on these scenarios ! (You do not have anything in the play_hard output, is that normal ?)

Thank you very much for these scenarios ! :)

Regards,

Timothé Viot, Engineer student, Insa Rennes 1 France
Ritratto di Heye (aka. slevin7)

I actually used the original program to produce the output files, so either the proposed cities are not reachable or there is some other issue... I didn't bother working on the play_hard problem so far, so I don't know what else could cause empty play_hard files. In the first and second scenario there is actually no play_hard output as well...
Cédric, could you tell us what causes empty play_hard files?

Rock the bits!
Ritratto di Heye (aka. slevin7)

Well, I just submitted a version of my program that succeeded on all scenarios (provided as download and the online benchmark) but failed on both of the ones generated by me.
So either there is an inconsistency in the generated ones, or the online benchmarks don't stress extreme cases that might have been generated by the scenarios I uploaded....

Here are the differences:

diff of scenario10:
work_hard: original vs modified
2,4c2,4
< Price : 176
< Airline19-393-C1 (12/1 16h26min)/C2 (12/1 17h31min)-112$-80%
< Airline9-797-C2 (12/3 11h4min)/C1 (12/3 11h8min)-108$-80%
---
> Price : 184.1
> Airline8-27-C1 (12/1 13h14min)/C2 (12/1 14h1min)-103$-70%
> Airline8-868-C2 (12/2 13h32min)/C1 (12/2 14h9min)-160$-70%

diff of scenario11:
work_hard: original vs modified
2,4c2,4
< Price : 403.2
< Airline19-1329-C1 (12/1 16h27min)/C22 (12/1 16h5min)-398$-80%
< Airline9-6044-C22 (12/2 9h9min)/C1 (12/2 9h48min)-106$-80%
---
> Price : 404
> Airline11-4236-C1 (12/1 11h22min)/C22 (12/1 11h35min)-298$-100%
> Airline9-6044-C22 (12/2 9h9min)/C1 (12/2 9h48min)-106$-100%

Well, the difference is just 80 cents, but hey, we want to save every single dime :D

Rock the bits!
Ritratto di Cédric ANDREOLLI (Intel)

The benchmarks are just a way for you to test the scalability of your program. They are not really used to test the correctness of your program. We could add more tests on the benchmarks but this will decrease the availableness of our servers.

You have to check the correctness of your program. But as I already said, 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.

Ritratto di Nikolay Kuznetsov

Why are you using strange backquote characters in the judges' code? Why are you not use typical " (decimal ASCII code 34)?

Ritratto di Cédric ANDREOLLI (Intel)

Could you send me the output you get by mail please ? I don't see what you are talking about.

Ritratto di Nikolay Kuznetsov

A piece of your code is:

output<<"“Work Hard” Proposition :";

A phrase Work hard is surrounded by quotes. It works incorrectly on my computer. Can I write like that,

output<<"\"Work Hard\" Proposition :";

?

Ritratto di Cédric ANDREOLLI (Intel)

I've taken a look at your code and the way you output is not correct. You write <93>Work <94>.

If you just need to output the double quotes, you indeed need to add backslashes.

Ritratto di eviltosha

First of new inputs seems to have two optimal solutions. Here they are (for work_hard problem):

-------- (reference solution)
“Work Hard” Proposition :
Price : 185.382
UNITED STATES Airlines-143811646172561-CHICAGO (4/22 9h15min)/SEATTLE (4/22 18h15min)-67.8221$-70%
UNITED STATES Airlines-958384950201540-SEATTLE (12/20 9h13min)/CHICAGO (12/20 18h13min)-197.009$-70%

------ (alternative solution)

“Work Hard” Proposition :
Price : 185.382
UNITED STATES Airlines-143811646172561-CHICAGO (4/22 9h15min)/SEATTLE (4/22 18h15min)-67.8221$-70%
UNITED STATES Airlines-650474052719327-SEATTLE (12/11 9h13min)/CHICAGO (12/11 18h13min)-197.009$-70%

Any comments? Is program which outputs second solution valid?

Ritratto di Cédric ANDREOLLI (Intel)

Actually, the script used to generate this file was done very quickly to provide a larger input for contestants.

This kind of problem should not happen any more on the new inputs (included the newinput2.zip). I will update newinput.zip to remove the second solution.

Thanks for the warning.

Ritratto di Cédric ANDREOLLI (Intel)

Actually, the script used to generate this file was done very quickly to provide a larger input for contestants.

This kind of problem should not happen any more on the new inputs (included the newinput2.zip). I will update newinput.zip to remove the second solution.

Thanks for the warning.

Ritratto di eviltosha

When new inputs will be added? I want to test my solution with something really big =)

Ritratto di Tim

Hello Cédric,

I have a suggestion for one of the next new inputs.
What if the work_hard and play_hard outputs are bigger ? (i.e. the path between city A and B (and same thing with the airports of interest) is longer).

Edit : I know it's tricky because of the constraint we have between flights but... It could be very interesting ! :)

Regards,

Timothé Viot, Engineer student, Insa Rennes 1 France
Ritratto di Cédric ANDREOLLI (Intel)

Well I do not generate test files manually as you can guess and it takes a lot of time to find interesting program calls and to check the validity of the output. The point is that the file flight.txt that we provide is created from real flights and in real life, you would not find a cheap flight from London to Rome that stop at every cities between London and Rome. :)
What you can do t get (probably) more flights is to increase the time were flights are possibles.

Ritratto di Tim

I will try that (when my program will be ready) but you are right, in real life, travels won't have more than 2 or 3 correspondences (or a maximum of 4 : little city of departure from country A -> capital from country A -> capital from country B -> little city of arrival from country B. And some more for the play hard travel)
I will modify the parameters when I will be sure I'm ok with the initials one.

Thanks for the advice. :)

Regards,

Timothé Viot, Engineer student, Insa Rennes 1 France
Ritratto di Dusan V.

Hmm, so, would the final list of flights be generated from real life (to make some assumptions) or?

EDIT: Also, how the output is verified?
Because of prices are in floating point, and because addition of floating point isn't associative operation on PC, wouldn't it be impossible to verify output. Even if there is some tolerance in final price, it would be pretty hard to make large number of flights, without getting close results for multiple flights?

Thanks.

Ritratto di Cédric ANDREOLLI (Intel)

We don't want you to make any assumption on the flight list :)

For the output, I already explained on an other topic that we are using a diff.

Ritratto di Andrei S.

Quote:

Dusan V. wrote:

Hmm, so, would the final list of flights be generated from real life (to make some assumptions) or?

EDIT: Also, how the output is verified?
Because of prices are in floating point, and because addition of floating point isn't associative operation on PC, wouldn't it be impossible to verify output. Even if there is some tolerance in final price, it would be pretty hard to make large number of flights, without getting close results for multiple flights?

Thanks.

Hi!

Cedric said at some point they just diff the files, which sounds reasonable enough to me. The problem states that you should have the same output as the program they provide. Perhaps you could do the calculations in the same order?

Andrei

Ritratto di Tim

Hi,

Is it really a hard constraint to keep associativity of the floating addition ? You can do probably what you want (even calculating step by step without lose associativity). Finaly, is there really a problem in that ?

Moreover, I'm not sure but, real flights are won't have more than 2 digits after the decimal point (on websites, the price is considered like that). But I have maybe wrong and it is more sure to keep all the information in the number by keeping the order.

Regards,

Timothé Viot, Engineer student, Insa Rennes 1 France
Ritratto di Dusan V.

Quote:

Tim wrote:

Hi,

Is it really a hard constraint to keep associativity of the floating addition ? You can do probably what you want (even calculating step by step without lose associativity). Finaly, is there really a problem in that ?

Moreover, I'm not sure but, real flights are won't have more than 2 digits after the decimal point (on websites, the price is considered like that). But I have maybe wrong and it is more sure to keep all the information in the number by keeping the order.

Regards,


Hi Tim,

Yes, first I need to see if it would cause invalid result (I'm just guessing because od large number of combinations).
Unfortunately, for my implementation, it's impossible to keep order of adding prices :/.

Ritratto di Nikolay Kuznetsov

CompileScale3 runs our scenario 12 with nbthreads=4

Is "scenario 12" the same as "newinput2.zip"? If it's true, then our program works locally faster a little :) More exactly, 5 times faster...

Ritratto di eviltosha

This was said in another topic
Quote:

Cédric ANDREOLLI (Intel) wrote:

Do your program succed the newinput2 ? This test is almost the same size that the CompileScale2.


so I suppose, only sizes are similar, not whole scenarios. Anyway your computer hardware differs from the cluster, so you would get different run times even on same tests.
Ritratto di dan.lincan

Hello.

When can we expect bigger tests? I'm asking because weekend is coming and it would be nice to be able to test scalability ( most of us will probably work this weekend ).

Thank you!

Ritratto di Axel S.

Quote:

Nikolay Kuznetsov wrote:

Is "scenario 12" the same as "newinput2.zip"? If it's true, then our program works locally faster a little :) More exactly, 5 times faster...

The scenarios on the cluster aren't the same ;)

Axel Shaïta, U.F.R Sciences Reims
Ritratto di Andrei S.

I can confirm they are not the same - on my machine, newinput1 takes about 15s, compared to ~1100s on the cluster.

Andrei

Ritratto di Tim

Quote:

Dusan V. wrote:
Hi Tim,

Yes, first I need to see if it would cause invalid result (I'm just guessing because od large number of combinations).
Unfortunately, for my implementation, it's impossible to keep order of adding prices :/.

Hi Dusan,

You should try on the last inputs that Cédric generated to see if results are exactly the same. Did you do it ? I personally can't do anything if not (I could but I can't forget your code if you show it to me :C). For that, let's wait Cédric for the answer because it may be possible that, for evaluations, only 2 digits after decimal point would be the worst case.
But I don't want to communicate bad information even if it sounds logical for me, so do not care about that. I'm only discussing about this point.
If yes, the you are safe. :D Did it works on the cluster and on the last inputs ?

For the scenarios, I confirm, they are not the same on the cluster. I can't find the thread but I am sure I already read that.

Regards,

Timothé Viot, Engineer student, Insa Rennes 1 France
Ritratto di Cédric ANDREOLLI (Intel)

It shouldn't be a problem even if you do not realize your arithmetic operations in the same order. There shouldn't be any approximation error on the first significant numbers of a float when you compute the costs.

If the problem appears, we will probably manage this on the cluster side. But for now, outputing the same result as our program is part of the specifications.

Ritratto di Dusan V.

Quote:

Tim wrote:

Quote:

Dusan V. wrote:
Hi Tim,

Yes, first I need to see if it would cause invalid result (I'm just guessing because od large number of combinations).
Unfortunately, for my implementation, it's impossible to keep order of adding prices :/.

Hi Dusan,

You should try on the last inputs that Cédric generated to see if results are exactly the same. Did you do it ? I personally can't do anything if not (I could but I can't forget your code if you show it to me :C). For that, let's wait Cédric for the answer because it may be possible that, for evaluations, only 2 digits after decimal point would be the worst case.
But I don't want to communicate bad information even if it sounds logical for me, so do not care about that. I'm only discussing about this point.
If yes, the you are safe. :D Did it works on the cluster and on the last inputs ?

For the scenarios, I confirm, they are not the same on the cluster. I can't find the thread but I am sure I already read that.

Regards,


Hi Timothe,

thanks for good will to help me.
Unfortunately, algorithm is not completely transformed into code yet (it will be propably in two days), so when it would be completed, I'll test it.
Problem with rounding floating point is just my assumption, because of large number of combinations, it would be impossible to create file with guaranteed minimum difference between prices.
But, let's see how the program will behave in reality.

Regards, Dusan

Quote:

Cédric ANDREOLLI (Intel) wrote:

It shouldn't be a problem even if you do not realize your arithmetic operations in the same order. There shouldn't be any approximation error on the first significant numbers of a float when you compute the costs.

If the problem appears, we will probably manage this on the cluster side. But for now, outputing the same result as our program is part of the specifications.


Hi Cedric

Ofcourse, i'll try to have same output as original source.

Regards, Dusan

Ritratto di Tim

Some more questions that could be interesting :

Can the string we pass in parameters be wrong ?
I explain :
For example, having cities that don't exist in flights file or some data alike that are particular cases which will be put our program in difficulties ?
Have we to deal with these type of parameters ?

Regards,

Timothé Viot, Engineer student, Insa Rennes 1 France
Ritratto di eviltosha

As was said,
Quote:

Cédric ANDREOLLI (Intel) wrote:

Hi,

The goal of this contest is not to get you on tricky scenarios. We just want you to optimize the given problem.


So I think there won't be such inputs. But anyway, you can analyze behavior of reference solution and make your program alike.
Ritratto di Dusan V.

Quote:

Tim wrote:

Some more questions that could be interesting :

Can the string we pass in parameters be wrong ?
I explain :
For example, having cities that don't exist in flights file or some data alike that are particular cases which will be put our program in difficulties ?
Have we to deal with these type of parameters ?

Regards,


Hi Timothe,

not completly sure about that. In original source, you can find on few places where it's checked for not valid data, but, I'm pretty sure that purpose of this contest is not testing robustnes of this program, so, let's assume that input is always valid, until someone from Intel answer.
Also, I'm pretty sure that if flight doesn't exist in flights list, is valid input.

Regards, Dusan

Ritratto di pierrick.brunet.tb

IMO inputs are correct for reference source code.
For example, we can see in some example some date like : 12092012300000
As you can see, we are asking for the 30th hour of the day so it is not a correct input BUT the intel source code manage this issue so we have to do the same.

Ritratto di Cédric ANDREOLLI (Intel)

I've just added a new set of files that you can test on your machine.

A new benchmark will be available on the cluster soon (1 or 2 hours)

Ritratto di eviltosha

I've found another bug in scenarios:
Scenario5 has 2 exactly same flights with different IDs:

10;Paris;10242012000000;Rio;10242012150000;1800;Expensive Airlines
7;Paris;10242012000000;Rio;10242012150000;1800;Expensive Airlines

Thus there're at least 2 paths with same cost.

Ritratto di Cédric ANDREOLLI (Intel)

Yes this scenario were generated by hand to give some indications to help understand the problem. Copy/Paste is a very bad tool :)

But anyway, it you are having problems with this scenario, just change the price of one of the flights.

Ritratto di Axel S.

Hi,

is it normal that I've 0 second on ​​"CompileScale5"?

thanks!

Axel Shaïta, U.F.R Sciences Reims
Ritratto di Cédric ANDREOLLI (Intel)

Yes the test was probably run when I was uploading the files.

You can retry.

I will also add some informations about the new tests soon.

Ritratto di Vlad D.

Hello,

I keep getting "ERROR - Output error" on CompileScale3, even for a previous backup version of my program that i had saved, which used to
work well. CompileScale1 and CompileScale2, as well as my local tests work fine.
Could this be a problem on the cluster side?

On a different note, what does a very large reported CPU usage mean? I'm talking about > 2000%.

Thank you.

Pagine

Accedere per lasciare un commento.