This competition will most likely run in several rounds. The first round only has as a goal to find an algorithm that computes the optimal order without strict limits on time or memory complexity, as long as you can create your submission on your computer on time.
Solutions that generate invalid sets or cannot find a valid subset will be disqualified.
The first round submission is a zip file containing a file called sequence_20_3.csv.
The naming scheme is sequence_N_M.csv, where N is the number of star candidates in the scene and M is the subset size, ie. the number of stars that need to be queried at once. These csv files contain no header and each row is one query for the database. The file has M columns and every cell contains a number between 0 and N-1 inclusive, which is the star candidate ID.
To calculate the score scenes with 20 candidates of which 3 to 20 are true stars are randomly generated. For 10 000 of these random scenes for each number of true stars, the submitted sequences are iterated and the number of sequences tried until a first valid is found is the score for this scene. The average score over the 10 000 scenes is summed up for all numbers of true stars to get the final score. In mathematical terms this is:
score = mean (mean sequences_tried(sequences, random_scene(i)) for all possible scenes wrt. T) for T = 3..20
If your submitted sequences cannot detect the correct sequence (because it is not contained), the score will be the number of sequences tried plus the worst case score.
The winner of the competition is the person with the lowest score. In case multiple people have the same lowest score, the submission time decides the winner.
In a second round we will evaluate other setups. Possible are for example:
where T is the number of true stars and we will averaged again over 10000 random scenes per combination.