I am competing in a programming contest where the submission phase can be stated abstractly as follows : There is a known universe set, $U$, and a hidden target $T \subset U$. I submit $S \subset U$, and for feedback I am given $|S \cap T|$.

Two questions :

1) What is a good/optimal strategy for finding $T$ in as few submissions as possible given no assumptions on the distribution of $T$?

2) What if for each $u \in U$, there is a known probability, $P(u \in T)$, and the elements of $T$ are chosen independently according to those probabilities? Is it a good/optimal strategy to pick the set $S$ that gives the largest expected information gain given the feedback you have received so far? Is there an algorithm that would compute this set in a reasonable amount of time if $|U|$ is in the tens of millions and $|T|$ has a known size of around 5000?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.