Nice Interactive Problem

Правка en2, от enlwfie, 2021-08-10 11:26:53

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. Any ideas ?

Теги #interactive, #permutation

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский enlwfie 2021-08-10 11:26:53 11 Tiny change: ' queries. ' -> ' queries. Any ideas ?'
en1 Английский enlwfie 2021-08-10 10:21:10 710 Initial revision (published)