DARTS - Editorial

PROBLEM LINK:

Practice
Contest

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 :slight_smile: )

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.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

2 Likes

After the first rejudge I’ve made a [score table][1] of the 12 best solution which shows the score on the test cases.

As I know we will re-rejudge :slight_smile: those solutions which get ACC on the contest but not get ACC at the rejudge.
[1]: https://docs.google.com/spreadsheets/d/1NHE1uF9uQo-XcPYSH2x565hnyWGVflrp5elKB10g2KU/edit#gid=1339109496

2 Likes

I have noticed that during the rejudging some of my AC submissions have turned into compilation error :
The error shown is <bits/stdc++> no such file or directory found
I observed that this is happening only with users who have used <bits/stdc++> as header file and submitted in c++4.8.1.
I dont understand why this is happening.I have also sent a mail to codechef in this regard but i havent got any response.

The Tester’s solution is not available. (Reason: Access Denied)

Its not only me but some other people also who are facing the problem of compile error … Hope rejudging takes place

@iscsi: Cool statistics! @rednivrug15, @admin: Maybe only the submissions which got Compilation Error could be rejudged, in order to finalize the rejudge sooner (hopefully there aren’t too many such submissions). From what I understand, this is the issue that occurred.

1 Like

@iscsi: Can you also add the standard deviation of each test case in the table? I also have another question. The offline tester used the same seed for the training darts, as well as for the 99999 “official” darts. On my machine I was able to write a solution which took advantage of this and scored around 3 times better than my winning solution during the contest (because I was able to predicit within some limits what the deviation of each “official” dart would be). However, this didn’t work on the online judge. Was the online judge different in this aspect from the offline tester?

1 Like

@mugurelionut: Did you check the new jar what we upload as a Final Darts.jar on the contest page? The online judge was written in c++, but I try to implement the same in the jar except one thing. In the official (and the final jar) when we init the mersenne twister for training we shift the seed with 0x15c51 :slight_smile:

(So it looks like in the code : MersenneTwister mtTraining(seed+0x15c51); ).

@mugurelionut: I checked maybe the last day with this new jar, with your actual best solution, and the new jar produce the same score on the first 3 official seeds as the online judge. (I don’t remember who but one of the top submission who used atan2l has different score with the online judge and the final jar. But I had two change his code to compile e.g atan2l -> atan2 but I haven’t find out why thes score was different. )

@iscsi: I didn’t check the final jar (the last one I used was DartsNew.jar, where the training and scoring MersenneTwisters had the same seed). It’s very good that you didn’t use the same seeds in the online judge :slight_smile: Even if I had noticed that the seeds were shifted by a fixed amount in the final version of the offline tester, this is something that cannot be exploited anyway (i.e. even if you use just seed+1 for the official darts, nothing in the training darts can tell me about what will happen with the official darts). It would have been bad for the judge to be so “exploitable” :slight_smile:

1 Like

@when be the editorial will be complete and final ?