An array $$$A$$$ of size $$$N$$$ ($$$N = 200$$$) is randomly filled with distinct integers in the range $$$[1,256]$$$ such that each of the possibilities is equally likely. You need to guess the array $$$A$$$. You can make your own array $$$B$$$ of size $$$N$$$ and a checker gives you two values :
- The number of distinct integers in your array which are also present in $$$A$$$.
- The number of indices where $$$A[i] = B[i]$$$.
The complexity of checker is $$$O(N^2)$$$. A solution which does around $$$40000$$$ queries is clearly possible, we can first find the integers in our array by $$$256$$$ queries and then their position by $$$200*200$$$ queries. I was wondering how much can we minimize the number of queries. Any ideas ?
