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$
  • 1
    $\begingroup$ You might want to look for strategies for solving Mastermind. $\endgroup$ – adrianN Oct 11 '17 at 15:12
  • $\begingroup$ The usual rule is one question per post. $\endgroup$ – Yuval Filmus Oct 11 '17 at 20:11
  • $\begingroup$ @YuvalFilmus I edited it to make it one question. $\endgroup$ – Josh Brown Kramer Oct 19 '17 at 17:23
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$
  • $\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$ – Josh Brown Kramer Oct 19 '17 at 17:20

Your Answer

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

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