Ambigious Scoring
Hi all,
This problem sounds really cool because it's not IO bound. However in the problem description you wrote:
"Deductions for not finding the optimal solution will be in force"
Could you be more precise about this sentence? If some entries find not the best score, but with speed of light, how did you manage this? Could you give us the scoring formula?
Cheers,
Arnaud
| |
Re: Ambigious Scoring
Hi all,
This problem sounds really cool because it's not IO bound. However in the problem description you wrote:
"Deductions for not finding the optimal solution will be in force"
Could you be more precise about this sentence? If some entries find not the best score, but with speed of light, how did you manage this? Could you give us the scoring formula?
Cheers,
Arnaud
The idea was to not reward solutions that quickly find a heuristically close answer to get a low execution time. The judges have no idea how the deductions would be assesed, at this time. Perhaps as a percentage of how far off from the optimal solution, or maybe take off 100% of the points for that solution.
--clay
| |
Re: Ambigious Scoring
The idea was to not reward solutions that quickly find a heuristically close answer to get a low execution time. The judges have no idea how the deductions would be assesed, at this time. Perhaps as a percentage of how far off from the optimal solution, or maybe take off 100% of the points for that solution.
--clay
Emm.. Again, this sounds really weird for an optimisation contest :-) We don't have an idea of the data, and now you tell us that we don't have any idea about the scoring method :-) Maybe you could ask to a non-programmer to try that contest, he will almost get the same chance to succeed..
| |
Re: Ambigious Scoring
Emm.. Again, this sounds really weird for an optimisation contest :-) We don't have an idea of the data, and now you tell us that we don't have any idea about the scoring method :-) Maybe you could ask to a non-programmer to try that contest, he will almost get the same chance to succeed..
100% agree. Making scoring criterion public after performance is ridiculous.
Imagine some sport competition. Every competitor go to the area and do *something*. After the performance, competitors get to know whether it was sprint or high jumping or something else.
---------------------------------------------
All about lock-free algorithms, multicore, scalability, parallel computing and related topics:
www.1024cores.net | |
Re: Ambigious Scoring
The idea was to not reward solutions that quickly find a heuristically close answer to get a low execution time. The judges have no idea how the deductions would be assesed, at this time. Perhaps as a percentage of how far off from the optimal solution, or maybe take off 100% of the points for that solution.
--clay
I think scoring for non-optimal solution is quite critical for us to select the algorithms. A clear standard for final score is advised.
| |
Re: Ambigious Scoring
I think scoring for non-optimal solution is quite critical for us to select the algorithms. A clear standard for final score is advised.
Could be useful to introduce a minimum total value for each problem. When you achieve (or of course go over) this value with a collection of items you can stop the searching and print the output. The computation time could be used for scoring criteria.
| |
Re: Ambigious Scoring
Emm.. Again, this sounds really weird for an optimisation contest :-) We don't have an idea of the data, and now you tell us that we don't have any idea about the scoring method :-) Maybe you could ask to a non-programmer to try that contest, he will almost get the same chance to succeed..
I think he is trying to say that you can't spend one full week working on the best answer yourself, and then have your program just spit out the same data you got. Anyone would probably know it is a lot faster for a program to copy a text file straight into the application than to work the problem, make sure it is right, check for exceptions, re-run if there is one, and THEN display the text on the screen.
| |
Re: Ambigious Scoring
If we assume that there is one optimal answer, then the question becomes what penalty should be accessed for not getting that answer after the computation terminates. If PlayerA spends 20 seconds to find the optimal answer and PlayerB takes 5 seconds to find an answer that is "close", should PlayerA recveive a lower score since her code ran 4 times slower? If the ratio of PlayerB's results to the optimal solution is 10% less (i.e., the total cost packed is 10% below the optimal), should PlayerB not get any points for the submitted application? And how should we judge PlayerC's entry that simply runs through the item list, adding things into the knapsack until nothing else will fit, and then reporting the total cost in 0.05 seconds?
If we had set a time limit on the computation time allowed and the best solution found to that point would be judged, then things are a little easier. The closer the results are to optimal (and the faster the code), the better the score. As it is, the judges will need to use test cases that can be solved by most applications within a generous time frame (say 10-15 minutes). The disparity of possible scenarios is why we've been vague on the scroing details.
At this time, then, the only way to make it fair and have everyone find the optimal solution would be to make it "all or nothing". If you don't compute the right answer for a given test case, you will receive zero points for that test case. If there are four tests and you only get 2 of them with the right answer, your maximum score would be 50.
If the judges adopt this scoring criteria, will that be acceptable?
--clay
| |
Re: Ambigious Scoring
If we assume that there is one optimal answer, then the question becomes what penalty should be accessed for not getting that answer after the computation terminates. If PlayerA spends 20 seconds to find the optimal answer and PlayerB takes 5 seconds to find an answer that is "close", should PlayerA recveive a lower score since her code ran 4 times slower? If the ratio of PlayerB's results to the optimal solution is 10% less (i.e., the total cost packed is 10% below the optimal), should PlayerB not get any points for the submitted application? And how should we judge PlayerC's entry that simply runs through the item list, adding things into the knapsack until nothing else will fit, and then reporting the total cost in 0.05 seconds?
If we had set a time limit on the computation time allowed and the best solution found to that point would be judged, then things are a little easier. The closer the results are to optimal (and the faster the code), the better the score. As it is, the judges will need to use test cases that can be solved by most applications within a generous time frame (say 10-15 minutes). The disparity of possible scenarios is why we've been vague on the scroing details.
At this time, then, the only way to make it fair and have everyone find the optimal solution would be to make it "all or nothing". If you don't compute the right answer for a given test case, you will receive zero points for that test case. If there are four tests and you only get 2 of them with the right answer, your maximum score would be 50.
If the judges adopt this scoring criteria, will that be acceptable?
--clay
Sounds good to me. Thanks clay.
| |
Re: Ambigious Scoring
If we assume that there is one optimal answer, then the question becomes what penalty should be accessed for not getting that answer after the computation terminates. If PlayerA spends 20 seconds to find the optimal answer and PlayerB takes 5 seconds to find an answer that is "close", should PlayerA recveive a lower score since her code ran 4 times slower? If the ratio of PlayerB's results to the optimal solution is 10% less (i.e., the total cost packed is 10% below the optimal), should PlayerB not get any points for the submitted application? And how should we judge PlayerC's entry that simply runs through the item list, adding things into the knapsack until nothing else will fit, and then reporting the total cost in 0.05 seconds?
If we had set a time limit on the computation time allowed and the best solution found to that point would be judged, then things are a little easier. The closer the results are to optimal (and the faster the code), the better the score. As it is, the judges will need to use test cases that can be solved by most applications within a generous time frame (say 10-15 minutes). The disparity of possible scenarios is why we've been vague on the scroing details.
At this time, then, the only way to make it fair and have everyone find the optimal solution would be to make it "all or nothing". If you don't compute the right answer for a given test case, you will receive zero points for that test case. If there are four tests and you only get 2 of them with the right answer, your maximum score would be 50.
If the judges adopt this scoring criteria, will that be acceptable?
--clay
Agree: correct solution is the optimal one.
That's the score criteria that is explained in the problem description, as it doesn't say anything about getting closer to the optimal result.
http:///www.rpenalva.com | |
Re: Ambigious Scoring
If we assume that there is one optimal answer, then the question becomes what penalty should be accessed for not getting that answer after the computation terminates. If PlayerA spends 20 seconds to find the optimal answer and PlayerB takes 5 seconds to find an answer that is "close", should PlayerA recveive a lower score since her code ran 4 times slower? If the ratio of PlayerB's results to the optimal solution is 10% less (i.e., the total cost packed is 10% below the optimal), should PlayerB not get any points for the submitted application? And how should we judge PlayerC's entry that simply runs through the item list, adding things into the knapsack until nothing else will fit, and then reporting the total cost in 0.05 seconds?
If we had set a time limit on the computation time allowed and the best solution found to that point would be judged, then things are a little easier. The closer the results are to optimal (and the faster the code), the better the score. As it is, the judges will need to use test cases that can be solved by most applications within a generous time frame (say 10-15 minutes). The disparity of possible scenarios is why we've been vague on the scroing details.
At this time, then, the only way to make it fair and have everyone find the optimal solution would be to make it "all or nothing". If you don't compute the right answer for a given test case, you will receive zero points for that test case. If there are four tests and you only get 2 of them with the right answer, your maximum score would be 50.
If the judges adopt this scoring criteria, will that be acceptable?
Every precisely defined criterion is Ok with me.
---------------------------------------------
All about lock-free algorithms, multicore, scalability, parallel computing and related topics:
www.1024cores.net | | |
