1
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.