PROBLEM LINK:
Author: Istvan Nagy
Tester: Shiplu Hawlader
Editorialist: Praveen Dhinwa
DIFFICULTY:
CHALLENGE
PREREQUISITES:
expectation value, random strategies.
PROBLEM:
The problem is an interactive problem. In the problem, you play the famous darts game “501 with double out”.
Detailed rules of the game are described in the problem statement.
EXPLANATION
#Various Strategies
Simplest Strategy
Just target the middle of the board each time.
Another Simple Strategy
You can just target the middle of the double 1.
Using Shortest paths
Calculate the shortest path to 0. You can make a simple improvement in it, if you prefer to target at simple sectors.
Better Strategies
Find the preferred place. These are the possible ideas to finding the preferred places.
- If the preferred place s cover large triple, then you can use it at the beginning to decrease your score faster.
- If the preferred place s cover double, then you should try to use it at the end.
- Try to checkout with double 16 because if you miss it with simple 16 than you have to throw double 8, after that double 4 and so on.
- If you have to throw double odd and you miss it e.g. double 15 and you throw simple 15 than you have to throw another odd number, so the pro’s target
not the middle double 15 instead of the outside (except last dart in hand).
Reason of getting lot of wrong answers in the problem
- Not using fflush(stdout).
- Outputting extra values than needed.
- Using more than given tries in the practice session of the game.
Understanding the parameters
You cannot target outside of the 1.2 radius (in real life outside the dart table contain wall protector) but you would like to target it.
The deviation used by the author:
- if the seed 0 mod 5 than the standard deviation [0.01,0.1] this represent a club player.
- if the seed 1 mod 5 than the standard deviation [0.3,1] this represent a beginner.
- if the seed other than the standard deviation [0.1,0.3] this represent a hobby player.
Any other solutions
Please share your solutions about the problem too. It would be interesting to know about your beautiful strategies.
Authors comments
In the contest the online judge and the offline tester different little bit in different way, to minimize the possibilty of cheating. So the offline tester using different seed for training mode than the online judge. So I would like to put in this in the editorial if you agree (but maybe you should fix the english 
)
We’ve added on the problem page “Final Darts.jar”. The judge in the training mode use different seed than in the compete mode. This jar is behave the same as the online judge (and using the same shift), in this aspect the older offline tester doesn’t follow this property (deliberately).
I check the some of the top subbmissions yesterday and this jar produce the same score as the online judge (except one subbmission).
This is the way how we generate the 30 seeds:
int seed = 123454321;
int df = 1231661;
for(int i=1;i<30;++i)
{
seed+=df;
if(i>3) df+=320;
}
Note
Please note that editorial is not complete yet. I will read strategies of various participants and will try to explain them in upcoming few days.
Please share your solutions and strategies too.