2
$\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|$.

What is a good/optimal strategy for finding $T$ in as few submissions as possible given no assumptions on the distribution of $T$? What are the complexity bounds in terms of $|U|$ and $|T|$? In my application, $|U|$ is in the tens of millions and $|T|$ has a known size of around 5000.

$\endgroup$
3
  • 1
    $\begingroup$ You might want to look for strategies for solving Mastermind. $\endgroup$
    – adrianN
    Oct 11, 2017 at 15:12
  • $\begingroup$ The usual rule is one question per post. $\endgroup$ Oct 11, 2017 at 20:11
  • $\begingroup$ @YuvalFilmus I edited it to make it one question. $\endgroup$ Oct 19, 2017 at 17:23

1 Answer 1

2
$\begingroup$

You are asking two questions. I will only answer the first, ignoring the fact that $|T|$ is much smaller than $|U|$. Your problem is very similar to the one tackled in this question. The same lower bound of $\Omega(n/\log n)$ holds here as well, where $n = |U|$. The same (apparently) matching upper bound also holds, since you can simulate a Hamming distance query using your kind of query.

$\endgroup$
1
  • $\begingroup$ This is very interesting. The introduction to the paper cited in the other post says "There are two cases of interest: (i) adaptive: the ith query is allowed to depend on all preceding queries and responses, and (ii) non-adaptive: the queries are formulated in advance. We only consider the non-adaptive case in this paper." I am interested in the adaptive case, which achieves much better results (more like $\log n$) when $|T|$ is much less than $|U|$. $\endgroup$ Oct 19, 2017 at 17:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.