Nice Interactive Problem

Revision en1, by enlwfie, 2021-08-10 10:21:10

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 :

  1. The number of distinct integers in your array which are also present in $$$A$$$.
  2. 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.

Tags #interactive, #permutation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English enlwfie 2021-08-10 11:26:53 11 Tiny change: ' queries. ' -> ' queries. Any ideas ?'
en1 English enlwfie 2021-08-10 10:21:10 710 Initial revision (published)